![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Computational 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
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
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.