default search action
Computational Complexity, Volume 21
Volume 21, Number 1, March 2012
- Oded Goldreich
, Salil P. Vadhan:
Special issue from RANDOM'09: Editors' Foreword. 1 - Jeff Kinne
Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. 3-61 - Ido Ben-Eliezer, Rani Hod
Random low-degree polynomials are hard to approximate. 63-81 - Andrej Bogdanov, Youming Qiao
On the security of Goldreich's one-way function. 83-127 - Oded Goldreich
Hierarchy Theorems for Property Testing. 129-192
Volume 21, Number 2, June 2012
- Anup Rao:
Special Issue "Conference on Computational Complexity 2011" Guest Editor's Foreword. 193-195 - Andrew Drucker:
Improved direct product theorems for randomized query complexity. 197-244 - Shachar Lovett
Bounded-Depth Circuits Cannot Sample Good Codes. 245-266 - Eli Ben-Sasson, Michael Viderman:
Towards lower bounds on locally testable codes via density arguments. 267-309 - Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity. 311-358
Volume 21, Number 3, September 2012
- Markus Bläser, Holger Dell
Complexity and Approximability of the Cover Polynomial. 359-419 - Jacek Pomykala, Bartosz Zralek
On reducing factorization to the discrete logarithm problem modulo a composite. 421-429 - Henning Wunderlich:
On a Theorem of Razborov. 431-477 - Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
Low-Depth Witnesses are Easy to Find. 479-497 - Hugue Blier, Alain Tapp:
A Quantum Characterization Of NP. 499-510 - Hannah Alpert
Length 3 Edge-Disjoint Paths Is NP-Hard. 511-513
Volume 21, Number 4, December 2012
- Zeev Dvir:
Extractors for varieties. 515-572 - Jin-Yi Cai, Pinyan Lu
Holographic reduction, interpolation and hardness. 573-604 - Leslie Ann Goldberg, Mark Jerrum:
Inapproximability of the Tutte polynomial of a planar graph. 605-642 - Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran:
On the power of unambiguity in log-space. 643-670
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 2024-11-22 19:32 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: