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