default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID14th CCC 1999: Atlanta, Georgia, USA
- Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999. IEEE Computer Society 1999, ISBN 0-7695-0075-7
Joint STOC/Complexity Session
- Eli Ben-Sasson, Avi Wigderson:
Short Proofs Are Narrow - Resolution Made Simple (Abstract). 2 - J. Maurice Rojas:
On the Complexity of Diophantine Geometry in Low Dimensions (Abstract). 3 - Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma (Abstract). 4 - Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo
, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). 5 - Marcus Schaefer:
Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). 6 - Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). 7
Session 1
- Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. 10-14 - Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi:
Non-Automatizability of Bounded-Depth Frege Proofs. 15-23 - David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
On Monotone Planar Circuits. 24-
Session 2
- Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank:
Computing from Partial Solutions. 34-45 - Ravi Kumar, D. Sivakumar:
Proofs, Codes, and Polynomial-Time Reducibilities. 46-53 - Oded Goldreich, Salil P. Vadhan:
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. 54-
Invited Speaker 1
- Avi Wigderson:
De-Randomizing BPP: The State of the Art. 76-
Session 3
- Mikael Goldmann, Alexander Russell:
The Complexity of Solving Equations over Finite Groups. 80-86 - Amir Shpilka, Avi Wigderson:
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. 87-
Session 4
- László Babai, Sophie Laplante:
Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. 98-104 - Tao Jiang, Ming Li, Paul M. B. Vitányi:
The Expected Size of Heilbronn's Triangles. 105-113 - Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". 114-
Session 5
- Richard Beigel:
Gaps in Bounded Query Hierarchies. 124-141 - Jack Jie Dai, Jack H. Lutz:
Query Order and NP-Completeness. 142-148 - Harry Buhrman, Wim van Dam:
Quantum Bounded Query Complexity. 149-
Invited Speaker 2
- Jin-yi Cai:
Some Recent Progress on the Complexity of Lattice Problems. 158-
Session 6
- John Watrous:
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. 180-187 - Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson:
Deterministic Amplification of Space-Bounded Probabilistic Algorithms. 188-
Session 7
- Ravi Kumar, D. Sivakumar:
A Note on the Shortest Lattice Vector Problem. 200-204 - Jin-yi Cai:
Applications of a New Transference Theorem to Ajtai's Connection Factor. 205-214 - Jun Tarui, Tatsuie Tsukiji:
Learning DNF by Approximating Inclusion-Exclusion Formulae. 215-
Session 8
- Richard Beigel, Alexis Maciel:
Circuit Lower Bounds Collapse Relativized Complexity Classes. 222-226 - Harry Buhrman, Leen Torenvliet:
Complicated Complementations. 227-236 - Russell Impagliazzo, Ramamohan Paturi:
Complexity of k-SAT. 237-240
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 2025-11-16 23:38 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:
