default search action
Computational Complexity, Volume 15
Volume 15, Number 1, May 2006
- Kiran S. Kedlaya:
Quantum computation of zeta functions of curves. 1-19 - Elad Hazan
, Shmuel Safra
On the complexity of approximating k-set packing. 20-39 - Jan Kára, Daniel Král
Free binary decision diagrams for the computation of EARn. 40-61 - Kristoffer Arnsfelt Hansen
Circuits on cylinders. 62-81 - Richard Beigel, Lance Fortnow, William I. Gasarch:
A tight lower bound for restricted pir protocols. 82-91
Volume 15, Number 2, June 2006
- Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword. 93 - Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani
On the Hardness of Approximating Multicut and Sparsest-Cut. 94-114 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Computationally Private Randomizing Polynomials and Their Applications. 115-162 - Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. 163-196
Volume 15, Number 3, October 2006
- Peter Bürgisser, Felipe Cucker
The complexity of semilinear problems in succinct representation. 197-235 - Saugata Basu:
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities. 236-251 - Nader H. Bshouty, Michael Kaminski:
Polynomial multiplication over finite fields: from quadratic to straight-line complexity. 252-262 - Oded Goldreich
Lower bounds for linear locally decodable codes and private information retrieval. 263-296
Volume 15, Number 4, December 2006
- Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword. 297 - Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. 298-341 - Neeraj Kayal, Nitin Saxena
Complexity of Ring Morphism Problems. 342-390 - Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. 391-432 - Ryan Williams
Inductive Time-Space Lower Bounds for Sat and Related Problems. 433-470
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-12-15 01:16 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: