The Western New York Theory Day series is a joint project of the theory groups at Rochester Institute of Technology, the University at Buffalo, and the University of Rochester. The meetings are once or twice yearly and rotate between the three schools. The two "visiting" schools usually provide the speakers.
These meetings bring people together in a friendly, informal atmosphere to hear about recent research advances in theoretical computer science. The meetings are open to the public, and all are warmly invited to attend.
9:30 | -9:45 | Coffee | |
9:45 | -10:45 | Joan Lucas, State University of New York, College at Brockport | |
New Results for Splay Trees: From O(n \alpha(n)) to O(n \alpha*(n)) | (Slides available here.) | ||
10:50 | -11:50 | Kenneth Regan, State University of New York, University at Buffalo | |
Are Instances of Small Kolmogorov Complexity Often Hard? | |||
11:50 | -1:45 | Lunch break | |
1:45 | -2:45 | Atri Rudra, State University of New York, University at Buffalo | |
Recovering Data in Presence of Malicious Errors | (Slides available here.) | ||
2:50 | -3:50 | Ivona Bezakova, Rochester Institute of Technology | |
Convex Combinations of Markov Chains |
The Theory Day will be held in
Room CSB 601 (Computer Studies Bldg., 6th floor, to the right when coming out of the elevator)
University of Rochester
734 Computer Studies Bldg.
Rochester, NY 14627-0226
Directions to UofR and to the computer science department. The department is located in Computer Studies Building, 160 Trustee Rd., Rochester NY 14627.
Information
on visitor parking at River Campus of University of Rochester
(the short "River Campus Visitors" initial segment
is what to look at---not the long
"Medical Center Visitors" section).
You should please follow the instructions at that link, and whatever
instructions the agent at the Information Booth gives you when you
arrive, extremely carefully (e.g., make sure to park in a lot
that the agent directs you to, rather than to whatever lot---e.g.,
the administration's special lot---happens to
look convenient), to avoid ending up with a parking ticket (our
parking enforcement people seem to have reached
perfect efficiency---they should be a model for the rest of the university!).
The map below shows the location of the Information Booth warning:
(not of the CS Building!), where you can purchase parking
passes (the price is, I think, $4, a great deal for four talks!);
you'll probably want to click the "+" button on the top-left part of
the map if you want to see all the involved street names (one thing to
also note: On the map it looks as if Intercampus and Elmwood cross but
in fact, due to Intercampus going over Elmwood on a bridge, there is
no connection between them). Oh... please leave extra time... parking
will probably take longer than you expect, and the Information Booth
agent (depending on what is available that day) may well put you in a
lot halfway across campus, although he or she will give you a campus
map if you ask so you can at least find your way to park at the
appropriate lot and then to walk back to the Computer Studies
Building.
New Results for Splay Trees: From O(n \alpha(n)) to O(n \alpha*(n))
Joan Lucas, State University of New York, College at Brockport
Sleator and Tarjan introduced the splay tree in 1985 and conjectured that it is dynamically optimal (i.e., as good as any other binary search tree). This general conjecture remains open, although splay trees have been shown optimal in many special cases. In particular, splay trees should have O(n) complexity when performing deque (double-ended queue) operations. In this talk we describe the recent result of Seth Pettie that improves the known bound for a splay tree deque from O(n \alpha(n)) to O(n \alpha*(n)), where \alpha(n) is the inverse Ackermann function. Pettie employs a novel technique to obtain this result. He illustrates how the complexity of splaying can be related to Davenport-Schinzel sequences, and then uses well known bounds on the length of such sequences to bound the cost of splaying.
Are Instances of Small Kolmogorov Complexity Often Hard?
Kenneth Regan, State University of New York, University at Buffalo
It is a truism that the hardest instances of length n for a program A have low Kolmogorov complexity, because this sentence is a description of size log_2(n) + constant for such instance(s). This is basically the proof of an old theorem by Li and Vitanyi that average-case running times under Kolmogorov-based distributions have the same order as the worst-case running time. It is also known that many NP-hard problems are easy under uniform distributions, so incompressible instances tend to be easy. This leaves the question: do /most/ or /many/ compressible instances tend to be harder, in practice, than the random ones? We ask this in particular for the instances in the range of a pseudorandom generator g: {0,1}^m --> {0,1}^n, with m = \sqrt(n), say. We also investigate the parameterized complexity of problems whereby the parameter k applies to instances of Kolmogorov complexity (conditioned on the length n) k or k*log(n). Part of this is joint work in progress with Jonathan Buss.
Recovering Data in Presence of Malicious Errors
Atri Rudra, State University of New York, University at Buffalo
Suppose you want to communicate k packets over a noisy communication channel. This is a common scenario when transmitting data over any real world channel such as the Internet or the telephone line. In order to tolerate errors, you transmit a redundant collection of n=c*k packets. When can you communicate reliably despite the adverse effects of the noisy channel? That is, when can the receiver recover the original message even in the presence of corrupted packets? Clearly, the receiver must receive at least k correct packets to have any hope of recovering the original message. In this talk, I will describe an efficient encoding (and decoding) scheme that achieves this information theoretical limit: for any eps>0, the receiver can recover the original message as long as (1+eps)*k packets are not corrupted. The location of the correct packets and the errors can be chosen adversarially by the channel. This achieves the optimal trade-off (called "capacity") between redundancy and error-resilience for a malicious noise model where the channel can corrupt the transmitted symbols arbitrarily subject to a bound on the total number of errors. These results are obtained in an error-recovery model called list decoding. In the second part of the talk I will focus on some important challenges that are yet to be resolved and describe some recent developments that make some (small) progress towards addressing those questions. The talk will be self-contained and is based on joint works with Venkat Guruswami (U. of Washington)
Convex Combinations of Markov Chains
Ivona Bezakova, Rochester Institute of Technology
We will discuss the use of Markov chains for sampling and counting combinatorial objects that belong to potentially exponentially large sets. Examples include coloring the vertices of a graph with k colors, perfect matchings of graphs, etc. For many of these applications it is sufficient to know how to sample these objects - then we can use sampling to (approximately - that is within (1+epsilon) factor) count all the objects. Often the fastest way to do this is through a so-called simulated annealing technique where we use a sequence of Markov chains to estimate certain probabilities and the product of these gives us the desired result. These Markov chains can be phrased as convex combinations of two other Markov chains; and for the technique to be applied successfully, each of the intermediate Markov chains must be mixing rapidly (that is, it must get to a random sample within a polynomial number of steps). We will study conditions under which convex combinations of Markov chains mix rapidly and we will prove both positive and negative results - it is possible that the two "parent" Markov chains mix rapidly but their convex combination does not; and there are conditions under which the convex combination always mixes rapidly. This is joint work with Daniel Stefankovic.