Seminar on Jan. 11, 2011

Date: Jan. 11, 2011

Venue: Fudan Zhangjiang Campus, Software School Building, room 105 (IBM Lab meeting room)

Schedule of talks:

11am Yin Yitong

Certificate Complexity: a new lower bound tool for data structures


A classic lower bound technique for static data structures is the communication complexity. However, since every data structure problem has a trivial communication protocol, communication complexity can not be used to prove high lower bounds for data structures; and communication complexity tells us little about other aspects of data structure complexity, such as nondeterminism or the interactive proofs.

I will talk about certificates in data structures and show its potentials to overcome the above limitations. I will show that unlike communication complexity, there exist hard problems that are hard to certify, and the richness lemma in communication complexity holds for certificates with exactly the same parameters. Then I will use certificates to prove the intractability of several high dimensional problems in distributed localized data structures. All these results are due to a combinatorial characterization of certificates in data structures.


In September 2009, Yin Yitong joined the LAMDA group in the Department of Computer Science and Technology at Nanjing University. Before that, he was a PhD candidate in the Theory Group in the Computer Science Department at Yale University, under the supervision of James Aspnes.

12am Lunch

2pm David Woodruff

Efficient Sketches for Earth-Mover Distance and Cascaded Moments


We provide the first sub-linear sketching algorithm for estimating the planar Earth-Mover Distance with a constant approximation. For sets living in the two-dimensional grid [Delta]^2, we achieve space Delta^{eps} for approximation O(1/eps), for any desired 0< eps < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.

Our result is achieved by obtaining new sketches for product norms and cascaded moments, which have several other applications.  Based on two papers, the union of the coauthors being Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and T.S. Jayram.


David Woodruff is a Research Scientist at IBM Almaden. David obtained a Ph.D. in computer science in 2007 from MIT. He spent a year (2005-2006) at Tsinghua University as a visiting student of Andy Yao. His interests are in data streams and sketching, learning and network algorithms, and coding theory. He received the Best Paper Award in PODS, 2010.

3pm Uri Zwick

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm


The *simplex* algorithm is among the most widely used algorithms for solving *linear programs* in practice. Most *deterministic* pivoting rules are known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for *randomized* pivoting rules. We provide the first *subexponential* (i.e., of the form~$2^{\Omega(n^\alpha)}$, for some $\alpha>0$) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

The first randomized pivoting rule considered is *Random-Edge*, which among all improving pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule we consider is *Random-Facet*, a more complicated randomized pivoting rule suggested by Kalai and by Matousek, Sharir and Welzl .

Our lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and *improving switches* performed by *policy iteration* algorithms for 1-player and 2-player games. We start by building 2-player *parity games* (PGs) on which suitable randomized policy iteration algorithms perform a subexponential number of iterations. We then transform these 2-player games into 1-player *Markov Decision Processes* (MDPs) which correspond almost immediately to concrete linear programs.

Joint work with Oliver Friedmann and Thomas Dueholm Hansen


Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University.

He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.