default search action
18th CCC 2003: Aarhus, Denmark
- 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark. IEEE Computer Society 2003, ISBN 0-7695-1879-6
Session 1
- Ryan O'Donnell, Rocco A. Servedio:
Extremal properties of polynomial threshold functions. 3-12 - Yijia Chen, Jörg Flum, Martin Grohe:
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. 13-29
Session 2
- Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
:
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. 33-47 - Russell Impagliazzo
A zero one law for RP. 48-52 - Emanuele Viola:
Hardness vs. Randomness within Alternating Time. 53-
Session 3
- Pranab Sen:
Lower bounds for predecessor searching in the cell probe model. 73-83 - Detlef Sieling:
Minimization of Decision Trees Is Hard to Approximate. 84-92 - Navin Goyal, Michael E. Saks, Srinivasan Venkatesh:
Optimal Separation of EROW and CROWPRAMs. 93-
Session 4
- Amit Chakrabarti, Subhash Khot, Xiaodong Sun:
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. 107-117 - Hartmut Klauck:
Rectangle Size Bounds and Threshold Covers in Communication Complexity. 118-134 - Chris Calabro, Russell Impagliazzo
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. 135-
Session 6
- Scott Aaronson:
Quantum Certificate Complexity. 171-178 - Howard Barnum, Michael E. Saks, Mario Szegedy:
Quantum query complexity and semi-definite programming. 179-193 - Ke Yang, Avrim Blum:
On Statistical Query Sampling and NMR Quantum Computing. 194-
Session 7
- Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
Derandomization and Distinguishing Complexity. 209-220 - Andrei E. Romashchenko:
Extracting the Mutual Information for a Triple of Binary Strings. 221-229 - Wolfgang Merkle:
The complexity of stochastic sequences. 230-
Session 8
- Albert Atserias, Víctor Dalmau:
A Combinatorial Characterization of Resolution Width. 239-247 - Paul Beame
Memoization and DPLL: Formula Caching Proof Systems. 248-
Invited Talk
- Johan Håstad
Inapproximability Some history and some open problems. 265-
Session 10
- Rahul Santhanam, Dieter van Melkebeek:
Holographic Proofs and Derandomization. 269-283 - Lars Engebretsen, Jonas Holmerin:
Three-Query PCPs with Perfect Completeness over non-Boolean Domains. 284-299 - Venkatesan Guruswami:
List Decoding with Side Information. 300-
Session 11
- Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
Disjoint NP-Pairs. 313-332 - Richard Beigel, Lance Fortnow:
Are Cook and Karp Ever the Same? 333-336 - Alan Nash, Russell Impagliazzo
Universal Languages and the Power of Diagonalization. 337-346 - Lance Fortnow, Aduri Pavan, Samik Sengupta:
Proving SAT does not have Small Circuits with an Application to the Two. 347-
Invited Talk
- Manindra Agrawal:
On Derandomizing Tests for Certain Polynomial Identities. 355-
Session 13
- Oded Regev:
Improved Inapproximability of Lattice and Coding Problems with Preprocessing. 363-370 - Jonas Holmerin, Subhash Khot:
A Strong Inapproximability Gap for a Generalization of Minimum Bisection. 371-378 - Subhash Khot, Oded Regev:
Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. 379-
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-11-27 20:17 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: