default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 16
Volume 16, Number 1, May 2007
- Prahladh Harsha
, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh:
Communication vs. Computation. 1-33 - Zeev Dvir, Amir Shpilka:
An Improved Analysis of Linear Mergers. 34-59 - Martin Beaudry, Markus Holzer:
The Complexity of Tensor Circuit Evaluation. 60-111
Volume 16, Number 2, May 2007
- Venkatesan Guruswami, Valentine Kabanets:
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. 113-114 - Neeraj Kayal, Nitin Saxena:
Polynomial Identity Testing for Depth 3 Circuits. 115-138 - Dieter van Melkebeek, Konstantin Pervyshev:
A Generic Time Hierarchy with One Bit of Advice. 139-179 - Rocco A. Servedio:
Every Linear Threshold Function has a Low-Weight Approximator. 180-209
Volume 16, Number 3, October 2007
- Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers. 211-244 - Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. 245-297 - Ingo Wegener, Philipp Woelfel:
New Results on the Complexity of the Middle Bit of Multiplication. 298-323
Volume 16, Number 4, December 2007
- Oded Goldreich, Salil P. Vadhan:
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword. 325-330 - Luca Trevisan, Salil P. Vadhan:
Pseudorandomness and Average-Case Complexity Via Uniform Reductions. 331-364 - Daniele Micciancio:
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions. 365-411 - Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma:
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. 412-441
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-12-09 23:25 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:
