![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Computational Complexity, Volume 25
Volume 25, Number 1, March 2016
- Or Meir:
Combinatorial PCPs with Short Proofs. 1-102 - André Chailloux, Iordanis Kerenidis, Bill Rosgen:
Quantum commitments from complexity assumptions. 103-151 - Thomas Watson:
The complexity of estimating min-entropy. 153-175 - Klaus Aehlig, Stephen A. Cook, Phuong Nguyen:
Relativizing small complexity classes and their theories. 177-215 - Eric Allender
, Fengming Wang:
On the power of algebraic branching programs of width two. 217-253 - Sangxia Huang, Pinyan Lu
:
A Dichotomy for Real Weighted Holant Problems. 255-304
Volume 25, Number 2, June 2016
- Zeev Dvir, David Zuckerman:
Special issue "Computational Complexity Conference 2015" Guest Editors' Foreword. 305-307 - Alex Samorodnitsky, Ilya D. Shkredov
, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. 309-348 - Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang:
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions. 349-418 - Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin. 419-454 - Rafael Oliveira, Amir Shpilka
, Ben lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. 455-505 - Rafael Oliveira:
Factors of low individual degree polynomials. 507-561
Volume 25, Number 3, September 2016
- Oded Goldreich
:
Special Issue on the 10th Theory of Cryptography Conference: Editor's Foreword. 563-565 - Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, Daniel Wichs:
A counterexample to the chain rule for conditional HILL entropy. 567-605 - Rafael Pass
:
Unprovable Security of Perfect NIZK and Non-interactive Non-malleable Commitments. 607-666 - Benny Applebaum:
Cryptographic Hardness of Random Local Functions - Survey. 667-722
Volume 25, Number 4, December 2016
- Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura
, Rudy Raymond
, Seiichiro Tani
, Shigeru Yamashita:
Quantum Query Complexity of Almost All Functions with Fixed On-set Size. 723-735 - Yuichi Yoshida:
Testing list H-homomorphisms. 737-773 - Michael Blondin
, Andreas Krebs, Pierre McKenzie:
The complexity of intersecting finite automata having few final states. 775-814 - Laurent Evain, Mathias Lederer, Bjarke Hammersholt Roune:
Connect Four and Graph Decomposition. 815-848 - Yasuhiro Takahashi, Seiichiro Tani
:
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. 849-881 - Andrew Hughes, Debasis Mandal, Aduri Pavan, Nathan Russell, Alan L. Selman:
A thirty Year old conjecture about promise problems. 883-919 - Jean Bourgain, Zeev Dvir, Ethan Leeman:
Affine extractors over large fields with exponential error. 921-931
![](https://dblp.uni-trier.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.