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

Special Issue: Conference on Computational Complexity 2015 (CCC 2015)

• 
  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 Mendes de 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

Special Issue: 10th Theory of Cryptography Conference 2013 (TCC 2013)

• 
  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