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