| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Peter Bürgisser |
Prospects for Geometric Complexity Theory.  |
IEEE Conference on Computational Complexity  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012 |
IEEE Conference on Computational Complexity |
2012 |
DBLP BibTeX RDF |
|
| 1 | Prasad Raghavendra, David Steurer, Madhur Tulsiani |
Reductions between Expansion Problems. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Moshkovitz |
Complexity Lower Bounds through Balanced Graph Properties. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Markus Bläser, Bekhan Chokaev |
Algebras of Minimal Multiplicative Complexity. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan |
Pseudorandom Generators for Read-Once ACC^0. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Gus Gutoski, Xiaodi Wu |
Parallel Approximation of Min-max Problems with Applications to Classical and Quantum Zero-Sum Games. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Gavinsky |
Quantum Money with Classical Verification. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah |
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Kazuhisa Seto, Suguru Tamaki |
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amnon Ta-Shma, Christopher Umans |
Better Condensers and New Extractors from Parvaresh-Vardy Codes. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Ricky Rosen |
A Strong Parallel Repetition Theorem for Projection Games on Expanders. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Amir Shpilka, Christopher Umans |
On Sunflowers and Matrix Multiplication. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel R. Buss, Ryan Williams |
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi |
Space Complexity in Polynomial Calculus. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Or Meir |
Combinatorial PCPs with Short Proofs. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Ran Raz, Gil Segev |
Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Johan Håstad |
On the Usefulness of Predicates. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Raghu Meka, Omer Reingold |
DNF Sparsification and a Faster Deterministic Counting Algorithm. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov |
Share Conversion and Private Information Retrieval. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Baris Aydinlioglu, Dieter van Melkebeek |
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Chi-Jen Lu |
Hitting Set Generators for Sparse Polynomials over Any Finite Fields. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Derrick Stolee, N. V. Vinodchandran |
Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Russell Impagliazzo, Srikanth Srinivasan |
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Toniann Pitassi |
Communication Complexity and Information Complexity: Foundations and New Directions. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard J. Lipton, Ryan Williams |
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | André Chailloux, Or Sattath |
The Complexity of the Separable Hamiltonian Problem. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Sangxia Huang, Pinyan Lu |
A Dichotomy for Real Weighted Holant Problems. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe |
Is Valiant-Vazirani's Isolation Probability Improvable? |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Troy Lee, Jérémie Roland |
A Strong Direct Product Theorem for Quantum Query Complexity. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua A. Grochow |
Matrix Isomorphism of Matrix Lie Algebras. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kindler, Ryan O'Donnell |
Gaussian Noise Sensitivity and Fourier Tails. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuichi Yoshida |
Testing List H-homomorphisms. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström |
On Problems as Hard as CNF-SAT. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Elena Grigorescu, Chris Peikert |
List Decoding Barnes-Wall Lattices. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew Drucker |
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi |
The Hardness of Being Private. |
IEEE Conference on Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 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 |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")