default search action
20th CCC 2005: San Jose, CA, USA
- 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA. IEEE Computer Society 2005, ISBN 0-7695-2364-1
Introduction
- Preface.
- Committees.
- Awards.
Session 1
- Neeraj Kayal, Nitin Saxena
:
On the Ring Isomorphism and Automorphism Problems. 2-12 - Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan:
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. 13-27 - Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia and Some Closure Properties of GapL. 28-37
Session 2 (Best Student Paper Award)
- Ryan Williams
Better Time-Space Lower Bounds for SAT and Related Problems. 40-49
Session 3
- Paul Beame
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. 52-66 - Amos Beimel
Monotone Circuits for Weighted Threshold Functions. 67-75 - Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. 76-90
Session 4
- Andrej Bogdanov, Hoeteck Wee:
More on Noncommutative Polynomial Identity Testing. 92-99 - Ingo Wegener, Philipp Woelfel:
New Results on the Complexity of the Middle Bit of Multiplication. 100-110
Session 5
- Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi:
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. 112-119 - Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Short PCPs Verifiable in Polylogarithmic Time. 120-134 - Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. 135-140
Session 6 (Invited Lecture)
Session 7
- Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani
On the Hardness of Approximating Multicut and Sparsest-Cut. 144-153 - Venkatesan Guruswami, Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses. 154-162 - Sourav Chakraborty:
On the Sensitivity of Cyclically-Invariant Boolean Functions. 163-167
Session 8
- Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu:
On the Complexity of Hardness Amplification. 170-182 - Emanuele Viola:
On Constructing Parallel Pseudorandom Generators from One-Way Functions. 183-197 - Emanuele Viola:
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates. 198-209
Session 9 (Best Paper Award)
- Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. 212-226
Session 10
- Lance Fortnow, Adam R. Klivans:
NP with Small Advice. 228-234 - Arfst Nickelsen, Birgit Schelm:
Average-Case Computations - Comparing AvgP, HP, and Nearly-P. 235-242 - Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances. 243-257
Session 11
- Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Computationally Private Randomizing Polynomials and Their Applications. 260-274 - David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. 275-284 - Rahul Jain
Prior Entanglement, Message Compression and Privacy in Quantum Communication. 285-296
Session 12
- Eric Allender, Samir Datta
Topology Inside NC¹. 298-307 - Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo
Toward a Model for Backtracking and Dynamic Programming. 308-322 - Lance Fortnow, Russell Impagliazzo
On the Complexity of Succinct Zero-Sum Games. 323-332
Session 13
- Gus Gutoski:
Upper Bounds for Quantum Interactive Proofs with Competing Provers. 334-343 - Bill Rosgen:
On the Hardness of Distinguishing Mixed-State Quantum Computations. 344-354
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-19 22:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: