default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2026
Volume TR16, 2016
- Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza:
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs. - Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. - Boris Brimkov, Illya V. Hicks:
On the logspace shortest path problem. - Dax Enshan Koh:
Further extensions of Clifford circuits and their classical simulation complexities. - Olaf Beyersdorff, Leroy Chew, Mikolas Janota:
Extension Variables in QBF Resolution. - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits. - Guy Kindler:
Property Testing, PCP, andJuntas. - Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Algorithms from Natural Lower Bounds. - Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Identity Testing for constant-width, and commutative, read-once oblivious ABPs. - Alexander A. Razborov:
On the Width of Semi-Algebraic Proofs and Algorithms. - Olaf Beyersdorff, Ján Pich:
Understanding Gentzen and Frege systems for QBF. - John M. Hitchcock, Hadi Shafei:
Autoreducibility of NP-Complete Sets. - Ludwig Staiger:
Bounds on the Kolmogorov complexity function for infinite words. - Gil Cohen, Leonard J. Schulman:
Extractors for Near Logarithmic Min-Entropy. - Oded Goldreich:
The uniform distribution is complete with respect to testing identity to a fixed distribution. - Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson:
Doubly infinite separation of quantum information and communication. - Georgios Stamoulis:
Limitations of Linear Programming Techniques for Bounded Color Matchings. - Kuan Cheng, Xin Li:
Randomness Extraction in AC0 and with Small Locality. - Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. - Zachary Remscrim:
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. - Shachar Lovett, Jiapeng Zhang:
Noisy Population Recovery from Unknown Noise. - Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki:
Circuit size lower bounds and #SAT upper bounds through a general framework. - Ilan Komargodski, Moni Naor, Eylon Yogev:
How to Share a Secret, Infinitely. - Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. - Shachar Lovett:
The Fourier structure of low degree polynomials. - Anindya De, Michael E. Saks, Sijian Tang:
Noisy population recovery in polynomial time. - Sagnik Mukhopadhyay:
Tribes Is Hard in the Message Passing Model. - Olaf Beyersdorff, Joshua Blinkhorn:
Dependency Schemes in QBF Calculi: Semantics and Soundness. - Joshua Brakensiek, Venkatesan Guruswami:
New hardness results for graph and hypergraph colorings. - Gil Cohen:
Non-Malleable Extractors with Logarithmic Seeds. - Titus Dose:
Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers. - Roei Tell:
A Note on Tolerant Testing with One-Sided Error. - Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight bounds for communication assisted agreement distillation. - Mohamed El Halaby:
On the Computational Complexity of MaxSAT. - Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. - Eshan Chattopadhyay, Xin Li:
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. - Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness when the odds are against you. - Meena Mahajan, Nitin Saurabh:
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. - Adam Bouland, Laura Mancinska, Xue Zhang:
Complexity Classification of Two-Qubit Commuting Hamiltonians. - Baris Aydinlioglu, Eric Bach:
Affine Relativization: Unifying the Algebrization and Relativization Barriers. - Johan Håstad:
An average-case depth hierarchy theorem for higher depth. - Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. - Mikolas Janota:
On Q-Resolution and CDCL QBF Solving. - Kaave Hosseini, Shachar Lovett:
Structure of protocols for XOR functions. - Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. - Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck. - Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel repetition via fortification: analytic view and the quantum case. - Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda:
Lifting QBF Resolution Calculi to DQBF. - Cynthia Dwork, Moni Naor, Guy N. Rothblum:
Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems. - Roei Tell:
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. - Ronald Cramer, Chaoping Xing, Chen Yuan:
On Multi-Point Local Decoding of Reed-Muller Codes. - Gil Cohen:
Making the Most of Advice: New Correlation Breakers and Their Applications. - Jiawei Gao, Russell Impagliazzo:
Orthogonal Vectors is hard for first-order properties on sparse graphs. - Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. - Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. - Shafi Goldwasser, Dhiraj Holden:
On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances. - Ilario Bonacina:
Total space in Resolution is at least width squared. - Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. - Alon Rosen, Gil Segev, Ido Shahaf:
Can PPAD Hardness be Based on Standard Cryptographic Assumptions? - Henry Yuen:
A parallel repetition theorem for all entangled games. - Omer Reingold, Ron Rothblum, Guy N. Rothblum:
Constant-Round Interactive Proofs for Delegating Computation. - Avishay Tal:
On The Sensitivity Conjecture. - Pavel Hubácek, Eylon Yogev:
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. - Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman:
Exponential Lower Bounds for Monotone Span Programs. - Xi Chen, Yu Cheng, Bo Tang:
A Note on Teaching for VC Classes. - Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. - Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani:
Pebbling Meets Coloring : Reversible Pebble Game On Trees. - Srikanth Srinivasan:
On Polynomial Approximations to AC0. - Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. - Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. - Jan Krajícek, Igor Carboni Oliveira:
Unprovability of circuit upper bounds in Cook's theory PV. - Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. - Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev:
Improved concrete efficiency and security analysis of Reed-Solomon PCPPs. - Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. - Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC0. - Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma:
Characterization and Lower Bounds for Branching Program Size using Projective Dimension. - Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai:
Non-Interactive RAM and Batch NP Delegation from any PIR. - Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. - Adam Kurpisz
, Samuli Leppänen, Monaldo Mastrolilli:
Sum-of-squares hierarchy lower bounds for symmetric formulations. - Oded Goldreich:
Reducing testing affine spaces to testing linearity. - Alexander A. Sherstov:
Compressing interactive communication under product distributions. - Benny Applebaum, Pavel Raykov:
Fast Pseudorandom Functions Based on Expander Graphs. - Nader H. Bshouty:
Derandomizing Chernoff Bound with Union Bound with an Application to k-wise Independent Sets. - Shalev Ben-David:
Low-Sensitivity Functions from Unambiguous Certificates. - Shiteng Chen, Periklis A. Papakonstantinou:
Depth-reduction for composites. - Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. - Shalev Ben-David, Robin Kothari:
Randomized query complexity of sabotaged and composed functions. - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Explicit two-source extractors for near-logarithmic min-entropy. - Vikraman Arvind, Partha Mukhopadhyay, Raja S:
Randomized Polynomial Time Identity Testing for Noncommutative Circuits. - Bernhard Haeupler, Ameya Velingker:
Bridging the Capacity Gap Between Interactive and One-Way Communication. - Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan:
Structure vs Hardness through the Obfuscation Lens. - Gilad Asharov, Alon Rosen, Gil Segev:
Indistinguishability Obfuscation Does Not Reduce to Structured Languages. - Cyrus Rashtchian:
Bounded Matrix Rigidity and John's Theorem. - Guillaume Lagarde, Guillaume Malod, Sylvain Perifel:
Non-commutative computations: lower bounds and polynomial identity testing. - Arkadev Chattopadhyay, Nikhil S. Mande:
Small Error Versus Unbounded Error Protocols in the NOF Model. - Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V. Vinay:
The Chasm at Depth Four, and Tensor Rank : Old results, new insights. - Vivek Anand T. Kallampally, Raghunath Tewari:
Trading Determinism for Time in Space Bounded Computations. - Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. - Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama:
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. - Suguru Tamaki:
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates. - Toniann Pitassi, Iddo Tzameret:
Algebraic Proof Complexity: Progress, Frontiers and Challenges. - Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. - Jaikumar Radhakrishnan, Swagato Sanyal:
The zero-error randomized query complexity of the pointer function. - Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-Interactive Simulation of Joint Distributions. - Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Low-error two-source extractors for polynomial min-entropy. - Nathanaël Fijalkow:
Lower Bounds for Alternating Online Space Complexity. - Michael Rudow:
Discrete Logarithm and Minimum Circuit Size. - Scott Aaronson:
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. - Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. - Amit Chakrabarti, Sagar Kale:
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics. - Mohammad Taghi Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz:
Bicovering: Covering edges with two small subsets of vertices. - Gillat Kol, Ran Raz, Avishay Tal:
Time-Space Hardness of Learning Sparse Parities. - Gil Cohen:
Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols. - Xin Li:
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors. - Subhash Khot, Rishi Saket:
Approximating CSPs using LP Relaxation. - Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for all CSPs. - Shachar Lovett, Jiapeng Zhang:
On the impossibility of entropy reversal, and its application to zero-knowledge proofs. - Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov:
On the Limits of Gate Elimination. - Dean Doron, Amir Sarid, Amnon Ta-Shma:
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. - Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. - Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf:
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound. - Stasys Jukna:
Tropical Complexity, Sidon Sets, and Dynamic Programming. - Subhash Khot, Dor Minzer, Muli Safra:
On Independent Sets, 2-to-2 Games and Grassmann Graphs. - Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu:
Local Testing for Membership in Lattices. - Subhash Khot, Igor Shinkar:
An Õ(n) Queries Adaptive Tester for Unateness. - Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. - Irit Dinur:
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. - Emanuele Viola, Avi Wigderson:
Local Expanders. - Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra:
Tight Network Topology Dependent Bounds on Rounds of Communication. - Andrej Bogdanov, Siyao Guo, Ilan Komargodski:
Threshold Secret Sharing Requires a Linear Size Alphabet. - Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker:
On the Sensitivity Conjecture for Read-k Formulas. - Deeparnab Chakrabarty, C. Seshadhri:
A Õ(n) Non-Adaptive Tester for Unateness. - Ronen Shaltiel, Jad Silbak:
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. - Christoph Berkholz, Jakob Nordström:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps.