Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID17th CCC 2002: Montréal, Québec, Canada
- Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002. IEEE Computer Society 2002, ISBN 0-7695-1468-5
Session 1: Joint Session with STOC 2002
- Ran Raz
:
Resolution Lower Bounds for the Weak Pigeonhole Principle. 3 - Eli Ben-Sasson:
Hard Examples for Bounded Depth Frege. 4 - Uriel Feige:
Relations between Average Case Complexity and Approximation Complexity. 5 - Jonas Holmerin:
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε. 6
Session 2: Joint Session with STOC 2002
- Daniele Micciancio:
Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection. 9 - D. Sivakumar:
Algorithmic Derandomization via Complexity Theory. 10 - Christopher Umans:
Pseudo-Random Generators for All Hardnesses. 11
Session 3: Joint Session with STOC 2002
- Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson:
Randomness Conductors and Constant-Degree Lossless Expanders. 15 - Roy Meshulam, Avi Wigderson:
Expanders from Symmetric Codes. 16 - Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
The Complexity of Approximating the Entropy. 17 - Paul Beame, Erik Vee:
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. 18 - Ashwin Nayak, Julia Salzman:
On Communication over an Entanglement-Assisted Quantum Channel. 19
Session 4: Joint Session with STOC 2002
- Ryan O'Donnell:
Hardness Amplification within NP. 23 - Ian Agol, Joel Hass, William P. Thurston:
3-MANIFOLD KNOT GENUS is NP-complete. 24 - Subhash Khot:
On the Power of Unique 2-Prover 1-Round Games. 25 - Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio:
Learnability beyond AC0. 26
Session 5
- Alexander A. Razborov:
Resolution Lower Bounds for Perfect Matching Principles. 29-38 - Stefan S. Dantchev:
Resolution Width-Size Trade-offs for the Pigeon-Hole Principle. 39-43 - Uriel Feige, Daniele Micciancio:
The Inapproximability of Lattice and Coding Problems with Preprocessing. 44-52 - Miklós Ajtai, Ravi Kumar, D. Sivakumar:
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. 53-57
Invited Address 1
- Lance Fortnow:
The History of Complexity. 61
Session 6
- Frederic Green:
The Correlation Between Parity and Quadratic Polynomials Mod 3. 65-72 - Eldar Fischer, Ilan Newman:
Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. 73-79 - Philipp Woelfel:
On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism. 80-89
Session 7
- Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar:
Information Theory Methods in Communication Complexity. 93-102 - Andris Ambainis, Adam D. Smith, Ke Yang:
Extracting Quantum Entanglement. 103-112 - Markus Bläser:
Algebras of Minimal Rank over Perfect Fields. 113-122
Invited Address 2
- Peter Winkler:
Rapid Mixing. 125
Session 8
- Luca Trevisan, Salil P. Vadhan:
Pseudorandomness and Average-Case Complexity via Uniform Reductions. 129-138 - Manindra Agrawal:
Pseudo-Random Generators and Structure of Complete Degrees. 139-147 - Venkatesan Guruswami, Madhu Sudan:
Decoding Concatenated Codes using Soft Information. 148-157
Survey Talk 1
- John Watrous:
Arthur and Merlin in a Quantum World. 161
Session 9
- Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel:
Streaming Computation of Combinatorial Objects. 165-174 - Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. 175-183 - Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam:
Better Lower Bounds for Locally Decodable Codes. 184-193 - Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. 194-203
a service of 
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-04-25 05:27 CEST 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:
