All reports in year 2016:

__
TR16-001
| 9th January 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza#### Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

__
TR16-002
| 18th January 2016
__

Ryan Williams#### Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

__
TR16-003
| 2nd December 2015
__

Boris Brimkov, Illya Hicks#### On the logspace shortest path problem

__
TR16-004
| 26th December 2015
__

Dax Enshan Koh#### Further extensions of Clifford circuits and their classical simulation complexities

__
TR16-005
| 22nd January 2016
__

Olaf Beyersdorff, Leroy Chew, Mikolas Janota#### Extension Variables in QBF Resolution

__
TR16-006
| 22nd January 2016
__

Neeraj Kayal, Chandan Saha, Sébastien Tavenas#### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Revisions: 2

__
TR16-007
| 23rd January 2016
__

Guy Kindler#### Property Testing, PCP, andJuntas

Revisions: 1

__
TR16-008
| 26th January 2016
__

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova#### Algorithms from Natural Lower Bounds

__
TR16-009
| 28th January 2016
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Identity Testing for constant-width, and commutative, read-once oblivious ABPs

__
TR16-010
| 28th January 2016
__

Alexander Razborov#### On the Width of Semi-Algebraic Proofs and Algorithms

__
TR16-011
| 27th January 2016
__

Olaf Beyersdorff, Ján Pich#### Understanding Gentzen and Frege systems for QBF

__
TR16-012
| 21st January 2016
__

John Hitchcock, Hadi Shafei#### Autoreducibility of NP-Complete Sets

__
TR16-013
| 12th January 2016
__

Ludwig Staiger#### Bounds on the Kolmogorov complexity function for infinite words

Revisions: 2

__
TR16-014
| 3rd February 2016
__

Gil Cohen, Leonard Schulman#### Extractors for Near Logarithmic Min-Entropy

__
TR16-015
| 4th February 2016
__

Oded Goldreich#### The uniform distribution is complete with respect to testing identity to a fixed distribution

Revisions: 3

__
TR16-016
| 30th January 2016
__

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson#### Doubly infinite separation of quantum information and communication

__
TR16-017
| 24th December 2015
__

Georgios Stamoulis#### Limitations of Linear Programming Techniques for Bounded Color Matchings

__
TR16-018
| 3rd February 2016
__

Kuan Cheng, Xin Li#### Randomness Extraction in $AC^0$ and with Small Locality

Revisions: 7

__
TR16-019
| 5th February 2016
__

Ran Raz#### Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

__
TR16-020
| 8th February 2016
__

Zachary Remscrim#### The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

__
TR16-021
| 11th February 2016
__

Shachar Lovett, Jiapeng Zhang#### Noisy Population Recovery from Unknown Noise

__
TR16-022
| 22nd February 2016
__

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

__
TR16-023
| 23rd February 2016
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### How to Share a Secret, Infinitely

Revisions: 4

__
TR16-024
| 22nd February 2016
__

Patrick Scharpfenecker, Jacobo Toran#### Solution-Graphs of Boolean Formulas and Isomorphism

__
TR16-025
| 26th February 2016
__

Shachar Lovett#### The Fourier structure of low degree polynomials

Revisions: 1

__
TR16-026
| 20th February 2016
__

Anindya De, Michael Saks, Sijian Tang#### Noisy population recovery in polynomial time

__
TR16-027
| 10th February 2016
__

Sagnik Mukhopadhyay#### Tribes Is Hard in the Message Passing Model

Revisions: 1

__
TR16-028
| 29th February 2016
__

Olaf Beyersdorff, Joshua Blinkhorn#### Dependency Schemes in QBF Calculi:Semantics and Soundness

Revisions: 1

__
TR16-029
| 7th March 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### New hardness results for graph and hypergraph colorings

__
TR16-030
| 7th March 2016
__

Gil Cohen#### Non-Malleable Extractors with Logarithmic Seeds

__
TR16-031
| 7th March 2016
__

Titus Dose#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

__
TR16-032
| 10th March 2016
__

Roei Tell#### A Note on Tolerant Testing with One-Sided Error

__
TR16-033
| 10th March 2016
__

Venkatesan Guruswami, Jaikumar Radhakrishnan#### Tight bounds for communication assisted agreement distillation

__
TR16-034
| 7th March 2016
__

Mohamed El Halaby#### On the Computational Complexity of MaxSAT

Revisions: 1

__
TR16-035
| 11th March 2016
__

Irit Dinur, Or Meir#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

__
TR16-036
| 13th March 2016
__

Eshan Chattopadhyay, Xin Li#### Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols

Revisions: 3

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
TR16-038
| 15th March 2016
__

Meena Mahajan, Nitin Saurabh#### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

__
TR16-039
| 15th March 2016
__

Adam Bouland, Laura Mancinska, Xue Zhang#### Complexity Classification of Two-Qubit Commuting Hamiltonians

__
TR16-040
| 16th March 2016
__

Baris Aydinlioglu, Eric Bach#### Affine Relativization: Unifying the Algebrization and Relativization Barriers

Revisions: 3

__
TR16-041
| 17th March 2016
__

Johan Håstad#### An average-case depth hierarchy theorem for higher depth

__
TR16-042
| 19th March 2016
__

Oded Goldreich, Tom Gur#### Universal Locally Testable Codes

Revisions: 2

__
TR16-043
| 23rd February 2016
__

Mikolas Janota#### On Q-Resolution and CDCL QBF Solving

__
TR16-044
| 21st March 2016
__

Kaave Hosseini, Shachar Lovett#### Structure of protocols for XOR functions

Revisions: 1

__
TR16-045
| 22nd March 2016
__

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi#### Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

__
TR16-046
| 23rd March 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

Revisions: 2

__
TR16-047
| 23rd March 2016
__

Mohammad Bavarian, Thomas Vidick, Henry Yuen#### Parallel repetition via fortification: analytic view and the quantum case

__
TR16-048
| 11th March 2016
__

Olaf Beyersdorff, Leroy Chew, Renate Schmidt, Martin Suda#### Lifting QBF Resolution Calculi to DQBF

__
TR16-049
| 28th March 2016
__

Cynthia Dwork, Moni Naor, Guy Rothblum#### Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

__
TR16-050
| 31st March 2016
__

Roei Tell#### Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

Revisions: 1

__
TR16-051
| 7th April 2016
__

Ronald Cramer, Chaoping Xing, chen yuan#### On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 4

__
TR16-052
| 7th April 2016
__

Gil Cohen#### Making the Most of Advice: New Correlation Breakers and Their Applications

Revisions: 1

__
TR16-053
| 6th April 2016
__

Jiawei Gao, Russell Impagliazzo#### Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

__
TR16-054
| 11th April 2016
__

Omri Weinstein, Huacheng Yu#### Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

__
TR16-055
| 11th April 2016
__

Tim Roughgarden, Omri Weinstein#### On the Communication Complexity of Approximate Fixed Points

__
TR16-056
| 8th April 2016
__

Shafi Goldwasser, Dhiraj Holden#### On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

__
TR16-057
| 11th April 2016
__

Ilario Bonacina#### Total space in Resolution is at least width squared

__
TR16-058
| 12th April 2016
__

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin#### A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

__
TR16-059
| 14th April 2016
__

Alon Rosen, Gil Segev, Ido Shahaf#### Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 2

__
TR16-060
| 15th April 2016
__

Henry Yuen#### A parallel repetition theorem for all entangled games

__
TR16-061
| 17th April 2016
__

Omer Reingold, Ron Rothblum, Guy Rothblum#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 2

__
TR16-062
| 18th April 2016
__

Avishay Tal#### On The Sensitivity Conjecture

__
TR16-063
| 18th April 2016
__

Pavel Hubacek, Eylon Yogev#### Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Revisions: 1

__
TR16-064
| 19th April 2016
__

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman#### Exponential Lower Bounds for Monotone Span Programs

__
TR16-065
| 18th April 2016
__

Xi Chen, Yu Cheng, Bo Tang#### A Note on Teaching for VC Classes

Revisions: 1

__
TR16-066
| 19th April 2016
__

Oded Goldreich, Maya Leshkowitz#### On Emulating Interactive Proofs with Public Coins

__
TR16-067
| 20th April 2016
__

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani#### Pebbling Meets Coloring : Reversible Pebble Game On Trees

__
TR16-068
| 28th April 2016
__

Prahladh Harsha, Srikanth Srinivasan#### On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR16-070
| 24th April 2016
__

Mika Göös, Rahul Jain, Thomas Watson#### Extension Complexity of Independent Set Polytopes

Revisions: 1

__
TR16-071
| 1st May 2016
__

Jan Krajicek, Igor Carboni Oliveira#### Unprovability of circuit upper bounds in Cook's theory PV

__
TR16-072
| 4th May 2016
__

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha#### Separations in communication complexity using cheat sheets and information complexity

__
TR16-073
| 7th May 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1
,
Comments: 1

__
TR16-074
| 9th May 2016
__

Ilias Diakonikolas, Daniel Kane#### A New Approach for Testing Properties of Discrete Distributions

__
TR16-075
| 9th May 2016
__

Mark Bun, Justin Thaler#### Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

__
TR16-076
| 27th April 2016
__

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

__
TR16-077
| 12th May 2016
__

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai#### Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

__
TR16-078
| 9th May 2016
__

Gregory Valiant, Paul Valiant#### Information Theoretically Secure Databases

__
TR16-079
| 2nd May 2016
__

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli#### Sum-of-squares hierarchy lower bounds for symmetric formulations

__
TR16-080
| 18th May 2016
__

Oded Goldreich#### Reducing testing affine spaces to testing linearity

Revisions: 4

__
TR16-081
| 20th May 2016
__

Alexander A. Sherstov#### Compressing interactive communication under product distributions

__
TR16-082
| 22nd May 2016
__

Benny Applebaum, Pavel Raykov#### Fast Pseudorandom Functions Based on Expander Graphs

__
TR16-083
| 23rd May 2016
__

Nader Bshouty#### Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets

__
TR16-084
| 23rd May 2016
__

Shalev Ben-David#### Low-Sensitivity Functions from Unambiguous Certificates

__
TR16-085
| 28th May 2016
__

Shiteng Chen, Periklis Papakonstantinou#### Depth-reduction for composites

__
TR16-086
| 29th May 2016
__

Noga Alon, Klim Efremenko, Benny Sudakov#### Testing Equality in Communication Graphs

Revisions: 1

__
TR16-087
| 30th May 2016
__

Shalev Ben-David, Robin Kothari#### Randomized query complexity of sabotaged and composed functions

__
TR16-088
| 1st June 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Explicit two-source extractors for near-logarithmic min-entropy

__
TR16-089
| 2nd June 2016
__

Vikraman Arvind, Partha Mukhopadhyay, Raja S#### Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

__
TR16-090
| 27th May 2016
__

Bernhard Haeupler, Ameya Velingker#### Bridging the Capacity Gap Between Interactive and One-Way Communication

__
TR16-091
| 3rd June 2016
__

Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan#### Structure vs Hardness through the Obfuscation Lens

Revisions: 3

__
TR16-092
| 3rd June 2016
__

Gilad Asharov, Alon Rosen, Gil Segev#### Indistinguishability Obfuscation Does Not Reduce to Structured Languages

Revisions: 1

__
TR16-093
| 4th June 2016
__

Cyrus Rashtchian#### Bounded Matrix Rigidity and John's Theorem

__
TR16-094
| 6th June 2016
__

Guillaume Lagarde, Guillaume Malod#### Non-commutative computations: lower bounds and polynomial identity testing

Comments: 1

__
TR16-095
| 7th June 2016
__

Arkadev Chattopadhyay, Nikhil Mande#### Small Error Versus Unbounded Error Protocols in the NOF Model

Revisions: 1
,
Comments: 1

__
TR16-096
| 14th June 2016
__

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

__
TR16-097
| 15th June 2016
__

Vivek Anand T Kallampally, Raghunath Tewari#### Trading Determinism for Time in Space Bounded Computations

__
TR16-098
| 16th June 2016
__

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson#### Proof Complexity Lower Bounds from Algebraic Circuit Complexity

__
TR16-099
| 13th June 2016
__

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama#### Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

__
TR16-100
| 27th June 2016
__

Suguru Tamaki#### A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

__
TR16-101
| 1st July 2016
__

Toniann Pitassi, Iddo Tzameret#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

__
TR16-102
| 4th July 2016
__

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola#### Bounded independence vs. moduli

Revisions: 1

__
TR16-103
| 6th July 2016
__

Jaikumar Radhakrishnan, Swagato Sanyal#### The zero-error randomized query complexity of the pointer function.

__
TR16-104
| 14th July 2016
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Decidability of Non-Interactive Simulation of Joint Distributions

__
TR16-105
| 13th July 2016
__

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

__
TR16-106
| 15th July 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Low-error two-source extractors for polynomial min-entropy

Revisions: 1

__
TR16-107
| 17th July 2016
__

Nathanael Fijalkow#### Lower Bounds for Alternating Online Space Complexity

Revisions: 1

__
TR16-108
| 16th July 2016
__

Michael Rudow#### Discrete Logarithm and Minimum Circuit Size

__
TR16-109
| 18th July 2016
__

Scott Aaronson#### The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

__
TR16-110
| 19th July 2016
__

Alexander Golovnev, Oded Regev, Omri Weinstein#### The Minrank of Random Graphs

Revisions: 1

__
TR16-111
| 20th July 2016
__

Amit Chakrabarti, Sagar Kale#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

__
TR16-112
| 18th July 2016
__

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz#### Bicovering: Covering edges with two small subsets of vertices

__
TR16-113
| 22nd July 2016
__

Gillat Kol, Ran Raz, Avishay Tal#### Time-Space Hardness of Learning Sparse Parities

__
TR16-114
| 30th July 2016
__

Gil Cohen#### Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

Revisions: 1

__
TR16-115
| 30th July 2016
__

Xin Li#### Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors

__
TR16-116
| 26th July 2016
__

Subhash Khot, Rishi Saket#### Approximating CSPs using LP Relaxation

__
TR16-117
| 31st July 2016
__

Mrinalkanti Ghosh, Madhur Tulsiani#### From Weak to Strong LP Gaps for all CSPs

Revisions: 1

__
TR16-118
| 31st July 2016
__

Shachar Lovett, Jiapeng Zhang#### On the impossibility of entropy reversal, and its application to zero-knowledge proofs

__
TR16-119
| 1st August 2016
__

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov#### On the Limits of Gate Elimination

Revisions: 1

__
TR16-120
| 1st August 2016
__

Dean Doron, Amir Sarid, Amnon Ta-Shma#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

__
TR16-121
| 4th August 2016
__

Mark Bun, Justin Thaler#### Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR16-123
| 11th August 2016
__

Stasys Jukna#### Tropical Complexity, Sidon Sets, and Dynamic Programming

__
TR16-124
| 12th August 2016
__

Subhash Khot#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Revisions: 1
,
Comments: 1

__
TR16-125
| 31st July 2016
__

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu#### Local Testing for Membership in Lattices

__
TR16-126
| 8th August 2016
__

Subhash Khot, Igor Shinkar#### An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

__
TR16-127
| 12th August 2016
__

Timothy Gowers, Emanuele Viola#### The multiparty communication complexity of interleaved group products

__
TR16-128
| 13th August 2016
__

Irit Dinur#### Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

__
TR16-129
| 16th August 2016
__

Emanuele Viola, Avi Wigderson#### Local Expanders

Revisions: 1

__
TR16-130
| 11th August 2016
__

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra#### Tight Network Topology Dependent Bounds on Rounds of Communication

__
TR16-131
| 21st August 2016
__

Andrej Bogdanov, Siyao Guo, Ilan Komargodski#### Threshold Secret Sharing Requires a Linear Size Alphabet

__
TR16-132
| 23rd August 2016
__

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker#### On the Sensitivity Conjecture for Read-k Formulas

__
TR16-133
| 25th August 2016
__

Deeparnab Chakrabarty, C. Seshadhri#### A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness

Revisions: 1

__
TR16-134
| 29th August 2016
__

Ronen Shaltiel, Jad Silbak#### Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

Revisions: 1

__
TR16-135
| 31st August 2016
__

Christoph Berkholz, Jakob Nordström#### Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps

__
TR16-136
| 31st August 2016
__

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer#### Testing k-Monotonicity

Revisions: 1

__
TR16-137
| 3rd September 2016
__

Mrinal Kumar, Ramprasad Saptharishi#### Finer separations between shallow arithmetic circuits

__
TR16-138
| 3rd September 2016
__

Alexander A. Sherstov#### On multiparty communication with large versus unbounded error

__
TR16-139
| 8th September 2016
__

Ludwig Staiger#### Exact constructive and computable dimensions

Revisions: 1

__
TR16-140
| 9th September 2016
__

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan#### On SZK and PP

Revisions: 3

__
TR16-141
| 11th September 2016
__

Ryan O'Donnell#### SOS is not obviously automatizable, even approximately

Revisions: 1

__
TR16-142
| 11th September 2016
__

Jason Li, Ryan O'Donnell#### Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

__
TR16-143
| 15th September 2016
__

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan#### An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

__
TR16-144
| 15th September 2016
__

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky#### Expander Construction in VNC${}^1$

Revisions: 2

__
TR16-145
| 16th September 2016
__

Markus Bläser, Gorav Jindal, Anurag Pandey#### Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

Revisions: 2

__
TR16-146
| 18th September 2016
__

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini#### Computability Theory of Closed Timelike Curves

__
TR16-147
| 19th September 2016
__

Ryan O'Donnell, A. C. Cem Say#### The weakness of CTC qubits and the power of approximate counting

Revisions: 1

__
TR16-148
| 23rd September 2016
__

Thomas Watson#### Communication Complexity with Small Advantage

Revisions: 1

__
TR16-149
| 23rd September 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### A security analysis of Probabilistically Checkable Proofs

Comments: 1

__
TR16-150
| 23rd September 2016
__

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez#### Streaming Communication Protocols

__
TR16-151
| 26th September 2016
__

Amir Yehudayoff#### Pointer chasing via triangular discrimination

__
TR16-152
| 27th September 2016
__

Oded Goldreich#### Deconstructing 1-local expanders

Revisions: 1

__
TR16-153
| 28th September 2016
__

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah#### Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials

Revisions: 3

__
TR16-154
| 21st September 2016
__

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor#### Logical Induction

__
TR16-155
| 10th October 2016
__

Vaibhav Krishan, Nutan Limaye#### Isolation Lemma for Directed Reachability and NL vs. L

__
TR16-156
| 12th October 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

__
TR16-157
| 13th October 2016
__

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran#### Parameterized Complexity of Small Weight Automorphisms

__
TR16-158
| 9th October 2016
__

Alexander Kulikov, Vladimir Podolskii#### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

__
TR16-159
| 18th October 2016
__

Daniel Grier, Luke Schaeffer#### New Hardness Results for the Permanent Using Linear Optics

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR16-161
| 26th October 2016
__

Shachar Lovett, Jiapeng Zhang#### Robust sensitivity

Revisions: 1

__
TR16-162
| 18th October 2016
__

Joshua Grochow#### NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

__
TR16-163
| 25th October 2016
__

Matthew Hastings#### Local Maxima and Improved Exact Algorithm for MAX-2-SAT

__
TR16-164
| 25th October 2016
__

Andreas Krebs, Meena Mahajan, Anil Shukla#### Relating two width measures for resolution proofs

__
TR16-165
| 30th October 2016
__

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Lower Bounds for Elimination via Weak Regularity

__
TR16-166
| 1st November 2016
__

Mark Braverman, Ran Gelles, Michael A. Yitayew#### Optimal Resilience for Short-Circuit Noise in Formulas

Revisions: 1

__
TR16-167
| 1st November 2016
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

__
TR16-168
| 2nd November 2016
__

Eric Blais, Clement Canonne, Tom Gur#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

__
TR16-169
| 3rd November 2016
__

Elad Haramaty, Chin Ho Lee, Emanuele Viola#### Bounded independence plus noise fools products

__
TR16-170
| 3rd November 2016
__

Thomas Watson#### Communication Complexity of Statistical Distance

Revisions: 1

__
TR16-171
| 3rd November 2016
__

Daniel Minahan, Ilya Volkovich#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

__
TR16-172
| 3rd November 2016
__

William Hoza, Adam Klivans#### Preserving Randomness for Adaptive Algorithms

Revisions: 4

__
TR16-173
| 5th November 2016
__

Egor Klenin, Alexander Kozachinsky#### One-sided error communication complexity of Gap Hamming Distance

Revisions: 2

__
TR16-174
| 7th November 2016
__

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev#### Linear Sketching over $\mathbb F_2$

Revisions: 5
,
Comments: 2

__
TR16-175
| 8th November 2016
__

Pavel Pudlak, Neil Thapen#### Random resolution refutations

Revisions: 2

__
TR16-176
| 9th November 2016
__

Venkata Gandikota, Badih Ghazi, Elena Grigorescu#### NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

__
TR16-177
| 11th November 2016
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Revisions: 1

__
TR16-178
| 11th November 2016
__

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price#### Collision-based Testers are Optimal for Uniformity and Closeness

Comments: 1

__
TR16-179
| 15th November 2016
__

Avishay Tal#### Computing Requires Larger Formulas than Approximating

__
TR16-180
| 15th November 2016
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions

__
TR16-181
| 15th November 2016
__

Avishay Tal#### The Bipartite Formula Complexity of Inner-Product is Quadratic

__
TR16-182
| 14th November 2016
__

Rohit Gurjar, Thomas Thierauf#### Linear Matroid Intersection is in quasi-NC

__
TR16-183
| 16th November 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 2

__
TR16-184
| 16th November 2016
__

Alexander Razborov#### On Space and Depth in Resolution

__
TR16-185
| 18th November 2016
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere

Revisions: 1

__
TR16-186
| 19th November 2016
__

Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh#### A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation

__
TR16-187
| 21st November 2016
__

morris yau#### Almost Cubic Bound for Depth Three Circuits in VP

Revisions: 3

__
TR16-188
| 21st November 2016
__

Toniann Pitassi, Robert Robere#### Strongly Exponential Lower Bounds for Monotone Computation

__
TR16-189
| 21st November 2016
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for 2-query LCCs over large alphabet

__
TR16-190
| 21st November 2016
__

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li#### Trading information complexity for error

__
TR16-191
| 24th November 2016
__

Roei Tell#### Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Revisions: 3

__
TR16-192
| 25th November 2016
__

Oded Goldreich, Tom Gur#### Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revisions: 2
,
Comments: 1

__
TR16-193
| 22nd November 2016
__

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S#### Identity Testing for +-Regular Noncommutative Arithmetic Circuits

__
TR16-194
| 4th December 2016
__

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan#### The Optimality of Correlated Sampling

Revisions: 1

__
TR16-195
| 19th November 2016
__

Pasin Manurangsi#### Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Revisions: 1

__
TR16-196
| 5th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Constructions in Subexponential Time

__
TR16-197
| 7th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

__
TR16-198
| 14th December 2016
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Towards a Proof of the 2-to-1 Games Conjecture?

__
TR16-199
| 15th December 2016
__

Pavel Hubacek, Moni Naor, Eylon Yogev#### The Journey from NP to TFNP Hardness

__
TR16-200
| 18th December 2016
__

Scott Aaronson, Lijie Chen#### Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

__
TR16-201
| 19th December 2016
__

Eric Blais, Yuichi Yoshida#### A Characterization of Constant-Sample Testable Properties

__
TR16-202
| 19th December 2016
__

Dmitry Sokolov#### Dag-like Communication and Its Applications

Revisions: 1

__
TR16-203
| 21st December 2016
__

Christoph Berkholz, Jakob Nordström#### Supercritical Space-Width Trade-offs for Resolution

__
TR16-204
| 20th December 2016
__

Prahladh Harsha, Srikanth Srinivasan#### Robust Multiplication-based Tests for Reed-Muller Codes

__
TR16-205
| 22nd December 2016
__

Amey Bhangale, Irit Dinur, Inbal Livni Navon#### Cube vs. Cube Low Degree Test

__
TR16-206
| 24th December 2016
__

Benjamin Rossman#### An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

Ryan Williams

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,

$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ...
more >>>

Boris Brimkov, Illya Hicks

In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex ... more >>>

Dax Enshan Koh

Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations that might just be slightly different, lead to ... more >>>

Olaf Beyersdorff, Leroy Chew, Mikolas Janota

We investigate two QBF resolution systems that use extension variables: weak extended Q-resolution, where the extension variables are quantified at the innermost level, and extended Q-resolution, where the extension variables can be placed inside the quantifier prefix. These systems have been considered previously by Jussila et al. '07 who ... more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\SPS$) arithmetic circuit computing an explicit multilinear polynomial in $n$ variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson.

more >>>Guy Kindler

The first part of this thesis strengthens the low-error PCP

characterization of NP, coming closer to the upper limit of the

conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over

$n$ variables can be tested for the property of depending ...
more >>>

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

Alexander Razborov

In this paper we initiate the study of width in semi-algebraic proof systems

and various cut-based procedures in integer programming. We focus on two

important systems: Gomory-Chv\'atal cutting planes and

Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for

proving width lower bounds and apply them to random $k$-CNFs and several ...
more >>>

Olaf Beyersdorff, Ján Pich

Recently Beyersdorff, Bonacina, and Chew (ITCS'16) introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the new extended Frege system from Beyersdorff et al., denoted EF+$\forall$red, which is a ... more >>>

John Hitchcock, Hadi Shafei

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>

Ludwig Staiger

The Kolmogorov complexity function of an infinite word $\xi$ maps a natural

number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We

investigate the maximally achievable complexity function if $\xi$ is taken

from a constructively describable set of infinite words. Here we are

interested ...
more >>>

Gil Cohen, Leonard Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an ... more >>>

Oded Goldreich

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances ... more >>>

Georgios Stamoulis

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>

Kuan Cheng, Xin Li

We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>>

Ran Raz

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

Zachary Remscrim

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the ... more >>>

Shachar Lovett, Jiapeng Zhang

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best ... more >>>

Patrick Scharpfenecker, Jacobo Toran

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

Shachar Lovett

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

Anindya De, Michael Saks, Sijian Tang

In the noisy population recovery problem of Dvir et al., the goal is to learn

an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,

a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with

more >>>

Sagnik Mukhopadhyay

We consider the point-to-point message passing model of communication in which there are $k$ processors

with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying

undirected graph and has access to private random coins. An edge of the graph is a private channel ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn

We study the parametrization of QBF resolution calculi by dependency schemes. One of the main problems in this area is to understand for which dependency schemes the resulting calculi are sound. Towards this end we propose a semantic framework for variable independence based on `exhibition' by QBF models, and use ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

Gil Cohen

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>

Titus Dose

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>

Roei Tell

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number ... more >>>

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

Mohamed El Halaby

Given a Boolean formula in Conjunctive Normal Form (CNF) $\phi=S \cup H$, the MaxSAT (Maximum Satisfiability) problem asks for an assignment that satisfies the maximum number of clauses in $\phi$. Due to the good performance of current MaxSAT solvers, many real-life optimization problems such as scheduling can be solved efficiently ... more >>>

Irit Dinur, Or Meir

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).

For the first ... more >>>

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Meena Mahajan, Nitin Saurabh

We provide a list of new natural VNP-intermediate polynomial

families, based on basic (combinatorial) NP-complete problems that

are complete under \emph{parsimonious} reductions. Over finite

fields, these families are in VNP, and under the plausible

hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under

oracle-circuit reductions) nor in VP. Prior to ...
more >>>

Adam Bouland, Laura Mancinska, Xue Zhang

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian $H$ which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

Baris Aydinlioglu, Eric Bach

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>

Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula ...
more >>>

Oded Goldreich, Tom Gur

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>

Mikolas Janota

Q-resolution and its variations provide the underlying proof

systems for the DPLL-based QBF solvers. While (long-distance) Q-resolution

models a conflict driven clause learning (CDCL) QBF solver, it is not

known whether the inverse is also true. This paper provides a negative

answer to this question. This contrasts with SAT solving, ...
more >>>

Kaave Hosseini, Shachar Lovett

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.

We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.

This relies on a novel technique ...
more >>>

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial ... more >>>

Olaf Beyersdorff, Leroy Chew, Renate Schmidt, Martin Suda

We examine the existing Resolution systems for quantified Boolean formulas (QBF) and answer the question which of these calculi can be lifted to the more powerful Dependency QBFs (DQBF). An interesting picture emerges: While for QBF we have the strict chain of proof systems Q-Resolution < IR-calc < IRM-calc, the ... more >>>

Cynthia Dwork, Moni Naor, Guy Rothblum

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

Roei Tell

We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about $S$ is estimates of the density of $S$ in adaptively chosen subsets of ... more >>>

Ronald Cramer, Chaoping Xing, chen yuan

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a ... more >>>

Gil Cohen

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>>

Jiawei Gao, Russell Impagliazzo

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

Omri Weinstein, Huacheng Yu

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic

data structure problems. We introduce a new randomized nondeterministic four-party communication model

that enables "accelerated", error-preserving simulations of dynamic data structures.

We use this technique to prove an $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe ... more >>>

Tim Roughgarden, Omri Weinstein

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition

of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an

exponential (in $n$) lower bound on the deterministic ...
more >>>

Shafi Goldwasser, Dhiraj Holden

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.

In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ...
more >>>

Ilario Bonacina

Given an unsatisfiable $k$-CNF formula $\phi$ we consider two complexity measures in Resolution: width and total space. The width is the minimal $W$ such that there exists a Resolution refutation of $\phi$ with clauses of at most $W$ literals. The total space is the minimal size $T$ of a memory ... more >>>

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.

This yields a nearly tight ...
more >>>

Alon Rosen, Gil Segev, Ido Shahaf

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

Henry Yuen

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.

...
more >>>

Omer Reingold, Ron Rothblum, Guy Rothblum

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

Avishay Tal

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>

Pavel Hubacek, Eylon Yogev

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

Xi Chen, Yu Cheng, Bo Tang

In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of $C \subseteq \{0,1\}^n$, denoted by $VCD(C)$, is the maximum size of a shattered subset of $[n]$, where $Y\subseteq [n]$ is shattered if for every binary string $\vec{b}$ of length $|Y|$, ... more >>>

Oded Goldreich, Maya Leshkowitz

The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.

Specifically, the possible messages are essentially clustered according to ...
more >>>

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>

Mika Göös, Rahul Jain, Thomas Watson

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

Jan Krajicek, Igor Carboni Oliveira

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.

PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ...
more >>>

Ilias Diakonikolas, Daniel Kane

We study problems in distribution property testing:

Given sample access to one or more unknown discrete distributions,

we want to determine whether they have some global property or are $\epsilon$-far

from having the property in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').

In this work, we give a ...
more >>>

Mark Bun, Justin Thaler

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

Gregory Valiant, Paul Valiant

We introduce the notion of a database system that is information theoretically "secure in between accesses"--a database system with the properties that 1) users can efficiently access their data, and 2) while a user is not accessing their data, the user's information is information theoretically secure to malicious agents, provided ... more >>>

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of ``well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>

Oded Goldreich

We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$

is the indicator function of an $(\ell-k)$-dimensional affine space.

An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky ({\em SIDMA}, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, {\em JCSS}, 1993) ...
more >>>

Alexander A. Sherstov

We study the problem of compressing interactive communication to its

information content $I$, defined as the amount of information that the

participants learn about each other's inputs. We focus on the case when

the participants' inputs are distributed independently and show how to

compress the communication to $O(I\log^{2}I)$ bits, with ...
more >>>

Benny Applebaum, Pavel Raykov

We present direct constructions of pseudorandom function (PRF) families based on Goldreich's one-way function. Roughly speaking, we assume that non-trivial local mappings $f:\{0,1\}^n\rightarrow \{0,1\}^m$ whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak ... more >>>

Nader Bshouty

Derandomization of Chernoff bound with union bound is already proven in many papers.

We here give another explicit version of it that obtains a construction of size

that is arbitrary close to the probabilistic nonconstructive size.

We apply this to give a new simple polynomial time constructions of

almost $k$-wise ...
more >>>

Shalev Ben-David

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>>

Shiteng Chen, Periklis Papakonstantinou

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... more >>>

Noga Alon, Klim Efremenko, Benny Sudakov

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose

that on each vertex of the graph there is a player having an $n$-bit

string. Each player is allowed to communicate with its neighbors according

to an agreed communication protocol, and the players must decide,

deterministically, if their inputs ...
more >>>

Shalev Ben-David, Robin Kothari

We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Raja S

In this paper we show that polynomial identity testing for

noncommutative circuits of size $s$, computing a polynomial in

$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm

with running time polynomial in $s$ and $n$. This answers a question

that has been open for over ten years.

The ... more >>>

Bernhard Haeupler, Ameya Velingker

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan

Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, ... more >>>

Gilad Asharov, Alon Rosen, Gil Segev

We prove that indistinguishability obfuscation (iO) and one-way functions do not naturally reduce to any language within $NP \cap coNP$. This is proved within the framework introduced by Asharov and Segev (FOCS '15) that captures the vast majority of techniques that have been used so far in iO-based constructions.

Our ... more >>>

Cyrus Rashtchian

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

Guillaume Lagarde, Guillaume Malod

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-

alize algebraic branching programs (ABP). This model is called unambiguous because it captures the

polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-

morphic).

We ...
more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

Vivek Anand T Kallampally, Raghunath Tewari

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.

...
more >>>

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ...
more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ is weighted symmetric if there exist a function $g: \mathbb{Z} \to \{0,1\}$ and integers $w_0, w_1, \ldots, w_n$ such that $f(x_1,\ldots,x_n) = g(w_0+\sum_{i=1}^n w_i x_i)$ holds.

In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, ... more >>>

Suguru Tamaki

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

Toniann Pitassi, Iddo Tzameret

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Let $k=k(n)$ be the largest integer such that there

exists a $k$-wise uniform distribution over $\zo^n$ that

is supported on the set $S_m := \{x \in \zo^n : \sum_i

x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We

show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ...
more >>>

Jaikumar Radhakrishnan, Swagato Sanyal

The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson

\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently

been used to prove separation results among various measures of

complexity such as deterministic, randomized and quantum query

complexities, exact and approximate polynomial degrees, etc. In

particular, the widest possible (quadratic) separations between

deterministic and zero-error ...
more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

We construct explicit two-source extractors for $n$ bit sources,

requiring $n^\alpha$ min-entropy and having error $2^{-n^\beta}$,

for some constants $0 < \alpha,\beta < 1$. Previously, constructions

for exponentially small error required either min-entropy

$0.49n$ \cite{Bou05} or three sources \cite{Li15}. The construction

combines somewhere-random condensers based on the Incidence

Theorem \cite{Zuc06,Li11}, ...
more >>>

Nathanael Fijalkow

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,

represented by a machine which scans the input exactly once from left to right.

In this paper, we study alternating machines as introduced by ...
more >>>

Michael Rudow

This paper shows that the Discrete Logarithm Problem is in ZPP^(MCSP) (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPP^(MCSP) Allender et al. (2006). In doing so, this paper helps classify the relative difficulty of the Minimum ... more >>>

Scott Aaronson

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

Alexander Golovnev, Oded Regev, Omri Weinstein

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

Amit Chakrabarti, Sagar Kale

We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a ...
more >>>

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

Gillat Kol, Ran Raz, Avishay Tal

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

Gil Cohen

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>

Xin Li

In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are:

(1) An explicit seeded non-malleable extractor with error $\epsilon$ and seed length $d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon))$, that supports min-entropy $k=\Omega(d)$ and outputs $\Omega(k)$ bits. Combined with ... more >>>

Subhash Khot, Rishi Saket

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

Mrinalkanti Ghosh, Madhur Tulsiani

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $\Omega\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ... more >>>

Shachar Lovett, Jiapeng Zhang

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. ... more >>>

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

Dean Doron, Amir Sarid, Amnon Ta-Shma

Approximating the eigenvalues of a Hermitian operator can be solved

by a quantum logspace algorithm. We introduce the problem of

approximating the eigenvalues of a given matrix in the context of

classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a

certain range of ...
more >>>

Mark Bun, Justin Thaler

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

Stasys Jukna

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of 1s. Jerrum and Snir [JACM 29 (1982), pp. 874-897] proved that tropical circuit complexity of homogeneous problems ... more >>>

Subhash Khot

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about

Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in

a certain non-standard sense. A reduction that is sound in this non-standard sense

implies that ...
more >>>

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>>

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.

more >>>

Timothy Gowers, Emanuele Viola

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on

its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of

elements from the group $G=\text{SL}(2,q)$. The parties

are promised that the interleaved product $a_{11}\dots

a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is

equal either to the identity $e$ or to some other fixed

element $g\in G$. Their goal is ...
more >>>

Irit Dinur

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>

Emanuele Viola, Avi Wigderson

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

Andrej Bogdanov, Siyao Guo, Ilan Komargodski

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>

Deeparnab Chakrabarty, C. Seshadhri

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.

Ronen Shaltiel, Jad Silbak

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

Christoph Berkholz, Jakob Nordström

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by ... more >>>

Alexander A. Sherstov

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

Ludwig Staiger

In this paper we derive several results which generalise the constructive

dimension of (sets of) infinite strings to the case of exact dimension. We

start with proving a martingale characterisation of exact Hausdorff

dimension. Then using semi-computable super-martingales we introduce the

notion of exact constructive dimension ...
more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Ryan O'Donnell

Suppose we want to minimize a polynomial $p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints $q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include $x_i^2 \leq 1$ for all $1 \leq i \leq ... more >>>

Jason Li, Ryan O'Donnell

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>>

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [Annals of Mathematics, 2002], and show that this analysis can be formalized in the bounded-arithmetic system $VNC^1$ (corresponding to the ``$NC^1$ reasoning''). As a corollary, we prove the ... more >>>

Markus Bläser, Gorav Jindal, Anurag Pandey

We consider the problem of commutative rank computation of a given matrix space, $\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is $n$, subsumes problems such as testing perfect matching in graphs ... more >>>

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

Ryan O'Donnell, A. C. Cem Say

We present two results in structural complexity theory concerned with the following interrelated

topics: computation with postselection/restarting, closed timelike curves (CTCs), and

approximate counting. The first result is a new characterization of the lesser known complexity

class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ...
more >>>

Thomas Watson

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

Amir Yehudayoff

We prove an essentially sharp $\tilde\Omega(n/k)$ lower bound on the $k$-round distributional complexity of the $k$-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson's $\tilde \Omega(n/k^2)$ lower bound. A key part of the proof is using triangular discrimination instead ... more >>>

Oded Goldreich

Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$.

more >>>

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

The power symmetric polynomial on $n$ variables of degree $d$ is defined as

$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers

of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by

...
more >>>

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running ... more >>>

Vaibhav Krishan, Nutan Limaye

In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

Alexander Kulikov, Vladimir Podolskii

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

Daniel Grier, Luke Schaeffer

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

Shachar Lovett, Jiapeng Zhang

The sensitivity conjecture is one of the central open problems in boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a boolean function to moments of its sensitivity. We prove this ... more >>>

Joshua Grochow

Mahaney's Theorem states that, assuming P $\neq$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>

Matthew Hastings

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima hat an instance of MAX-2-SAT can have. We give upper bounds in both the sparse ... more >>>

Andreas Krebs, Meena Mahajan, Anil Shukla

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, ... more >>>

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>

Mark Braverman, Ran Gelles, Michael A. Yitayew

We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

Eric Blais, Clement Canonne, Tom Gur

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

Elad Haramaty, Chin Ho Lee, Emanuele Viola

Let $D$ be a $b$-wise independent distribution over

$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over

$\{0,1\}^m$ where the bits are independent and each bit is 1

with probability $\eta/2$. We study which tests $f \colon

\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,

$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ...
more >>>

Thomas Watson

We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there ... more >>>

Daniel Minahan, Ilya Volkovich

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the

operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ...
more >>>

William Hoza, Adam Klivans

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>

Egor Klenin, Alexander Kozachinsky

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where ... more >>>

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

Pavel Pudlak, Neil Thapen

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the ... more >>>

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

We study the fundamental problems of (i) uniformity testing of a discrete distribution,

and (ii) closeness testing between two discrete distributions with bounded $\ell_2$-norm.

These problems have been extensively studied in distribution testing

and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}.

In this work, we show ... more >>>

Avishay Tal

A de Morgan formula over Boolean variables $x_1, \ldots, x_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that ... more >>>

Eshan Chattopadhyay, Xin Li

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>>

Avishay Tal

A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product ... more >>>

Rohit Gurjar, Thomas Thierauf

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>>

Alexander Razborov

We show that the total space in resolution, as well as in any other reasonable

proof system, is equal (up to a polynomial and $(\log n)^{O(1)}$ factors) to

the minimum refutation depth. In particular, all these variants of total space

are equivalent in this sense. The same conclusion holds for ...
more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh

The advent of data science has spurred interest in estimating properties of discrete distributions over large alphabets. Fundamental symmetric properties such as support size, support coverage, entropy, and proximity to uniformity, received most attention, with each property estimated using a different technique and often intricate analysis tools.

Motivated by the ... more >>>

morris yau

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$

on $N = \Theta(n polylog(n))$

variables with degree $N$ being in VP such that every

$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.

We ...
more >>>

Toniann Pitassi, Robert Robere

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

Arnab Bhattacharyya, Sivakanth Gopi

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.

We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ...
more >>>

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.

For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ...
more >>>

Roei Tell

Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.

In ... more >>>

Oded Goldreich, Tom Gur

Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures ... more >>>

Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

An efficient randomized polynomial identity test for noncommutative

polynomials given by noncommutative arithmetic circuits remains an

open problem. The main bottleneck to applying known techniques is that

a noncommutative circuit of size $s$ can compute a polynomial of

degree exponential in $s$ with a double-exponential number of nonzero

monomials. ...
more >>>

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

Pasin Manurangsi

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

Pavel Hubacek, Moni Naor, Eylon Yogev

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

Scott Aaronson, Lijie Chen

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>>

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.

Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>

Dmitry Sokolov

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>

Christoph Berkholz, Jakob Nordström

We show that there are CNF formulas which can be refuted in resolution

in both small space and small width, but for which any small-width

proof must have space exceeding by far the linear worst-case upper

bound. This significantly strengthens the space-width trade-offs in

[Ben-Sasson '09]}, and provides one more ...
more >>>

Prahladh Harsha, Srikanth Srinivasan

We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime.

* $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots P_k$ is the evaluation of a degree-$(d+ek)$ polynomial.

... more >>>Amey Bhangale, Irit Dinur, Inbal Livni Navon

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a ... more >>>

Benjamin Rossman

Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC$^0$ ... more >>>