Title: Abelian Permutation Group Problems and Logspace Counting Classes
Author(s): V. Arvind and T.C. Vijayaraghavan
Title: Compression of Samplable Sources
Author(s): Luca Trevisan, Salil Vadhan, and David Zuckerman
Title: Computing in fault tolerance broadcast networks
Author(s): Ilan Newman
Title: Consequences and Limits of Nonlocal Strategies
Author(s): R. Cleve and P. Hoyer and B. Toner and J. Watrous
Title: Deterministic Polynomial Identity Testing in Non Commutative Models
Author(s): Ran Raz, Amir Shpilka
Title: Dimension, Entropy Rates, and Compression
Author(s): John M. Hitchcock and N. V. Vinodchandran
Title: Graph properties and circular functions: how low can quantum query
complexity go?
Author(s): Xiaoming Sun, Andrew C. Yao and Shengyu Zhang
Title: Language Compression and Pseudorandom Generators
Author(s): Harry Buhrman, Troy Lee, Dieter van Melkebeek
Title: Lower Bounds for Testing Bipartiteness in Dense Graphs
Author(s): Andrej Bogdanov, Luca Trevisan
Title: Lower bounds for randomized and quantum query complexity using Kolmogorov
arguments
Author(s): Sophie Laplante and Frederic Magniez
Title: Multiparty Quantum Coin Flipping
Author(s): Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Roehrig
Title: On Pseudoentropy versus Compressibility
Author(s): Hoeteck Wee
Title: On the power of Quantum Proofs
Author(s): Ran Raz, Amir Shpilka
Title: Parameterized complexity of constraint satisfaction problems
Author(s): Daniel Marx
Title: Partial bi-immunity and NP-completeness
Author(s): John M. Hitchcock, A. Pavan, N. V. Vinodchandran
Title: Polylogarithmic-round Interactive Proofs for coNP
Author(s): Alan L. Selman, Samik Sengupta
Title: Polynomials that Sign Represent Parity and Descartes Rule of Signs
Author(s): Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J.
Lipton
Title: Properties of NP-Complete Sets
Author(s): Christian Glasser, A. Pavan, Alan L. Selman, Samik Sengupta
Title: Quantum Arthur-Merlin Games
Author(s): Chris Marriott and John Watrous
Title: Reductions between Disjoint NP-Pairs
Author(s): Christian Glasser, Alan L. Selman, Samik Sengupta
Title: Relativized NP search problems and propositional proof systems
Author(s): Joshua Buresh-Oppenheim and Tsuyoshi Morioka
Title: Separating complexity classes using structural properties
Author(s): Harry Buhrman and Leen Torenvliet
Title: Small Spans in Scaled Dimension
Author(s): John M. Hitchcock
Title: Solvable Group Isomorphism is (almost) in NP∩coNP
Author(s): V. Arvind and Jacobo Toran
Title: Some Results on Majority Quantifiers over words
Author(s): Klaus-Joern Lange
Title: The Complexity of Treelike Systems over λ-Local Formulae
Author(s): Nicola Galesi, Neil Thapen
Title: The Complexity of the Covering Radius Problem on Lattices and Codes
Author(s): Venkatesan Guruswami, Daniele Micciancio, Oded Regev
Title: Tight Lower Bounds for Certain Parameterized NP-hard Problems
Author(s): Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes,
Iyad A. Kanj, Ge Xia
Title: Towards the Classical Communication Complexity of Entanglement
Distillation Protocols with Incomplete Information
Author(s): Andris Ambainis, Ke Yang
Title: Limitations of Quantum Advice and One-Way Communication
Author(s): Scott Aaronson