Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Neeraj Kayal, Chandan Saha 0001 |
On the Sum of Square Roots of Polynomials and Related Problems. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Shachar Lovett, Emanuele Viola |
Bounded-Depth Circuits Cannot Sample Good Codes. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Watson 0001 |
Pseudorandom Generators for Combinatorial Checkerboards. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
A New Approach to Affine Extractors and Dispersers. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami |
Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Yuichi Yoshida |
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan 0001 |
Symmetric LDPC Codes are not Necessarily Locally Testable. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Arkadev Chattopadhyay, Shachar Lovett |
Linear Systems over Finite Abelian Groups. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Widad Machmouchi |
Making Branching Programs Oblivious Requires Superlogarithmic Overhead. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Andrew Drucker |
Improved Direct Product Theorems for Randomized Query Complexity. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Zohar Shay Karnin, Yuval Rabani, Amir Shpilka |
Explicit Dimension Reduction and Its Applications. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland |
Symmetry-Assisted Adversaries for Quantum State Generation. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii |
Exact Threshold Circuits. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Exact Threshold Functions, Boolean Circuits, Threshold Functions |
1 | Thanh Minh Hoang |
On the Matching Problem for Special Graph Classes. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
NC-computations, Perfect matchings, maximum matchings |
1 | Oded Regev 0001 |
The Learning with Errors Problem (Invited Survey). |
CCC |
2010 |
DBLP DOI BibTeX RDF |
learning with errors, lattice-based cryptography |
1 | Ronen Shaltiel |
Derandomized Parallel Repetition Theorems for Free Games. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Derandomization, Randomness extractors, Parallel repetition |
1 | Zeev Dvir |
On Matrix Rigidity and Locally Self-Correctable Codes. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
complexity, arithmetic circuits, matrices |
1 | Mohammad Mahmoody, David Xiao |
On the Power of Randomized Reductions and the Checkability of SAT. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Colusure, Instance Checkers, Complexity, Randomization |
1 | Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan |
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Boolean function, regularity lemma, polynomial threshold function |
1 | Parikshit Gopalan, Ryan O'Donnell, Yi Wu 0002, David Zuckerman |
Fooling Functions of Halfspaces under Product Distributions. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Pseudorandness, complexity theory, halfspace |
1 | Alexandra Kolla |
Spectral Algorithms for Unique Games. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Matei David, Periklis A. Papakonstantinou |
Trade-Off Lower Bounds for Stack Machines. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
AuxPDA, lower bound, streaming, communication complexity, stack, reversals, space bound |
1 | Dan Gutfreund, Akinori Kawachi |
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting |
1 | Luca Trevisan |
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Universal Search, Average-case Complexity |
1 | Matt DeVos, Ariel Gabizon |
Simple Affine Extractors Using Dimension Expansion. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness |
1 | Dániel Marx |
Completely Inapproximable Monotone and Antimonotone Parameterized Problems. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
parameterized comlexity, approximation, fixed-parameter tractability, inapproximability |
1 | Eric Allender, Klaus-Jörn Lange |
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation |
1 | Eric Blais, Ryan O'Donnell |
Lower Bounds for Testing Function Isomorphism. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
lower bounds, Boolean functions, property testing |
1 | Ran Raz |
Parallel Repetition of Two Prover Games (Invited Survey). |
CCC |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Derrick Stolee, Chris Bourke, N. V. Vinodchandran |
A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
acyclic digraph, logspace algorithm, planar graph, reachability |
1 | Irit Dinur, Or Meir |
Derandomized Parallel Repetition of Structured PCPs. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Low error, Direct Product Test, Derandomized Parallel Repetition, PCP, Direct Product, de-Bruijn |
1 | Subhash Khot |
On the Unique Games Conjecture (Invited Survey). |
CCC |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Jakob Nordström |
On the Relative Strength of Pebbling and Resolution. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
pebbling formula, resolution, space, trade-off, proof complexity, pebble games |
1 | Iftach Haitner, Mohammad Mahmoody, David Xiao |
A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
sampling protocols, constant-round statistically hiding commitments, black-box lower bounds, collision-resistant hash functions |
1 | Julia Kempe, Oded Regev 0001 |
No Strong Parallel Repetition with Entangled and Non-signaling Provers. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
entangled two-prover games, unique games, parallel repetition |
1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Relationless Completeness and Separations. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Completeness, Separations, Algebraic complexity |
1 | Daniel M. Kane |
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Lance Fortnow, Michal Koucký 0001, Bruno Loff |
Derandomizing from Random Strings. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Truth-table Reducibility, Kolmogorov Complexity, Derandomization |
1 | Russell Impagliazzo, Ryan Williams 0001 |
Communication Complexity with Synchronized Clocks. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
time-communication tradeoffs, lower bounds, communication complexity |
1 | Rahul Jain 0001, Hartmut Klauck |
The Partition Bound for Classical Communication Complexity and Query Complexity. |
CCC |
2010 |
DBLP DOI BibTeX RDF |
Partition Bound, Lower Bounds, Linear Programming, Communication Complexity, Query Complexity |
1 | |
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010 |
CCC |
2010 |
DBLP BibTeX RDF |
|
1 | Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan 0001, Michael Viderman |
Locally Testable Codes Require Redundant Testers. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Kristoffer Arnsfelt Hansen, Michal Koucký 0001 |
A New Characterization of ACC0 and Probabilistic CC0. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nitin Saxena 0001, C. Seshadhri 0001 |
An Almost Optimal Rank Bound for Depth-3 Identities. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Pavel Hrubes, Iddo Tzameret |
The Proof Complexity of Polynomial Identities. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Neeraj Kayal |
The Complexity of the Annihilating Polynomial. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Guy N. Rothblum, Salil P. Vadhan |
Are PCPs Inherent in Efficient Arguments? |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Adi Shraibman |
An Approximation Algorithm for Approximation Rank. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Zeev Dvir |
Extractors for Varieties. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Per Austrin, Subhash Khot, Muli Safra |
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Gideon Schechtman, Adi Shraibman |
Lower Bounds on Quantum Multiparty Communication Complexity. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Mark Braverman |
Poly-logarithmic Independence Fools AC0 Circuits. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Andrew Drucker |
Multitask Efficiencies in the Decision Tree Model. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Ronen Shaltiel |
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Zohar Shay Karnin, Amir Shpilka |
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Parikshit Gopalan, Shachar Lovett, Amir Shpilka |
On the Complexity of Boolean Functions in Different Characteristics. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Kazuyuki Amano |
k-Subgraph Isomorphism on AC0 Circuits. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Pascal Koiran, Sylvain Perifel |
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Luis Filipe Coelho Antunes, Lance Fortnow |
Worst-Case Running Times for Average-Case Algorithms. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Ilias Diakonikolas, Rocco A. Servedio |
Improved Approximation of Linear Threshold Functions. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nikos Leonardos, Michael E. Saks |
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Anup Rao 0001 |
Extractors for Low-Weight Affine Sources. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Adam R. Day |
Increasing the Gap between Descriptional Complexity and Algorithmic Probability. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto |
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009 |
CCC |
2009 |
DBLP BibTeX RDF |
|
1 | Manindra Agrawal, Osamu Watanabe 0001 |
One-Way Functions and the Berman-Hartmanis Conjecture. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson |
Quantum Copy-Protection and Quantum Money. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Rahul Santhanam, Ryan Williams 0001 |
Fixed-Polynomial Size Circuit Bounds. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | T. S. Jayram, Swastik Kopparty, Prasad Raghavendra |
On the Communication Complexity of Read-Once AC^0 Formulae. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Richard Královic |
Infinite vs. Finite Space-Bounded Randomized Computations. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran |
Every Permutation CSP of arity 3 is Approximation Resistant. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Akitoshi Kawamura |
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Jain 0001, Hartmut Klauck |
New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Jain 0001, John Watrous |
Parallel Approximation of Non-interactive Zero-sum Quantum Games. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody |
The Maximum Communication Complexity of Multi-Party Pointer Jumping. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | David Xiao |
On Basing ZK ≠ BPP on the Hardness of PAC Learning. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner |
Planar Graph Isomorphism is in Log-Space. |
CCC |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nati Linial, Adi Shraibman |
Learning Complexity vs. Communication Complexity. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
large margin classifiers, communication complexity, discrepancy, rigidity |
1 | Erik D. Demaine, Robert A. Hearn |
Constraint Logic: A Uniform Framework for Modeling Computation as Games. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
games, undecidability, hardness |
1 | Elena Grigorescu, Tali Kaufman, Madhu Sudan 0001 |
2-Transitivity Is Insufficient for Local Testability. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
error correcting codes, property testing, sublinear time algorithms |
1 | Zeev Dvir, Amir Shpilka |
Towards Dimension Expanders over Finite Fields. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Cayley graphs, expanders, explicit constructions |
1 | Troy Lee, Adi Shraibman |
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
multiparty communication complexity, disjointness, lower bounds |
1 | Emanuele Viola |
The Sum of d Small-Bias Generators Fools Polynomials of Degree d. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
|
1 | Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun 0001, Andrew Chi-Chih Yao |
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
multi-prover interactive proof systems, quantum nonlocality, Tsirelson inequality, entanglement |
1 | Parikshit Gopalan, Venkatesan Guruswami |
Hardness Amplification within NP against Deterministic Algorithms. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Hardness Amplication, Error-Correcting Codes, Derandomization, NP |
1 | Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner |
The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
quantum entanglement, nonlocal games, multi-prover interactive proof systems |
1 | Harry Buhrman, Michal Koucký 0001, Nikolai K. Vereshchagin |
Randomised Individual Communication Complexity. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
individual communication complexity, Kolmogorov complexity, rounds, randomized protocols |
1 | Alexander A. Sherstov |
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Approximate inclusion/exclusion, approximate degree of Boolean functions, linear-programming duality, Chebyshev polynomials |
1 | Kord Eickmeyer, Martin Grohe, Magdalena Grüber |
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
derandomisation, parameterized complexity, inapproximability |
1 | Richard Chang 0001, Suresh Purini |
Amplifying ZPP^SAT[1] and the Two Queries Problem. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
ZPP, amplification, bounded queries |
1 | Swastik Kopparty, Sergey Yekhanin |
Detecting Rational Points on Hypersurfaces over Finite Fields. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Chevalley-Warning Theorem, Lang-Weil Theorem, Nonsingular Spaces of Matrices, Polynomial Identity Testing |
1 | Kiran S. Kedlaya, Sergey Yekhanin |
Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Locally decodable codes, Mersenne primes |
1 | Dmitry Gavinsky, Pavel Pudlák |
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
separation of communication classes, communication complexity, quantum communication |
1 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
hard sets, polynomial advice, instance complexity |
1 | |
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA |
CCC |
2008 |
DBLP BibTeX RDF |
|
1 | Ran Raz, Amir Yehudayoff |
Lower Bounds and Separations for Constant Depth Multilinear Circuits. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Constant Depth, Lower Bounds, Separations, Arithmetic Circuits |
1 | Per Austrin, Elchanan Mossel |
Approximation Resistant Predicates from Pairwise Independence. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Max k-CSP, Approximation Resistance, Pairwise Independence, Unique Games Conjecture |
1 | Alexander A. Sherstov |
Communication Complexity under Product and Nonproduct Distributions. |
CCC |
2008 |
DBLP DOI BibTeX RDF |
Randomized/distributional communication complexity, product/nonproduct distributions, Yao's Minimax Principle |