| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan 0001 |
New Results on Noncommutative and Commutative Polynomial Identity Testing.  |
CCC  |
2008 |
DBLP DOI BibTeX RDF |
randomized, polynomial time, deterministic, polynomial identity testing |
| 1 | Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick |
Using Entanglement in Quantum Multi-prover Interactive Proofs. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
quantum interactive proofs, public-coin, parallelization, entanglement |
| 1 | Robert Spalek |
The Multiplicative Quantum Adversary. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
quantum query lower bounds, quantum adversary method, multiplicative adversary, combinatorial matrices, direct product theorems |
| 1 | Kristoffer Arnsfelt Hansen |
Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Constant Width, Circuits, Planarity, Branching Programs |
| 1 | Troy Lee, Adi Shraibman, Robert Spalek |
A Direct Product Theorem for Discrepancy. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
direct sum theorems, factorization norms, communication complexity, discrepancy, direct product theorems |
| 1 | Venkatesan Guruswami, Atri Rudra |
Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nathan Segerlind |
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
lower bounds, resolution, ordered binary decision diagrams, propositional proof complexity |
| 1 | Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor |
The Power of Unentanglement. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement |
| 1 | Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma |
Quantum Expanders: Motivation and Constructions. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Quantum Expanders, Quantum Statistical Zero-Knowledge |
| 1 | Eric Allender, Michal Koucký 0001 |
Amplifying Lower Bounds by Means of Self-Reducibility. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
self-reducibility, lower bounds, circuit complexity |
| 1 | Zeev Dvir, Amir Shpilka |
Noisy Interpolating Sets for Low Degree Polynomials. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Error correcting codes, Polynomial interpolation |
| 1 | Zohar Shay Karnin, Amir Shpilka |
Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
PIT, depth-3, arithmetic circuit, deterministic, polynomial identity testing |
| 1 | Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf |
On Computation and Communication with Small Bias. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Bourke, Raghunath Tewari, N. V. Vinodchandran |
Directed Planar Reachability is in Unambiguous Log-Space. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan |
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
error-correcting codes, expander graphs, condensers, list decoding, randomness extractors |
| 1 | Yijia Chen, Jörg Flum |
On Parameterized Path and Chordless Path Problems. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay |
Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Luis Antunes 0002, Lance Fortnow, Alexandre Pinto, Andre Souto |
Low-Depth Witnesses are Easy to Find. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Chang 0001, Suresh Purini |
Bounded Queries and the NP Machine Hypothesis. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Greg Kuperberg |
Quantum versus Classical Proofs and Advice. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | |
22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA |
CCC |
2007 |
DBLP BibTeX RDF |
|
| 1 | Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur |
Testing Properties of Constraint-Graphs. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Halfspace Matrices. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Pervyshev |
On Heuristic Time Hierarchies. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Wolfgang Merkle, Frank Stephan 0001 |
On C-Degrees, H-Degrees and T-Degrees. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
On Approximate Majority and Probabilistic Time. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Williams 0001 |
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Vinay Choudhary, Pinyan Lu |
On the Theory of Matchgate Computations. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Marius Zimand |
On Derandomizing Probabilistic Sublinear-Time Algorithms. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Kei Uchizawa, Eiji Takimoto |
An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Raghav Kulkarni, Sambuddha Roy |
Parity Problems in Planar Graphs. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Prahladh Harsha, Rahul Jain 0001, David A. McAllester, Jaikumar Radhakrishnan |
The Communication Complexity of Correlation. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Peikert |
Limits on the Hardness of Lattice Problems in ell _p Norms. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Kai-Min Chung, Omer Reingold, Salil P. Vadhan |
S-T Connectivity on Digraphs with a Known Stationary Distribution. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Guillaume Malod |
The Complexity of Polynomials and Their Coefficient Functions. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky |
Efficient Arguments without Short PCPs. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Omer Reingold |
A New Interactive Hashing Theorem. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Joseph Emerson |
Quantum t-designs: t-wise Independence in the Quantum World. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti |
Lower Bounds for Multi-Player Pointer Jumping. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Pinyan Lu |
Bases Collapse in Holographic Algorithms. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Guy Kindler, Ryan O'Donnell |
Understanding Parallel Repetition Requires Understanding Foams. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. |
CCC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel |
How to Get More Mileage from Randomness Extractors. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Committees. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Calabro, Russell Impagliazzo, Ramamohan Paturi |
A Duality between Clause Width and Clause Density for SAT. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Rocco A. Servedio |
Every Linear Threshold Function has a Low-Weight Approximator. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Kristoffer Arnsfelt Hansen |
On Modular Counting with Polynomials. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky, Julia Kempe, Ronald de Wolf |
Strengths and Weaknesses of Quantum Fingerprinting. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Dieter van Melkebeek, Konstantin Pervyshev |
A Generic Time Hierarchy for Semantic Models with One Bit of Advice. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Atserias |
Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Subhash Khot, Rishi Saket |
A 3-Query Non-Adaptive PCP with Perfect Completeness. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafael Pass |
Parallel Repetition of Zero-Knowledge Proofs and the Possibility of Basing Cryptography on NP-Hardness. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman |
Optimal Hardness Results for Maximizing Agreements with Monomials. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson |
Applications of the Sum-Product Theorem in Finite Fields. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Preface. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | H. Venkateswaran |
Derandomization of Probabilistic Auxiliary Pushdown Automata Classes. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Marius Zimand |
Exposure-Resilient Extractors. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranab Sen |
Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty 0001, Samir Datta, Sambuddha Roy |
Grid Graph Reachability Problems. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan |
Constructing Ramsey Graphs from Boolean Function Representations. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka |
Constructions of Low-Degree and Error-Correcting in-Biased Generators. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Yijia Chen, Martin Grohe |
An Isomorphism between Subexponential and Parameterized Complexity Theory. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Reviewers. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Buresh-Oppenheim, Rahul Santhanam |
Making Hard Problems Harder. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Rocco A. Servedio |
Learning Monotone Decision Trees in Polynomial Time. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson |
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Iannis Tourlakis |
New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal, Nitin Saxena 0001 |
Polynomial Identity Testing for Depth 3 Circuits. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson |
Oracles Are Subtle But Not Malicious. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Christoph Behle, Klaus-Jörn Lange |
FO[<]-Uniformity. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | |
21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic |
CCC |
2006 |
DBLP BibTeX RDF |
|
| 1 | Pavel Pudlák |
Godel and Computations (Abstract). |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Michal Koucký 0001, Clemens Lautemann, Sebastian Poloczek, Denis Thérien |
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishay Haviv, Oded Regev 0001 |
Hardness of the Covering Radius Problem on Lattices. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Awards. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks |
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. |
CCC |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Williams 0001 |
Better Time-Space Lower Bounds for SAT and Related Problems. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | |
20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA |
CCC |
2005 |
DBLP BibTeX RDF |
|
| 1 | Neeraj Kayal, Nitin Saxena 0001 |
On the Ring Isomorphism and Automorphism Problems. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Jain 0001, Jaikumar Radhakrishnan, Pranab Sen |
Prior Entanglement, Message Compression and Privacy in Quantum Communication. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Lance Fortnow |
Tolerant Versus Intolerant Testing for Boolean Properties. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Committees. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel, Christopher Umans |
Pseudorandomness for Approximate Counting and Sampling. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Samir Datta, Sambuddha Roy |
Topology Inside NC¹. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Ingo Wegener, Philipp Woelfel |
New Results on the Complexity of the Middle Bit of Multiplication. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Arfst Nickelsen, Birgit Schelm |
Average-Case Computations - Comparing AvgP, HP, and Nearly-P. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi |
Toward a Model for Backtracking and Dynamic Programming. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
On Constructing Parallel Pseudorandom Generators from One-Way Functions. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
Pseudorandom generator construction, one-way function, black-box, restriction, constant-depth circuit, noise sensitivity, hardness amplification |
| 1 | Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson |
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Woodruff, Sergey Yekhanin |
A Geometric Approach to Information-Theoretic Private Information Retrieval. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi |
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Sophie Laplante, Troy Lee, Mario Szegedy |
The Quantum Adversary Method and Classical Formula Size Lower Bounds. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Awards. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
On the Complexity of Succinct Zero-Sum Games. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Preface. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Thanh Minh Hoang, Thomas Thierauf |
The Complexity of the Inertia and Some Closure Properties of GapL. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Gus Gutoski |
Upper Bounds for Quantum Interactive Proofs with Competing Provers. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Hoeteck Wee |
More on Noncommutative Polynomial Identity Testing. |
CCC |
2005 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license