| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Russell Impagliazzo |
Relativized Separations of Worst-Case and Average-Case Complexities for NP.  |
IEEE Conference on Computational Complexity  |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zohar Shay Karnin, Yuval Rabani, Amir Shpilka |
Explicit Dimension Reduction and Its Applications. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal, Chandan Saha |
On the Sum of Square Roots of Polynomials and Related Problems. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Sevag Gharibian, Julia Kempe |
Approximation Algorithms for QMA-Complete Problems. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami |
Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuichi Yoshida |
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
Paris-Harrington Tautologies. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan |
Symmetric LDPC Codes are not Necessarily Locally Testable. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Hartmut Klauck |
On Arthur Merlin Games in Communication Complexity. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Drucker |
Improved Direct Product Theorems for Randomized Query Complexity. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Li |
A New Approach to Affine Extractors and Dispersers. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Emanuele Viola |
Bounded-Depth Circuits Cannot Sample Good Codes. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De |
Pseudorandomness for Permutation and Regular Branching Programs. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Shubhangi Saraf, Sergey Yekhanin |
Noisy Interpolation of Sparse Polynomials, and Applications. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Yi Wu, Yuan Zhou |
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich |
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011 |
IEEE Conference on Computational Complexity |
2011 |
DBLP BibTeX RDF |
|
| 1 | Amir Shpilka, Avishay Tal |
On the Minimal Fourier Degree of Symmetric Boolean Functions. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marius Zimand |
Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Shachar Lovett |
Linear Systems over Finite Abelian Groups. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland |
Symmetry-Assisted Adversaries for Quantum State Generation. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf |
Near-Optimal and Explicit Bell Inequality Violations. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane |
k-Independent Gaussians Fool Polynomial Threshold Functions. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Li |
Improved Constructions of Three Source Extractors. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Widad Machmouchi |
Making Branching Programs Oblivious Requires Superlogarithmic Overhead. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Michael Viderman |
Towards Lower Bounds on Locally Testable Codes via Density Arguments. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Williams |
Non-uniform ACC Circuit Lower Bounds. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Boris Alexeev, Michael A. Forbes, Jacob Tsimerman |
Tensor Rank: Some Lower and Upper Bounds. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Pinyan Lu |
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Blais, Joshua Brody, Kevin Matulef |
Property Testing Lower Bounds via Communication Complexity. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Watson |
Pseudorandom Generators for Combinatorial Checkerboards. |
IEEE Conference on Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohammad Mahmoody, David Xiao |
On the Power of Randomized Reductions and the Checkability of SAT. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Colusure, Instance Checkers, Complexity, Randomization |
| 1 | Alexandra Kolla |
Spectral Algorithms for Unique Games. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Relationless Completeness and Separations. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Completeness, Separations, Algebraic complexity |
| 1 | Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff |
Derandomizing from Random Strings. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Truth-table Reducibility, Kolmogorov Complexity, Derandomization |
| 1 | Zeev Dvir |
On Matrix Rigidity and Locally Self-Correctable Codes. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
complexity, arithmetic circuits, matrices |
| 1 | Russell Impagliazzo, Ryan Williams |
Communication Complexity with Synchronized Clocks. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
time-communication tradeoffs, lower bounds, communication complexity |
| 1 | Subhash Khot |
On the Unique Games Conjecture (Invited Survey). |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Klaus-Jörn Lange |
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation |
| 1 | Rahul Jain, Hartmut Klauck |
The Partition Bound for Classical Communication Complexity and Query Complexity. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Partition Bound, Lower Bounds, Linear Programming, Communication Complexity, Query Complexity |
| 1 | Oded Regev |
The Learning with Errors Problem (Invited Survey). |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
learning with errors, lattice-based cryptography |
| 1 | Thanh Minh Hoang |
On the Matching Problem for Special Graph Classes. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
NC-computations, Perfect matchings, maximum matchings |
| 1 | |
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010 |
IEEE Conference on Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Julia Kempe, Oded Regev |
No Strong Parallel Repetition with Entangled and Non-signaling Provers. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
entangled two-prover games, unique games, parallel repetition |
| 1 | Matt DeVos, Ariel Gabizon |
Simple Affine Extractors Using Dimension Expansion. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness |
| 1 | Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman |
Fooling Functions of Halfspaces under Product Distributions. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Pseudorandness, complexity theory, halfspace |
| 1 | Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan |
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Boolean function, regularity lemma, polynomial threshold function |
| 1 | Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii |
Exact Threshold Circuits. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Exact Threshold Functions, Boolean Circuits, Threshold Functions |
| 1 | Eric Blais, Ryan O'Donnell |
Lower Bounds for Testing Function Isomorphism. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
lower bounds, Boolean functions, property testing |
| 1 | Jakob Nordström |
On the Relative Strength of Pebbling and Resolution. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
pebbling formula, resolution, space, trade-off, proof complexity, pebble games |
| 1 | Luca Trevisan |
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Universal Search, Average-case Complexity |
| 1 | Daniel M. Kane |
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. |
IEEE Conference on Computational Complexity |
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. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
acyclic digraph, logspace algorithm, planar graph, reachability |
| 1 | Dániel Marx |
Completely Inapproximable Monotone and Antimonotone Parameterized Problems. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
parameterized comlexity, approximation, fixed-parameter tractability, inapproximability |
| 1 | Matei David, Periklis A. Papakonstantinou |
Trade-Off Lower Bounds for Stack Machines. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
AuxPDA, lower bound, streaming, communication complexity, stack, reversals, space bound |
| 1 | Ran Raz |
Parallel Repetition of Two Prover Games (Invited Survey). |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Mohammad Mahmoody, David Xiao |
A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
sampling protocols, constant-round statistically hiding commitments, black-box lower bounds, collision-resistant hash functions |
| 1 | Ronen Shaltiel |
Derandomized Parallel Repetition Theorems for Free Games. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Derandomization, Randomness extractors, Parallel repetition |
| 1 | Irit Dinur, Or Meir |
Derandomized Parallel Repetition of Structured PCPs. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Low error, Direct Product Test, Derandomized Parallel Repetition, PCP, Direct Product, de-Bruijn |
| 1 | Dan Gutfreund, Akinori Kawachi |
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting |
| 1 | Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner |
Planar Graph Isomorphism is in Log-Space. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Královic |
Infinite vs. Finite Space-Bounded Randomized Computations. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Zohar Shay Karnin, Amir Shpilka |
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman |
Poly-logarithmic Independence Fools AC0 Circuits. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Troy Lee, Gideon Schechtman, Adi Shraibman |
Lower Bounds on Quantum Multiparty Communication Complexity. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Nitin Saxena, C. Seshadhri |
An Almost Optimal Rank Bound for Depth-3 Identities. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir |
Extractors for Varieties. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Manindra Agrawal, Osamu Watanabe |
One-Way Functions and the Berman-Hartmanis Conjecture. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Jain, Hartmut Klauck |
New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Neeraj Kayal |
The Complexity of the Annihilating Polynomial. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | T. S. Jayram, Swastik Kopparty, Prasad Raghavendra |
On the Communication Complexity of Read-Once AC^0 Formulae. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Troy Lee, Adi Shraibman |
An Approximation Algorithm for Approximation Rank. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Akitoshi Kawamura |
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anup Rao |
Extractors for Low-Weight Affine Sources. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman |
Locally Testable Codes Require Redundant Testers. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Drucker |
Multitask Efficiencies in the Decision Tree Model. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Subhash Khot, Muli Safra |
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | David Xiao |
On Basing ZK ≠ BPP on the Hardness of PAC Learning. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto |
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran |
Every Permutation CSP of arity 3 is Approximation Resistant. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody |
The Maximum Communication Complexity of Multi-Party Pointer Jumping. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Rocco A. Servedio |
Improved Approximation of Linear Threshold Functions. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009 |
IEEE Conference on Computational Complexity |
2009 |
DBLP BibTeX RDF |
|
| 1 | Guy N. Rothblum, Salil P. Vadhan |
Are PCPs Inherent in Efficient Arguments? |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel |
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Kristoffer Arnsfelt Hansen, Michal Koucký |
A New Characterization of ACC0 and Probabilistic CC0. |
IEEE Conference on Computational Complexity |
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. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Lance Fortnow, Rahul Santhanam, Ryan Williams |
Fixed-Polynomial Size Circuit Bounds. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Shachar Lovett, Amir Shpilka |
On the Complexity of Boolean Functions in Different Characteristics. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam R. Day |
Increasing the Gap between Descriptional Complexity and Algorithmic Probability. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Jain, John Watrous |
Parallel Approximation of Non-interactive Zero-sum Quantum Games. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Iddo Tzameret |
The Proof Complexity of Polynomial Identities. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson |
Quantum Copy-Protection and Quantum Money. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luis Filipe Coelho Antunes, Lance Fortnow |
Worst-Case Running Times for Average-Case Algorithms. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Kazuyuki Amano |
k-Subgraph Isomorphism on AC0 Circuits. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikos Leonardos, Michael Saks |
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Venkatesan Guruswami |
Hardness Amplification within NP against Deterministic Algorithms. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Hardness Amplication, Error-Correcting Codes, Derandomization, NP |
| 1 | Nati Linial, Adi Shraibman |
Learning Complexity vs. Communication Complexity. |
IEEE Conference on Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
large margin classifiers, communication complexity, discrepancy, rigidity |
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")