Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | |
IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014 |
CCC |
2014 |
DBLP BibTeX RDF |
|
1 | Ryan Williams 0001 |
Algorithms for Circuits and Circuits for Algorithms. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Swastik Kopparty, Shubhangi Saraf, Amir Shpilka |
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan 0002 |
On the Power of Symmetric LP and SDP Relaxations. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Karl Wimmer |
Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz |
AM with Multiple Merlins. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Chaoping Xing |
Hitting Sets for Low-Degree Polynomials with Optimal Density. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Aleksandrs Belovs |
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Arturs Backurs, Mohammad Bavarian |
On the Sum of L1 Influences. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Jain 0001, Attila Pereszlényi, Penghui Yao |
A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Albert Atserias, Massimo Lauria, Jakob Nordström |
Narrow Proofs May Be Maximally Long. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Bruno Bauwens, Marius Zimand |
Linear List-Approximation for Short Programs (or the Power of a Few Random Bits). |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Simon Straub, Thomas Thierauf, Fabian Wagner |
Counting the Number of Perfect Matchings in K5-Free Graphs. |
CCC |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Aleksandrs Belovs, Ansis Rosmanis |
On the Power of Non-adaptive Learning Graphs. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Andris Ambainis, Ronald de Wolf |
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions? |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira |
Constructing Hard Functions Using Learning Algorithms. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Patrick M. Hayden, Kevin Milner, Mark M. Wilde |
Two-Message Quantum Interactive Proofs and the Quantum Separability Problem. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Albert Atserias, Moritz Müller, Sergi Oliva |
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Siu Man Chan |
Just a Pebble Game. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan, Tongke Xue |
A Derandomized Switching Lemma and an Improved Derandomization of AC0. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | John P. Steinberger |
The Distinguishability of Product Distributions by Read-Once Branching Programs. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Sepp Hartung, André Nichterlein |
On the Parameterized and Approximation Hardness of Metric Dimension. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Sushant Sachdeva, Rishi Saket |
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Santhanam, Ryan Williams 0001 |
On Medium-Uniformity and Circuit Lower Bounds. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Justin Gilmer, Michael E. Saks, Srikanth Srinivasan 0001 |
Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Daniel M. Kane |
The Correct Exponent for the Gotsman-Linial Conjecture. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Gil Cohen |
On Rigid Matrices and U-polynomials. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Ankit Gupta 0001, Neeraj Kayal, Youming Qiao |
Random Arithmetic Formulas Can Be Reconstructed Efficiently. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang |
Shared Randomness and Quantum Communication in the Multi-party Model. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Michael Viderman |
Strong LTCs with Inverse Polylogarithmic Rate and Soundness. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand |
Short Lists with Short Programs in Short Time. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Ankit Gupta 0001, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi |
Approaching the Chasm at Depth Four. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013 |
CCC |
2013 |
DBLP BibTeX RDF |
|
1 | Eric Blais, Li-Yang Tan |
Approximating Boolean Functions with Depth-2 Circuits. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert |
On the Lattice Smoothing Parameter Problem. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Madhur Tulsiani, Pratik Worah |
LS+ Lower Bounds from Pairwise Independence. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe 0001 |
An O(n½+∑)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Irit Dinur, Gillat Kol |
Covering CSPs. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Yasuhiro Takahashi, Seiichiro Tani |
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami, Krzysztof Onak |
Superlinear Lower Bounds for Multipass Graph Processing. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Pavel Hrubes, Amir Yehudayoff |
Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody, Harry Buhrman, Michal Koucký 0001, Bruno Loff, Florian Speelman, Nikolay K. Vereshchagin |
Towards a Reverse Newman's Theorem in Interactive Information Complexity. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Oded Regev 0001, Thomas Vidick |
Quantum XOR Games. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
1 | Gil Cohen, Ran Raz, Gil Segev 0001 |
Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe 0001 |
Is Valiant-Vazirani's Isolation Probability Improvable? |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov |
Share Conversion and Private Information Retrieval. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Dmitry Gavinsky |
Quantum Money with Classical Verification. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Joshua A. Grochow |
Matrix Isomorphism of Matrix Lie Algebras. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Guy Moshkovitz |
Complexity Lower Bounds through Balanced Graph Properties. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | André Chailloux, Or Sattath |
The Complexity of the Separable Hamiltonian Problem. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Chi-Jen Lu |
Hitting Set Generators for Sparse Polynomials over Any Finite Fields. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Samuel R. Buss, Ryan Williams 0001 |
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Prasad Raghavendra, David Steurer, Madhur Tulsiani |
Reductions between Expansion Problems. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Amnon Ta-Shma, Christopher Umans |
Better Condensers and New Extractors from Parvaresh-Vardy Codes. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Per Austrin, Johan Håstad |
On the Usefulness of Predicates. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký 0001, Toniann Pitassi |
The Hardness of Being Private. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Amir Shpilka, Christopher Umans |
On Sunflowers and Matrix Multiplication. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Sourav Chakraborty 0001, Eldar Fischer, David García-Soriano, Arie Matsliah |
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan 0001 |
Pseudorandom Generators for Read-Once ACC^0. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Jérémie Roland |
A Strong Direct Product Theorem for Quantum Query Complexity. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Sangxia Huang, Pinyan Lu |
A Dichotomy for Real Weighted Holant Problems. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Andrew Drucker |
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Baris Aydinlioglu, Dieter van Melkebeek |
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. |
CCC |
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. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Toniann Pitassi |
Communication Complexity and Information Complexity: Foundations and New Directions. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Russell Impagliazzo, Srikanth Srinivasan 0001 |
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Yuichi Yoshida |
Testing List H-homomorphisms. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Peter Bürgisser |
Prospects for Geometric Complexity Theory. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012 |
CCC |
2012 |
DBLP BibTeX RDF |
|
1 | Derrick Stolee, N. V. Vinodchandran |
Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh 0001, Magnus Wahlström |
On Problems as Hard as CNF-SAT. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Elena Grigorescu, Chris Peikert |
List Decoding Barnes-Wall Lattices. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Parikshit Gopalan, Raghu Meka, Omer Reingold |
DNF Sparsification and a Faster Deterministic Counting Algorithm. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Or Meir |
Combinatorial PCPs with Short Proofs. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Kazuhisa Seto, Suguru Tamaki |
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Ran Raz, Ricky Rosen |
A Strong Parallel Repetition Theorem for Projection Games on Expanders. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Guy Kindler, Ryan O'Donnell |
Gaussian Noise Sensitivity and Fourier Tails. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Markus Bläser, Bekhan Chokaev |
Algebras of Minimal Multiplicative Complexity. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Richard J. Lipton, Ryan Williams 0001 |
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi |
Space Complexity in Polynomial Calculus. |
CCC |
2012 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
Improved Constructions of Three Source Extractors. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Daniel M. Kane |
k-Independent Gaussians Fool Polynomial Threshold Functions. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Boris Alexeev, Michael A. Forbes 0001, Jacob Tsimerman |
Tensor Rank: Some Lower and Upper Bounds. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Oded Regev 0001, Giannicola Scarpa, Ronald de Wolf |
Near-Optimal and Explicit Bell Inequality Violations. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011 |
CCC |
2011 |
DBLP BibTeX RDF |
|
1 | Jin-yi Cai, Xi Chen 0001, Pinyan Lu |
Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Shubhangi Saraf, Sergey Yekhanin |
Noisy Interpolation of Sparse Polynomials, and Applications. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Ryan O'Donnell, Yi Wu 0002, Yuan Zhou 0007 |
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Amir Shpilka, Avishay Tal |
On the Minimal Fourier Degree of Symmetric Boolean Functions. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Sevag Gharibian, Julia Kempe |
Approximation Algorithms for QMA-Complete Problems. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Michael Viderman |
Towards Lower Bounds on Locally Testable Codes via Density Arguments. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Hartmut Klauck |
On Arthur Merlin Games in Communication Complexity. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Russell Impagliazzo |
Relativized Separations of Worst-Case and Average-Case Complexities for NP. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Eric Blais, Joshua Brody, Kevin Matulef |
Property Testing Lower Bounds via Communication Complexity. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Anindya De |
Pseudorandomness for Permutation and Regular Branching Programs. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Ryan Williams 0001 |
Non-uniform ACC Circuit Lower Bounds. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Marius Zimand |
Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich |
Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
Paris-Harrington Tautologies. |
CCC |
2011 |
DBLP DOI BibTeX RDF |
|