2 options
Proceedings. 18th IEEE Annual Conference on Computational Complexity : 7-10 July, 2003, Aarhus, Denmark / sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF) ; in cooperation with ACM ... [and others].
Connect to full text Available online
View online- Format:
- Book
- Conference/Event
- Conference Name:
- IEEE Conference on Computational Complexity (18th : 2003 : Aarhus, Denmark)
- Language:
- English
- Subjects (All):
- Computational complexity--Congresses.
- Computational complexity.
- Nonlinear boundary value problems--Congresses.
- Nonlinear boundary value problems.
- Polynomials--Congresses.
- Polynomials.
- Logic programming--Congresses.
- Logic programming.
- Genre:
- Conference papers and proceedings.
- Physical Description:
- xiii, 387 pages : illustrations
- Other Title:
- 18th Annual IEEE Conference on Computational Complexity
- Computational Complexity
- Computational complexity, 2003, proceedings, 18th IEEE Annual Conference on.
- Place of Publication:
- Los Alamitos, Calif. : IEEE Computer Society, [2003]
- System Details:
- Mode of access: World Wide Web.
- text file
- Contents:
- The Legacy of Andrei Kolmogorov ix
- Ronald V. Book Prize for Best Student Paper xii
- 2003 Best Paper Award xiii
- Extremal Properties of Polynomial Threshold Functions / R. O'Donnell, R. Servedio 3
- Bounded Nondeterminism and Alternation in Parameterized Complexity Theory / Y. Chen, J. Flum, M. Grohe 13
- Uniform Hardness vs. Randomness Tradeoffs for Arthur-Merlin Games / D. Gutfreund, R. Shaltiel, A. Ta-Shma 33
- A Zero One Law for RP / R. Impagliazzo, P. Moser 48
- Hardness vs. Randomness within Alternating Time / E. Viola 53
- Lower Bounds for Predecessor Searching in the Cell Probe Model / P. Sen 73
- Minimization of Decision Trees Is Hard to Approximate / D. Sieling 84
- Optimal Separation of EROW and CROW PRAMs / N. Goyal, M. Saks, S. Venkatesh 93
- Near-Optimal Lower Bounds on the Multi-party Communication Complexity of Set Disjointness / A. Chakrabarti, S. Khot, X. Sun 107
- Rectangle Size Bounds and Threshold Covers in Communication Complexity / H. Klauck 118
- The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs / C. Calabro, R. Impagliazzo, V. Kabanets, R. Paturi 135
- Invited Talk
- Parameterized Complexity for the Skeptic / R. Downey 147
- Quantum Certificate Complexity / S. Aaronson 171
- Quantum Query Complexity and Semi-definite Programming / H. Barnum, M. Saks, M. Szegedy 179
- On Statistical Query Sampling and NMR Quantum Computing / A. Blum, K. Yang 194
- Derandomization and Distinguishing Complexity / E. Allender, M. Koucky, D. Ronneburger, S. Roy 209
- Extracting the Mutual Information for a Triple of Binary Strings / A. Romashchenko 221
- The Complexity of Stochastic Sequences / W. Merkle 230
- A Combinatorial Characterization of Resolution Width / A. Atserias, V. Dalmau 239
- Memoization and DPLL: Formula Caching Proof Systems / P. Beame, R. Impagliazzo, T. Pitassi, N. Segerlind 248
- Inapproximability
- Some History and Some Open Problems / J. Hastad 265
- Holographic Proofs and Derandomization / R. Santhanam, D. van Melkebeek 269
- Three-Query PCPs with Perfect Completeness over Non-Boolean Domains / L. Engebretsen, J. Holmerin 284
- List Decoding with Side Information / V. Guruswami 300
- Disjoint NP-Pairs / C. Glasser, A. Selman, S. Sengupta, L. Zhang 313
- Are Cook and Karp Ever the Same? / R. Beigel, L. Fortnow 333
- Universal Languages and the Power of Diagonalization / A. Nash, R. Impagliazzo, J. Remmel 337
- Proving SAT Does Not Have Small Circuits with an Application to the Two Queries Problem / L. Fortnow, A. Pavan, S. Sengupta 347
- On Derandomizing Tests for Certain Polynomial Identities / M. Agrawal 355
- Improved Inapproximability of Lattice and Coding Problems with Preprocessing / O. Regev 363
- A Strong Inapproximability Gap for a Generalization of Minimum Bisection / J. Holmerin, S. Khot 371
- Vertex Cover Might Be Hard to Approximate to within 2-[epsilon] / S. Khot, O. Regev 379.
- Notes:
- Includes bibliographical references and author index.
- "IEEE Computer Society Order Number PR01879"--T.p. verso.
- ISBN:
- 0769518796
- 9780769518794
- OCLC:
- 52689041
- Access Restriction:
- Restricted for use by site license.
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.