The Third Western New York Theory Day
Friday, May 2, 2008

Introduction

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.

Program

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

Location

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.


View Larger Map

Organizers

Edith Hemaspaandra, Rochester Institute of Technology
Lane A. Hemaspaandra, University of Rochester
Alan Selman, University at Buffalo
Piotr Faliszewski, University of Rochester


Abstracts

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.