Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
Randomness Conductors and Constant-Degree Lossless Expanders. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 15, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
expander graphs, extractors, condensers, graph products |
1 | |
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 0-7695-1468-5 The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP BibTeX RDF |
|
1 | Amit Deshpande 0001, Rahul Jain 0001, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam |
Better Lower Bounds for Locally Decodable Codes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 184-193, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
Second Moment Method, Probabilistically Checkable Proof Systems, Error Correcting Codes, Pseudorandom Generators, Private Information Retrieval |
1 | John Watrous |
Arthur and Merlin in a Quantum World. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 161, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel |
Streaming Computation of Combinatorial Objects. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 165-174, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
error-correcting codes, extractors, dispersers, streaming computation, universal hash functions, online computation |
1 | Ian Agol, Joel Hass, William P. Thurston |
3-MANIFOLD KNOT GENUS is NP-complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 24, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
2-prover games, Hardness of approximation, probabilistically checkable proofs |
1 | Daniele Micciancio |
Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 9, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
worst-case/average-case connection, computational complexity, cryptography, hash functions, lattices |
1 | Christopher Umans |
Pseudo-Random Generators for All Hardnesses. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 11, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
low-degree extension, hardness vs. randomness tradeoffs, pseudo-random generator |
1 | D. Sivakumar |
Algorithmic Derandomization via Complexity Theory. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 10, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
Johnson-Lindenstrauss Lemma, Derandomization, randomized rounding |
1 | Paul Beame, Erik Vee |
Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 18, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Jonas Holmerin |
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 6, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Uriel Feige |
Relations between Average Case Complexity and Approximation Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, pp. 5, 2002, IEEE Computer Society, 0-7695-1468-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
random 3sat, bipartite clique, bisection |
1 | Richard Chang 0001, Jon S. Squire |
Bounded Query Functions with Limited Output Bits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 90-98, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Albert Atserias, Nicola Galesi, Pavel Pudlák |
Monotone Simulations of Nonmonotone Proofs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 36-41, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, David A. Mix Barrington, William Hesse |
Uniform Circuits for Division: Consequences and Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 150-159, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Yuval Ishai |
On the Power of Nonlinear Secrect-Sharing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 188-202, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Larry J. Stockmeyer, Dharmendra S. Modha |
Links Between Complexity Theory and Constrained Block Coding. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 226-243, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
Logical Operations and Kolmogorov Complexity II. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 256-265, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Ronald de Wolf |
Communication Complexity Lower Bounds by Polynomials. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 120-130, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Santhanam |
On Separators, Segregators and Time versus Space. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 286-294, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann 0001, Frank Stephan 0001 |
Hausdorff Dimension in Exponential Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 210-217, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Jack Jie Dai |
A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 204-209, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Manindra Agrawal |
Towards Uniform AC0 - Isomorphisms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 13-20, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Elchanan Mossel, Christopher Umans |
On the Complexity of Approximating the VC Dimension. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 220-225, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Aduri Pavan, Alan L. Selman |
Separation of NP-Completeness Notions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 78-89, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, Ronald de Wolf |
Quantum Algorithms for Element Distinctness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 131-137, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Beate Bollig, Martin Sauerhoff, Ingo Wegener |
On the Non-Approximability of Boolean Functions by OBDDs and Read-K-Times Branching Programs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 172-183, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
Computational complexity, lower bounds, approximations, binary decision diagrams, branching programs |
1 | |
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 0-7695-1053-1 The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP BibTeX RDF |
|
1 | Amir Shpilka |
Affine Projections of Symmetric Polynomials. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 160-171, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Nicola Galesi |
Space Complexity of Random Formulae in Resolution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 42-51, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Rocco A. Servedio, Steven J. Gortler |
Quantum versus Classical Learnability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 138-148, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow |
Comparing Notions of Full Derandomization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 28-34, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Jürgen Forster |
A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 100-106, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Russell Impagliazzo, Ashish Sabharwal |
Resolution Complexity of Independent Sets in Random Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 52-68, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Luis Antunes 0002, Lance Fortnow, Dieter van Melkebeek |
Computational Depth. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 266-273, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
Time-Space Tradeoffs in the Counting Hierarchy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 295-302, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Stefan S. Dantchev, Søren Riis |
Tree Resolution Proofs of the Weak Pigeon-Hole Principle. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 69-75, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Johan Håstad, Avi Wigderson |
Simple Analysis of Graph Tests for Linearity and PCP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 244-254, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
graph test, pseudorandomness, PCP, Linearity testing, iterated test |
1 | Péter Gács |
Quantum Algorithmic Entropy. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 274-283, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Ronen Shaltiel |
Towards Proving Strong Direct Product Theorems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 107-117, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Richard Beigel |
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 184-187, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Michal Koucký 0001 |
Universal Traversal Sequences with Backtracking. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 21-27, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 2-12, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Iannis Tourlakis |
Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 22-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Oliver Kullmann |
An Application of Matroid Theory to the SAT Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 116-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Pavol Duris, Juraj Hromkovic, Katsushi Inoue |
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 214-228, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Las Vegas randomization, two-dimensional finite automata, nondeterminism |
1 | Jack H. Lutz |
Dimension in Complexity Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 158-169, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Sanjeev Khanna |
On the Hardness of 4-Coloring a 3-Colorable Graph. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 188-197, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Graph Coloring, Hardness of approximation, PCP |
1 | Gabriel Istrate |
Computational Complexity and Phase Transitions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 104-115, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Combinatorial Interpretation of Kolmogorov Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 131-137, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
algorithmic information theory, combinatorial inequalities, Kolmogorov complexity |
1 | Carsten Damm, Markus Holzer 0001, Pierre McKenzie |
The Complexity of Tensor Calculus. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 70-86, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Nikolai K. Vereshchagin, Michael V. Vyugin |
Independent Minimum Length Programs to Translate between Given Strings. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 138-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Sophie Laplante, Peter Bro Miltersen |
New Bounds for the Language Compression Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 126-130, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Frederic Green, Steven Homer, Chris Pollett |
On the Complexity of Quantum ACC. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 250-262, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Marcus Schaefer 0001 |
Deciding the K-Dimension is PSPACE-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 198-203, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
computational complexity, learning theory, PSPACE |
1 | Ronald de Wolf |
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 271-278, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
non-deterministic computation, Quantum computing, communication complexity, query complexity |
1 | André Berthiaume, Wim van Dam, Sophie Laplante |
Quantum Kolmogorov Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 240-249, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
data compression, information theory, quantum computation, Kolmogorov complexity, quantum information theory |
1 | Oliver Giel |
BP(L(f)1+epsilon). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 36-43, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Dieter van Melkebeek |
Time-Space Tradeoffs for Nondeterministic Computation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 2-13, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Satisfiability, Time-space tradeoffs |
1 | Ketan Mulmuley, Pradyut Shah |
A Lower Bound for the Shortest Path Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 14-21, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
parallel, lower bound, shortest path problem |
1 | |
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 0-7695-0674-7 The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP BibTeX RDF |
|
1 | Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet |
The Communication Complexity of Enumeration, Elimination, and Selection. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 44-53, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Jeff Kahn 0001, Michael E. Saks, Cliff Smyth 0001 |
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 98-103, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Reimer's inequality, van den Berg-Kesten conjecture, Rudich's conjecture |
1 | Paul M. B. Vitányi |
Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 263-270, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan |
A Survey of Optimal PCP Characterizations of NP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 146-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andrei A. Voronenko |
On the Complexity of the Monotonicity Verification. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 235-238, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | George Karakostas, Richard J. Lipton, Anastasios Viglas |
On the Complexity of Intersecting Finite State Automata. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 229-234, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Thanh Minh Hoang, Thomas Thierauf |
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 87-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie |
On the Complexity of Some Problems on Groups Input as Multiplication Tables. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 62-69, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
logic, circuit complexity, group membership, integer arithmetic |
1 | Ke Yang |
Integer Circuit Evaluation is PSPACE-Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 204-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
Integer Circuit, Chinese Remainder Theorem, PSPACE |
1 | Richard Cleve |
The Query Complexity of Order-Finding. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 54-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Jakoby, Rüdiger Reischuk |
Average Case Complexity of Unbounded Fanin Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 170-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Valentine Kabanets |
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 150-157, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
probabilistic complexity classes, uniform setting, derandomization |
1 | Marcus Schaefer 0001 |
Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 6, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Jack Jie Dai, Jack H. Lutz |
Query Order and NP-Completeness. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 142-148, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
query order, resource-bounded genericity, computational complexity, NP-completeness, complexity classes, resource-bounded measure |
1 | Jin-yi Cai |
Some Recent Progress on the Complexity of Lattice Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 158-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Tao Jiang 0001, Ming Li 0001, Paul M. B. Vitányi |
The Expected Size of Heilbronn's Triangles. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 105-113, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Ziv Bar-Yossef, Oded Goldreich 0001, Avi Wigderson |
Deterministic Amplification of Space-Bounded Probabilistic Algorithms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 188-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
space bounded randomized computation, deterministic amplification, expander graphs |
1 | Eric Allender, Michael E. Saks, Igor E. Shparlinski |
A Lower Bound for Primality. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 10-14, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Circuit Complexity Lower Bounds, Primality, Square-Free Numbers, GCD |
1 | Jin-yi Cai |
Applications of a New Transference Theorem to Ajtai's Connection Factor. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 205-214, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Transference theorems, Lattices, Public-key cryptosystem, Average-case complexity, Harmonic analysis, Shortest vector problem |
1 | Harry Buhrman, Leen Torenvliet |
Complicated Complementations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 227-236, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Oracles, Kolmogorov Complexity, Complexity Classes, Simplicity, Polynomial Hierarchy, Immunity |
1 | David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum |
On Monotone Planar Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 24-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Mikael Goldmann, Alexander Russell |
The Complexity of Solving Equations over Finite Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 80-86, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Ravi Kumar 0001, D. Sivakumar 0001 |
Proofs, Codes, and Polynomial-Time Reducibilities. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 46-53, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
reducibilities, proof systems, partial solutions |
1 | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 5, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
counting principles, graph tautologies, algebraic proof systems, binomial proofs, Nullstellensatz proofs, polynomial calculus proofs, propositional logic, Proof complexity |
1 | John Watrous |
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 180-187, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
quantum computation, graph connectivity, space-bounded computation |
1 | Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank |
Computing from Partial Solutions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 34-45, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Robust proofs, erasure correction, erasure-resilient reductions, fault tolerant computations, NP-Hardness |
1 | Oded Goldreich 0001, Salil P. Vadhan |
Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 54-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
Statistical Zero-Knowledge Proofs, Universal Hashing, Arthur-Merlin Games |
1 | László Babai, Sophie Laplante |
Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 98-104, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh 0001 |
The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 7, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
pointer chasing, entropy, Communication complexity |
1 | Ravi Kumar 0001, D. Sivakumar 0001 |
A Note on the Shortest Lattice Vector Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 200-204, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
shortest lattice vector, NP-completness, uniqueness |
1 | Richard Beigel, Alexis Maciel |
Circuit Lower Bounds Collapse Relativized Complexity Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 222-226, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
relativized computation, Booleand circuits, oracles, complexity theory |
1 | Amir Shpilka, Avi Wigderson |
Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 87-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Avi Wigderson |
Short Proofs Are Narrow - Resolution Made Simple (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 2, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Generators without the XOR Lemma (Abstract). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 4, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
polynomial reconstruct ion, Pseudorandom generators, extractors, list-decoding |
1 | Harry Buhrman, Wim van Dam |
Quantum Bounded Query Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 149-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
query limited reductions, quantum computation, structural complexity |
1 | Avi Wigderson |
De-Randomizing BPP: The State of the Art. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 76-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Richard Beigel |
Gaps in Bounded Query Hierarchies. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 124-141, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
complexity, separation, collapse, bounded queries |
1 | Russell Impagliazzo, Ramamohan Paturi |
Complexity of k-SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 237-240, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
NP-completeness, Satisfiability, Reductions, Complexity Theory |
1 | |
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 0-7695-0075-7 The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP BibTeX RDF |
|