default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 20
Volume 20, Number 1, March 2011
- Pascal Koiran, Sylvain Perifel:
Interpolation in Valiant's Theory. 1-20 - Mark Kambites:
Generic Complexity of Finitely Presented Monoids and Semigroups. 21-50 - Stefan S. Dantchev
, Barnaby Martin, Stefan Szeider:
Parameterized Proof Complexity. 51-85 - Ronen Shaltiel:
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. 87-143 - Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu:
Complexity of Hard-Core Set Proofs. 145-171
Volume 20, Number 2, June 2011
- Dieter van Melkebeek:
Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. 173-175 - Alexandra Kolla:
Spectral Algorithms for Unique Games. 177-206 - Irit Dinur, Or Meir:
Derandomized Parallel Repetition via Structured PCPs. 207-327 - Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi:
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. 329-366 - Zeev Dvir:
On Matrix Rigidity and Locally Self-correctable Codes. 367-388 - Daniel M. Kane:
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. 389-412
Volume 20, Number 3, September 2011
- Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. 413-504 - Venkatesan T. Chakaravarthy, Sambuddha Roy:
Arthur and Merlin as Oracles. 505-558 - Pavel Hrubes, Amir Yehudayoff:
Homogeneous Formulas and Symmetric Polynomials. 559-578
Volume 20, Number 4, December 2011
- Allan Borodin, Toniann Pitassi, Alexander A. Razborov:
Special Issue In Memory of Misha Alekhnovich. Foreword. 579-590 - Max Nalsky, Michael Ostrovsky:
Obituary. 591-595 - Michael Alekhnovich:
Lower Bounds for k-DNF Resolution on Random 3-CNFs. 597-614 - Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. 615-648 - Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin tautologies. 649-678 - Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. 679-740 - Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi:
Hardness of Approximating the Closest Vector Problem with Pre-Processing. 741-753 - Michael Alekhnovich:
More on Average Case vs Approximation Complexity. 755-786
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-02-21 19:21 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
