| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Andrej Bogdanov, Youming Qiao |
On the security of Goldreich's one-way function.  |
Computational Complexity  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Salil P. Vadhan |
Special issue from RANDOM'09: Editors' Foreword. |
Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg |
Hierarchy Theorems for Property Testing. |
Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel |
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. |
Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Ido Ben-Eliezer, Rani Hod, Shachar Lovett |
Random low-degree polynomials are hard to approximate. |
Computational Complexity |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra |
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Allan Borodin, Toniann Pitassi, Alexander A. Razborov |
Special Issue In Memory of Misha Alekhnovich. Foreword. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Pascal Koiran, Sylvain Perifel |
Interpolation in Valiant's Theory. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronen Shaltiel |
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich, Alexander A. Razborov |
Satisfiability, Branch-Width and Tseitin tautologies. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis |
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Or Meir |
Derandomized Parallel Repetition via Structured PCPs. |
Computational Complexity |
2011 |
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. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandra Kolla |
Spectral Algorithms for Unique Games. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich |
More on Average Case vs Approximation Complexity. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Max Nalsky, Michael Ostrovsky |
Obituary. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
Complexity of Hard-Core Set Proofs. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich |
Lower Bounds for k-DNF Resolution on Random 3-CNFs. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane |
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefan S. Dantchev, Barnaby Martin, Stefan Szeider |
Parameterized Proof Complexity. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Kambites |
Generic Complexity of Finitely Presented Monoids and Semigroups. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi |
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir |
On Matrix Rigidity and Locally Self-correctable Codes. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan T. Chakaravarthy, Sambuddha Roy |
Arthur and Merlin as Oracles. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi |
Hardness of Approximating the Closest Vector Problem with Pre-Processing. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Dieter van Melkebeek |
Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Amir Yehudayoff |
Homogeneous Formulas and Symmetric Polynomials. |
Computational Complexity |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Or Sheffet |
On The Randomness Complexity of Property Testing. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad |
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Guy N. Rothblum, Salil P. Vadhan |
Are PCPs Inherent in Efficient Arguments? |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jin-yi Cai, Xi Chen, Dong Li |
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Thanh Minh Hoang, Thomas Thierauf |
The Complexity of the Inertia. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeff Kinne, Dieter van Melkebeek |
Space Hierarchy Results for Randomized and other Semantic Models. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
A Complexity Dichotomy For Hypergraph Partition Functions. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Kazuyuki Amano |
k-Subgraph Isomorphism on AC0 Circuits. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Parikshit Gopalan, Amir Shpilka, Shachar Lovett |
The Complexity of Boolean Functions in Different Characteristics. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Noam Livne |
All Natural NP-Complete Problems Have Average-Case Complete Versions. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Communication Complexity Under Product and Nonproduct Distributions. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Vikraman Arvind, T. C. Vijayaraghavan |
Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan |
New Results on Noncommutative and Commutative Polynomial Identity Testing. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Bürgisser, Peter Scheiblechner |
Counting Irreducible Components of Complex Algebraic Varieties. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Erich Kaltofen, Mark Lavin |
Efficiently Certifying Non-Integer Powers. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Kristoffer Arnsfelt Hansen, Michal Koucký |
A New Characterization of ACC0 and Probabilistic CC0. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Dana Moshkovitz, Ran Raz |
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam R. Klivans, Alexander A. Sherstov |
Lower Bounds for Agnostic Learning via Approximate Rank. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Giesbrecht, Daniel S. Roche |
Interpolation of Shifted-Lacunary Polynomials. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Russell Impagliazzo |
Random Cnf's are Hard for the Polynomial Calculus. |
Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikos Leonardos, Michael Saks |
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Akitoshi Kawamura |
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. |
Computational Complexity |
2010 |
DBLP BibTeX RDF |
|
| 1 | Amos Beimel, Renen Hallak, Kobbi Nissim |
Private Approximation of Clustering and Vertex Cover. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ezequiel Dratman, Guillermo Matera, Ariel Waissbein |
Robust Algorithms For Generalized Pham Systems. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Primary 14Q05, 68W30 - Secondary 12Y05, 13F25, 14Q20, Subject classification, 68W40 |
| 1 | Paul Beame, Amit Chakrabarti |
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Nutan Limaye, Meena Mahajan, Jayalal M. N. Sarma |
Upper Bounds for Monotone Planar Circuit Value and Variants. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Emmanuel Briand, Rosa Orellana, Mercedes Rosas |
Reduced Kronecker Coefficients and Counter-Examples to Mulmuley's Strong Saturation Conjecture SH. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
Extractors And Rank Extractors For Polynomial Sources. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Derandomization, Extractors |
| 1 | Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick |
Using Entanglement in Quantum Multi-Prover Interactive Proofs. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Subject classification. 03D15, 81P68, 68Q15, 68Q10 |
| 1 | Per Austrin, Elchanan Mossel |
Approximation Resistant Predicates from Pairwise Independence. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
MSC Primary 68Q17, Secondary 41A52, Subject classification |
| 1 | Troy Lee, Adi Shraibman |
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka |
The Black-Box Query Complexity of Polynomial Summation. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Subject classification. 68Q05, 68Q17, 68Q25, 68Q15 |
| 1 | Emanuele Viola |
The Sum of D Small-Bias Generators Fools Polynomials of Degree D. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
68Q99, Subject classification |
| 1 | Peter Bürgisser |
On Defining Integers And Proving Arithmetic Circuit Lower Bounds. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Primary 68Q17, Secondary 11D45, Subject classification |
| 1 | Ran Raz, Amir Yehudayoff |
Lower Bounds and Separations for Constant Depth Multilinear Circuits. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Felipe Cucker, Paulin Jacobé de Naurois |
Parallel Time and Quantifier Prefixes. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
On Approximate Majority and Probabilistic Time. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Pascal Koiran, Sylvain Perifel |
VPSPACE and a Transfer Theorem over the Reals. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On the Approximation Resistance of a Random Predicate. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka |
Constructions of Low-degree and Error-Correcting epsilon-Biased Generators. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Subject classification. 03D15, 68Q17 |
| 1 | Mark Braverman, Raghav Kulkarni, Sambuddha Roy |
Space-Efficient Counting in Graphs on Surfaces. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Hashemi |
Nullstellensätze for Zero-Dimensional Gröbner Bases. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Primary 13P10, Secondary 68Q17, Subject classification |
| 1 | Alexander Healy |
Randomness-Efficient Sampling within NC1. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q15, 68R10, Subject classification. 68Q10 |
| 1 | R. Ryan Williams |
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification. 68Q15 |
| 1 | Marius Zimand |
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification, 68Q15 |
| 1 | Oded Goldreich |
Preface to the Special Issue from Random'06. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
Every 2-csp Allows Nontrivial Approximation. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 68W25, 68Q25 |
| 1 | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
On Pseudorandom Generators with Linear Stretch in NC0. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 94A60, 68P25 |
| 1 | Peter Bro Miltersen |
Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Iddo Tzameret |
The Strength of Multilinear Proofs. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 03F20, 68Q17, 13P10 |
| 1 | Alexander A. Sherstov |
Halfspace Matrices. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 03D15, 68Q17, 68Q15 |
| 1 | Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay |
Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 81P68, 68Q10 |
| 1 | Oded Lachish, Ilan Newman, Asaf Shapira |
Space Complexity Vs. Query Complexity. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification. 68Q15, 68Q10 |
| 1 | Jin-yi Cai, Pinyan Lu |
Basis Collapse in Holographic Algorithms. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q25, Subject classification. 68Q17 |
| 1 | Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
On the Complexity of Succinct Zero-Sum Games. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
91A05, 68Q17, Subject classification. 68Q15, 03D15, 68Q32 |
| 1 | Chris Peikert |
Limits on the Hardness of Lattice Problems in lp Norms. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
11H06, 94B75, 68Q25, Subject classification. 68Q17 |
| 1 | Aduri Pavan, N. V. Vinodchandran |
2-Local Random Reductions to 3-Valued Functions. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification. 68Q15 |
| 1 | John M. Hitchcock, Aduri Pavan |
Hardness Hypotheses, Derandomization, and Circuit Complexity. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q30, 68Q17, Subject classification. 68Q15 |
| 1 | Xiaoyang Gu, Jack H. Lutz |
Dimension Characterizations of Complexity Classes. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification, 68Q15 |
| 1 | Venkatesan Guruswami, Valentine Kabanets |
Hardness Amplification via Space-Efficient Direct Products. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17 |
| 1 | Hubie Chen |
Inverse NP Problems. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Dima Grigoriev |
Probabilistic Communication Complexity Over The Reals. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification, 68W40 |
| 1 | Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton |
Polynomials that Sign Represent Parity and Descartes' Rule of Signs. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
68Q17, Subject classification |
| 1 | Ran Raz, Amir Yehudayoff |
Balancing Syntactically Multilinear Arithmetic Circuits. |
Computational Complexity |
2008 |
DBLP DOI BibTeX RDF |
Subject classification, 68W30 |
| 1 | Neeraj Kayal, Nitin Saxena |
Polynomial Identity Testing for Depth 3 Circuits. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
13P99, Subject classification. 68Q15 |
| 1 | Zeev Dvir, Amir Shpilka |
An Improved Analysis of Linear Mergers. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
68W20, Subject classification |
| 1 | Rocco A. Servedio |
Every Linear Threshold Function has a Low-Weight Approximator. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
Subject classification. 06E30, 52C07, 52C35, 68Q15, 68Q32 |
| 1 | Paul Beame, Russell Impagliazzo, Ashish Sabharwal |
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
Subject classification. 03F20, 68Q17 |
| 1 | Dieter van Melkebeek, Konstantin Pervyshev |
A Generic Time Hierarchy with One Bit of Advice. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
Subject classification. 68Q15, 68Q10 |
| 1 | Daniele Micciancio |
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
11H06, Subject classification. 68Q17, 94B15 |
| 1 | Martin Beaudry, Markus Holzer |
The Complexity of Tensor Circuit Evaluation. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
Subject classification. 15A69, 68Q70, 68Q17, 68Q15, 68Q05 |
| 1 | Venkatesan Guruswami, Valentine Kabanets |
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")