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. |
CCC |
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 |
CCC |
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. |
CCC |
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. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel |
Streaming Computation of Combinatorial Objects. |
CCC |
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. |
CCC |
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. |
CCC |
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. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
low-degree extension, hardness vs. randomness tradeoffs, pseudo-random generator |
1 | D. Sivakumar |
Algorithmic Derandomization via Complexity Theory. |
CCC |
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. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Jonas Holmerin |
Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Uriel Feige |
Relations between Average Case Complexity and Approximation Complexity. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
random 3sat, bipartite clique, bisection |
1 | Richard Chang 0001, Jon S. Squire |
Bounded Query Functions with Limited Output Bits. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Albert Atserias, Nicola Galesi, Pavel Pudlák |
Monotone Simulations of Nonmonotone Proofs. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, David A. Mix Barrington, William Hesse |
Uniform Circuits for Division: Consequences and Problems. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Yuval Ishai |
On the Power of Nonlinear Secrect-Sharing. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Larry J. Stockmeyer, Dharmendra S. Modha |
Links Between Complexity Theory and Constrained Block Coding. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Andrei A. Muchnik, Nikolai K. Vereshchagin |
Logical Operations and Kolmogorov Complexity II. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Ronald de Wolf |
Communication Complexity Lower Bounds by Polynomials. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Santhanam |
On Separators, Segregators and Time versus Space. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann 0001, Frank Stephan 0001 |
Hausdorff Dimension in Exponential Time. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Jack Jie Dai |
A Stronger Kolmogorov Zero-One Law for Resource-Bounded Measure. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Manindra Agrawal |
Towards Uniform AC0 - Isomorphisms. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Elchanan Mossel, Christopher Umans |
On the Complexity of Approximating the VC Dimension. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Aduri Pavan, Alan L. Selman |
Separation of NP-Completeness Notions. |
CCC |
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. |
CCC |
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. |
CCC |
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 |
CCC |
2001 |
DBLP BibTeX RDF |
|
1 | Amir Shpilka |
Affine Projections of Symmetric Polynomials. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Nicola Galesi |
Space Complexity of Random Formulae in Resolution. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Rocco A. Servedio, Steven J. Gortler |
Quantum versus Classical Learnability. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow |
Comparing Notions of Full Derandomization. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Jürgen Forster |
A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Russell Impagliazzo, Ashish Sabharwal |
Resolution Complexity of Independent Sets in Random Graphs. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Luis Antunes 0002, Lance Fortnow, Dieter van Melkebeek |
Computational Depth. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
Time-Space Tradeoffs in the Counting Hierarchy. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Stefan S. Dantchev, Søren Riis |
Tree Resolution Proofs of the Weak Pigeon-Hole Principle. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Johan Håstad, Avi Wigderson |
Simple Analysis of Graph Tests for Linearity and PCP. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
graph test, pseudorandomness, PCP, Linearity testing, iterated test |
1 | Péter Gács |
Quantum Algorithmic Entropy. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Ronen Shaltiel |
Towards Proving Strong Direct Product Theorems. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Richard Beigel |
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Michal Koucký 0001 |
Universal Traversal Sequences with Backtracking. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
1 | Iannis Tourlakis |
Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Oliver Kullmann |
An Application of Matroid Theory to the SAT Problem. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Pavol Duris, Juraj Hromkovic, Katsushi Inoue |
A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
Las Vegas randomization, two-dimensional finite automata, nondeterminism |
1 | Jack H. Lutz |
Dimension in Complexity Classes. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Sanjeev Khanna |
On the Hardness of 4-Coloring a 3-Colorable Graph. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
Graph Coloring, Hardness of approximation, PCP |
1 | Gabriel Istrate |
Computational Complexity and Phase Transitions. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
Combinatorial Interpretation of Kolmogorov Complexity. |
CCC |
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. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Nikolai K. Vereshchagin, Michael V. Vyugin |
Independent Minimum Length Programs to Translate between Given Strings. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Sophie Laplante, Peter Bro Miltersen |
New Bounds for the Language Compression Problem. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Frederic Green, Steven Homer, Chris Pollett |
On the Complexity of Quantum ACC. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Marcus Schaefer 0001 |
Deciding the K-Dimension is PSPACE-Complete. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
computational complexity, learning theory, PSPACE |
1 | Ronald de Wolf |
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. |
CCC |
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. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
data compression, information theory, quantum computation, Kolmogorov complexity, quantum information theory |
1 | Oliver Giel |
BP(L(f)1+epsilon). |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Dieter van Melkebeek |
Time-Space Tradeoffs for Nondeterministic Computation. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
Satisfiability, Time-space tradeoffs |
1 | Ketan Mulmuley, Pradyut Shah |
A Lower Bound for the Shortest Path Problem. |
CCC |
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 |
CCC |
2000 |
DBLP BibTeX RDF |
|
1 | Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet |
The Communication Complexity of Enumeration, Elimination, and Selection. |
CCC |
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. |
CCC |
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. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan |
A Survey of Optimal PCP Characterizations of NP. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andrei A. Voronenko |
On the Complexity of the Monotonicity Verification. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | George Karakostas, Richard J. Lipton, Anastasios Viglas |
On the Complexity of Intersecting Finite State Automata. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Thanh Minh Hoang, Thomas Thierauf |
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. |
CCC |
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. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
logic, circuit complexity, group membership, integer arithmetic |
1 | Ke Yang |
Integer Circuit Evaluation is PSPACE-Complete. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
Integer Circuit, Chinese Remainder Theorem, PSPACE |
1 | Richard Cleve |
The Query Complexity of Order-Finding. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Andreas Jakoby, Rüdiger Reischuk |
Average Case Complexity of Unbounded Fanin Circuits. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
|
1 | Valentine Kabanets |
Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. |
CCC |
2000 |
DBLP DOI BibTeX RDF |
probabilistic complexity classes, uniform setting, derandomization |
1 | Marcus Schaefer 0001 |
Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Jack Jie Dai, Jack H. Lutz |
Query Order and NP-Completeness. |
CCC |
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. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Tao Jiang 0001, Ming Li 0001, Paul M. B. Vitányi |
The Expected Size of Heilbronn's Triangles. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Ziv Bar-Yossef, Oded Goldreich 0001, Avi Wigderson |
Deterministic Amplification of Space-Bounded Probabilistic Algorithms. |
CCC |
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. |
CCC |
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. |
CCC |
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. |
CCC |
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. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Mikael Goldmann, Alexander Russell |
The Complexity of Solving Equations over Finite Groups. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Ravi Kumar 0001, D. Sivakumar 0001 |
Proofs, Codes, and Polynomial-Time Reducibilities. |
CCC |
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). |
CCC |
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. |
CCC |
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. |
CCC |
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. |
CCC |
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. |
CCC |
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). |
CCC |
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. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
shortest lattice vector, NP-completness, uniqueness |
1 | Richard Beigel, Alexis Maciel |
Circuit Lower Bounds Collapse Relativized Complexity Classes. |
CCC |
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. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Avi Wigderson |
Short Proofs Are Narrow - Resolution Made Simple (Abstract). |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Generators without the XOR Lemma (Abstract). |
CCC |
1999 |
DBLP DOI BibTeX RDF |
polynomial reconstruct ion, Pseudorandom generators, extractors, list-decoding |
1 | Harry Buhrman, Wim van Dam |
Quantum Bounded Query Complexity. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
query limited reductions, quantum computation, structural complexity |
1 | Avi Wigderson |
De-Randomizing BPP: The State of the Art. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
|
1 | Richard Beigel |
Gaps in Bounded Query Hierarchies. |
CCC |
1999 |
DBLP DOI BibTeX RDF |
complexity, separation, collapse, bounded queries |
1 | Russell Impagliazzo, Ramamohan Paturi |
Complexity of k-SAT. |
CCC |
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 |
CCC |
1999 |
DBLP BibTeX RDF |
|