IEEE Conference on Computational Complexity
The project organizes the 24th IEEE Conference on Computational Complexity in Paris, July 15th to July 18th, 2009: Local arrangements
Randomized Algorithms
Streaming Algorithms
F. Magniez, C. Mathieu and A. Nayak (2010) Recognizing well-parenthesized expressions in the streaming model. In Proceedings of 42nd ACM Symposium on Theory of Computing, pages 261-270. (PDF) (BibTeX)
With concrete applications in mind, and theoretical motivations, we initiated the streaming complexity of language recognition. On the way, we exhibit a curious phenomenon: an explicit, natural data stream problem that is fairly easy given two passes in opposite directions, whereas it is exponentially harder if only multiple unidirectional passes are allowed.
Online Computing
Y. Emek, P. Fraigniaud, A. Korman and A. Rosén (2009) Online Computation with Advice. In Proc. ICALP'09, pages 427-438. (PDF) (BibTeX)
We introduce the new model of online computing with advice and gives (sometimes tight) results on two of the most extensively studied online problems.
Algorithmic Game Theory
F. Magniez, M. de Rougemont, M. Santha and X. Zeitoun (2011) The complexity of approximate Nash equilibrium in congestion games with negative delays. In Proceedings of 7th Workshop on Internet and Network Economics (WINE) Pages 266-277. (PDF) (BibTeX)
We extend the study of the complexity of computing an approximate Nash equilibrium in symmetric congestion games from the case of positive delay functions to delays of arbitrary sign. Our results show that with this extension the complexity has a richer structure, and it depends on the exact nature of the signs allowed.
Quantum Computation
Quantum Algorithms
F. Magniez, A. Nayak, P. Richter and M. Santha (2009) On the hitting times of quantum versus random walks. In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, pages 86-95. (PDF) (BibTeX)
We define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.
T. Lee F. Magniez and M. Santha (2013) Improved quantum query algorithms for triangle finding and associativity testing. In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pages 1486-1502. (PDF) (BibTeX)
Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity.
Quantum Lower Bounds and Complexity
A. Ambainis, L. Magnin, M. Roetteler and J. Roland (2011) Symmetry-assisted adversaries for quantum state generation. In Proceedings of the 26th IEEE Conference on Computational Complexity, pages 167-177. (PDF) (BibTeX)
We introduce a new quantum adversary method to prove lower bounds on the query complex- ity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. We show that for the problem of Index Erasure our method leads to a tight lower bound, closing open problem first raised by Shi in FOCSÂ’02.
Quantum information and communication
A. Chailloux and I. Kerenidis (2009) Optimal quantum strong coin flipping. In FOCS'09. (PDF) (BibTeX)
André Chailloux and Iordanis Kerenidis (2011) Optimal bounds for quantum bit commitment. In Proc. of IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 354-362. (PDF) (BibTeX)
We resolve two of the main questions in the area of quantum cryptographic primitives, that of the optimal bias of any quantum coin flipping protocol, by providing a new protocol matching the previously known lower bound, and of any quantum bit commitment, by providing a new protocol matching a new lower bound.
Interaction between classical and quantum computation
Randomized Lower bounds and Complexity
F. Magniez, A. Nayak, M. Santha and D. Xiao (2011) Improved bounds for the randomized decision tree complexity of recursive majority. In Proceedings of 38th International Colloquium on Automata, Languages and Programming. LNCS. (PDF) (BibTeX)
We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating height h formulae, we prove a lower bound for the two-sided-error randomized decision tree complexity of 2.5^h, improving the lower bound of 2.333^h given by Jayram, Kumar, and Sivakumar (STOC ’03). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most 2.649^h. The previous best known algorithm achieved complexity 2.656^h. The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel “interleaving” of two recursive algorithms.
Proof Systems
Andris Ambainis, Julia Kempe and Or Sattath (2010) A quantum Lovász Local Lemma. In Proceedings of ACM STOC, pages 151-160. (PDF) (BibTeX)
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the exis- tence of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem
Julia Kempe and Thomas Vidick (2011) Parallel repetition of entangled games. In Proc. 43rd ACM STOC, pages 353-362. (PDF) (BibTeX)
We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in RazÂ’s celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1.
Classical and quantum communication protocols
S. Laplante, V. Lerays and J. Roland (2012) Classical and quantum partition bound and detector inefficiency. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP). (PDF) (BibTeX)
In the standard setting of communication complexity, two players each have an input and they wish to compute some function of the joint inputs. The best current lower bound methods is the partition bound, introduced by Jain and Klauck. Physicists have considered a closely related scenario where two players share a predefined entangled state, and produce some outcome distribution which is predicted by quantum mechanics. Physicists want to rule out the possibility that there is a classical explanation for the distribution, through loopholes such as communication or detector inefficiency. We present a new lower bound technique based on the notion of detector inefficiency, and show that it coincides with the partition bound.
I. Kerenidis, S. Laplante, V. Lerays, J. Roland and D. Xiao (2012) Lower bounds on information complexity via zero-communication protocols and applications. In Proceedings of 53rd Annual Symposium on Foundations of Computer Science (FOCS) Pages 500-509. (PDF) (BibTeX)
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods and rectangle-based methods, except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort.