22. CCC 2007:
San Diego,
California,
USA
22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA.
IEEE Computer Society 2007 BibTeX
Wednesday,
June 13
- Marius Zimand:
On Derandomizing Probabilistic Sublinear-Time Algorithms.
1-9
Electronic Edition (link) BibTeX
- Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan:
The Communication Complexity of Correlation.
10-23
Electronic Edition (link) BibTeX
- Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf:
On Computation and Communication with Small Bias.
24-32
Electronic Edition (link) BibTeX
- Amit Chakrabarti:
Lower Bounds for Multi-Player Pointer Jumping.
33-45
Electronic Edition (link) BibTeX
- Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find.
46-51
Electronic Edition (link) BibTeX
- Richard Chang, Suresh Purini:
Bounded Queries and the NP Machine Hypothesis.
52-59
Electronic Edition (link) BibTeX
- Wolfgang Merkle, Frank Stephan:
On C-Degrees, H-Degrees and T-Degrees.
60-69
Electronic Edition (link) BibTeX
Thursday,
June 14th
- Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.
70-82
Electronic Edition (link) BibTeX
- Alexander A. Sherstov:
Halfspace Matrices.
83-95
Electronic Edition (link) BibTeX
- Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
96-108
Electronic Edition (link) BibTeX
- Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay:
Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems.
109-114
Electronic Edition (link) BibTeX
- Scott Aaronson, Greg Kuperberg:
Quantum versus Classical Proofs and Advice.
115-128
Electronic Edition (link) BibTeX
- Andris Ambainis, Joseph Emerson:
Quantum t-designs: t-wise Independence in the Quantum World.
129-140
Electronic Edition (link) BibTeX
- Emanuele Viola, Avi Wigderson:
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols.
141-154
Electronic Edition (link) BibTeX
- Emanuele Viola:
On Approximate Majority and Probabilistic Time.
155-168
Electronic Edition (link) BibTeX
- Kei Uchizawa, Eiji Takimoto:
An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity.
169-178
Electronic Edition (link) BibTeX
Friday,
June 15th
- Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams.
179-192
Electronic Edition (link) BibTeX
- Guillaume Malod:
The Complexity of Polynomials and Their Coefficient Functions.
193-204
Electronic Edition (link) BibTeX
- Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
205-216
Electronic Edition (link) BibTeX
- Chris Bourke, Raghunath Tewari, N. V. Vinodchandran:
Directed Planar Reachability is in Unambiguous Log-Space.
217-221
Electronic Edition (link) BibTeX
- Mark Braverman, Raghav Kulkarni, Sambuddha Roy:
Parity Problems in Planar Graphs.
222-235
Electronic Edition (link) BibTeX
- Kai-Min Chung, Omer Reingold, Salil P. Vadhan:
S-T Connectivity on Digraphs with a Known Stationary Distribution.
236-249
Electronic Edition (link) BibTeX
- Yijia Chen, Jörg Flum:
On Parameterized Path and Chordless Path Problems.
250-263
Electronic Edition (link) BibTeX
- Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Properties of Constraint-Graphs.
264-277
Electronic Edition (link) BibTeX
- Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky:
Efficient Arguments without Short PCPs.
278-291
Electronic Edition (link) BibTeX
Saturday,
June 16th
Copyright © Sat May 16 23:02:44 2009
by Michael Ley (ley@uni-trier.de)
