Volume 6 (2010)
Vol 6, Article 1 (pp 1-25)
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search by Andris Ambainis |
Vol 6, Article 2 (pp 27-46)
Reordering Buffers for General Metric Spaces by Matthias Englert, Harald Räcke, and Matthias Westermann |
Vol 6, Article 3 (pp 47-79)
Quantum Expanders: Motivation and Construction by Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma |
Vol 6, Article 4 (pp 81-84)
[NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality by Homin K. Lee |
Vol 6, Article 5 (pp 85-112)
Can You Beat Treewidth? by Dániel Marx |
Vol 6, Article 6 (pp 113-134)
Rounds vs. Queries Tradeoff in Noisy Computation by Navin Goyal and Michael Saks |
Vol 6, Article 7 (pp 135-177)
Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz |
Vol 6, Article 8 (pp 179-199)
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games by Avrim Blum, Eyal Even-Dar, and Katrina Ligett |
Vol 6, Article 9 (pp 201-225)
Separating Deterministic from Randomized Multiparty Communication Complexity by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel |
Vol 6, Article 10 (pp 227-245)
A Separation of NP and coNP in Multiparty Communication Complexity by Dmitry Gavinsky and Alexander A. Sherstov |
Vol 6, Article 11 (pp 247-290)
The Submodular Welfare Problem with Demand Queries by Uriel Feige and Jan Vondrák |
Vol 6, Article 12 (pp 291-308)
[RESEARCH SURVEY]
Monotone Expanders: Constructions and Applications by Zeev Dvir and Avi Wigderson |
List of Editors |