Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Sourav Chakraborty 0001 |
On the Sensitivity of Cyclically-Invariant Boolean Functions. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Bill Rosgen |
On the Hardness of Distinguishing Mixed-State Quantum Computations. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Enav Weinreb |
Monotone Circuits for Weighted Threshold Functions. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan |
Short PCPs Verifiable in Polylogarithmic Time. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Subhash Khot |
Hardness of Max 3SAT with No Mixed Clauses. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan |
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
Computationally Private Randomizing Polynomials and Their Applications. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma |
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Adam R. Klivans |
NP with Small Advice. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Emanuele Viola |
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
On the Complexity of Hardness Amplification. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Shuchi Chawla 0001, Robert Krauthgamer, Ravi Kumar 0001, Yuval Rabani, D. Sivakumar 0001 |
On the Hardness of Approximating Multicut and Sparsest-Cut. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
1 | Josh Buresh-Oppenheim, Tsuyoshi Morioka |
Relativized NP Search Problems and Propositional Proof Systems. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson |
Limitations of Quantum Advice and One-Way Communication. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Andrej Bogdanov, Luca Trevisan |
Lower Bounds for Testing Bipartiteness in Dense Graphs. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton |
Polynomials That Sign Represent Parity and Descartes Rule of Signs. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | |
19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA |
CCC |
2004 |
DBLP BibTeX RDF |
|
1 | Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig |
Multiparty Quantum Coin Flipping. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Klaus-Jörn Lange |
Some Results on Majority Quantifiers over Words. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Hoeteck Wee |
On Pseudoentropy versus Compressibility. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Nicola Galesi, Neil Thapen |
The Complexity of Treelike Systems over lamda-Local Formulae. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Chris Marriott, John Watrous |
Quantum Arthur-Merlin Games. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Vikraman Arvind, Jacobo Torán |
Solvable Group Isomorphism. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | John M. Hitchcock, N. V. Vinodchandran |
Dimension, Entropy Rates, and Compression. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | John M. Hitchcock |
Small Spans in Scaled Dimension. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Sophie Laplante, Frédéric Magniez |
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia |
Tight Lower Bounds for Certain Parameterized NP-Hard Problems. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Xiaoming Sun 0001, Andrew Chi-Chih Yao, Shengyu Zhang |
Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Andris Ambainis, Ke Yang 0005 |
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Alan L. Selman, Samik Sengupta |
Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Ilan Newman |
Computing in Fault Tolerance Broadcast Networks. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta |
Properties of NP-Complete Sets. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Dániel Marx |
Parameterized Complexity of Constraint Satisfaction Problems. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Troy Lee, Dieter van Melkebeek |
Language Compression and Pseudorandom Generators. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Leen Torenvliet |
Separating Complexity Classes Using Structural Properties. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Ran Raz, Amir Shpilka |
Deterministic Polynomial Identity Testing in Non-Commutative Models. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Ran Raz, Amir Shpilka |
On the Power of Quantum Proofs. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous |
Consequences and Limits of Nonlocal Strategies. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Daniele Micciancio, Oded Regev 0001 |
The Complexity of the Covering Radius Problem on Lattices and Codes. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Vikraman Arvind, T. C. Vijayaraghavan |
Abelian Permutation Group Problems and Logspace Counting Classes. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan, Salil P. Vadhan, David Zuckerman |
Compression of Samplable Sources. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Christian Glaßer, Alan L. Selman, Samik Sengupta |
Reductions between Disjoint NP-Pairs. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
Partial Bi-immunity and NP-Completeness. |
CCC |
2004 |
DBLP DOI BibTeX RDF |
|
1 | Manindra Agrawal |
On Derandomizing Tests for Certain Polynomial Identities. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Emanuele Viola |
Hardness vs. Randomness within Alternating Time. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Navin Goyal, Michael E. Saks, Srinivasan Venkatesh 0001 |
Optimal Separation of EROW and CROWPRAMs. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Howard Barnum, Michael E. Saks, Mario Szegedy |
Quantum query complexity and semi-definite programming. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi |
The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Richard Beigel, Lance Fortnow |
Are Cook and Karp Ever the Same? |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang |
Disjoint NP-Pairs. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami |
List Decoding with Side Information. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Andrei E. Romashchenko |
Extracting the Mutual Information for a Triple of Binary Strings. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Wolfgang Merkle |
The complexity of stochastic sequences. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Ke Yang, Avrim Blum |
On Statistical Query Sampling and NMR Quantum Computing. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Albert Atserias, Víctor Dalmau |
A Combinatorial Characterization of Resolution Width. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Oded Regev 0001 |
Improved Inapproximability of Lattice and Coding Problems with Preprocessing. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Yijia Chen, Jörg Flum, Martin Grohe |
Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Johan Håstad |
Inapproximability Some history and some open problems. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | |
18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark |
CCC |
2003 |
DBLP BibTeX RDF |
|
1 | Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma |
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind |
Memoization and DPLL: Formula Caching Proof Systems. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Russell Impagliazzo, Philippe Moser |
A zero one law for RP. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Aduri Pavan, Samik Sengupta |
Proving SAT does not have Small Circuits with an Application to the Two. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell, Rocco A. Servedio |
Extremal properties of polynomial threshold functions. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel |
Universal Languages and the Power of Diagonalization. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Santhanam, Dieter van Melkebeek |
Holographic Proofs and Derandomization. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Amit Chakrabarti, Subhash Khot, Xiaodong Sun |
Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Hartmut Klauck |
Rectangle Size Bounds and Threshold Covers in Communication Complexity. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Pranab Sen |
Lower bounds for predecessor searching in the cell probe model. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy |
Derandomization and Distinguishing Complexity. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Detlef Sieling |
Minimization of Decision Trees Is Hard to Approximate. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Subhash Khot, Oded Regev 0001 |
Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Jonas Holmerin, Subhash Khot |
A Strong Inapproximability Gap for a Generalization of Minimum Bisection. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson |
Quantum Certificate Complexity. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Lars Engebretsen, Jonas Holmerin |
Three-Query PCPs with Perfect Completeness over non-Boolean Domains. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell |
Hardness Amplification within NP. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Frederic Green |
The Correlation Between Parity and Quadratic Polynomials Mod 3. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson |
Hard Examples for Bounded Depth Frege. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Uriel Feige, Daniele Micciancio |
The Inapproximability of Lattice and Coding Problems with Preprocessing. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Miklós Ajtai, Ravi Kumar 0001, D. Sivakumar 0001 |
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
SVP, CVP, Lattice, shortest vector problem, closest vector problem |
1 | Manindra Agrawal |
Pseudo-Random Generators and Structure of Complete Degrees. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Completeness, Reductions, Pseudo-random Generators |
1 | Peter Winkler 0001 |
Rapid Mixing. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Madhu Sudan 0001 |
Decoding Concatenated Codes using Soft Information. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Ashwin Nayak 0001, Julia Salzman |
On Communication over an Entanglement-Assisted Quantum Channel. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Alexander A. Razborov |
Resolution Lower Bounds for Perfect Matching Principles. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Matching Principles, Resolution, Proof Complexity, Pigeonhole principle |
1 | Subhash Khot |
On the Power of Unique 2-Prover 1-Round Games. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
2-prover games, Hardness of approximation, probabilistically checkable proofs |
1 | Eldar Fischer, Ilan Newman |
Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Philipp Woelfel |
On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Lower Bounds, BDDs, Nondeterminism, Branching Programs, Integer Multiplication |
1 | Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar 0001, Ronitt Rubinfeld |
The Complexity of Approximating the Entropy. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
entropy approximation, black-box distribution, monotone distribution, entropy, sample complexity |
1 | Roy Meshulam, Avi Wigderson |
Expanders from Symmetric Codes. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Oded Goldreich 0001, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan |
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Error Correcting Codes, Linear Codes, Private Information Retrieval |
1 | Ran Raz |
Resolution Lower Bounds for the Weak Pigeonhole Principle. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar 0001, D. Sivakumar 0001 |
Information Theory Methods in Communication Complexity. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Fano's inequality, Maximum Likelihood Estimate Principle, Information Theory, Communication complexity |
1 | Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
Learnability beyond AC0. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow |
The History of Complexity. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Computational Complexity, History of Computing |
1 | Andris Ambainis, Adam D. Smith, Ke Yang 0005 |
Extracting Quantum Entanglement. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Entanglement Purification, General Error Models, Purity-Testing, Quantum Cryptography |
1 | Markus Bläser |
Algebras of Minimal Rank over Perfect Fields. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
algebras of minimal rank, multiplication, bilinear complexity |
1 | Luca Trevisan, Salil P. Vadhan |
Pseudorandomness and Average-Case Complexity via Uniform Reductions. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
|
1 | Boaz Barak, Oded Goldreich 0001 |
Universal Arguments and their Applications. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Probabilistic proof systems, computationally-sound proof systems, zero-knowledge proof systems, probabilistic checkable proofs (PCP), collision-free hashing, witness indistinguishable proof systems, error-correcting codes, proofs of knowledge |
1 | Stefan S. Dantchev |
Resolution Width-Size Trade-offs for the Pigeon-Hole Principle. |
CCC |
2002 |
DBLP DOI BibTeX RDF |
Pigeon-Hole Principle, Width-Size trade-off, Resolution, Propositional Proof Complexity |