Vita and Publications

My vita in pdf (including a list of publications)

· On the communication complexity of distributions.   With Jeremie Roland
· A new Line of Attack on the Dichotomy Conjecture.   With Gabor Kun
· Theory and algorithmic applications of quantum walks. (survey)   With Peter Richter

Most Recent Published Works
· Geometric representation of cubic graphs with four directions.   With Padmini Mukkamala (submitted)
· Parallel Repetitions of the Odd Cycle Game.   With Kooshiar Azimian (Latin 2008)
· Delaunay graphs of point sets in the plane with respect to axis parallel rectangles.   With Xiaomin Chen, Janos Pach and Gabor Tardos (SODA 2008)
· Product Rules in Semidefinite Programming.   With Rajat Mittal (FCT 2007)
· On the Variance of Subset Sum Estimation.   With Mikkel Thorup (ESA 2007)

Some Fairly Recent Papers
· Languages with Bounded Multiparty Communication Complexity   With Arkadev Chattopadhyay, Andreas Krebs, Michal Koucky, Pascal Tesson, Denis Therien(STACS 2007)
· The DLT priority sampling is essentially optimal.   (STOC 2006)
· The Quantum Adversary Method and Classical Formula Size Lower Bounds.   With Sophie Laplante and Troy Lee (Computational Complexity 2006)
· All Quantum Adversary Methods are Equivalent   With Robert Spalek (ICALP 2005)
· Quantum algorithms for the triangle problem.   With Frederic Magniez and Miklos Santha (Siam Journal of Computing 2007)
· Quantum Speed-Up of Markov Chain Based Algorithms.   (FOCS 2004)
· Quantum and classical query complexities of local search are polynomially related.   With Miklos Santha (Algorithmica 2008)
· Quantum query complexity and semi-definite programming.   With Howard Barnum and Mike Saks (Computational Complexity 2003)

Some older publications available on-line:

Computer Science


Combinatorics and Combinatorial Number Theory