default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational 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
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-10-29 01:37 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:
