All reports in year 2017:

__
TR17-111
| 2nd June 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

__
TR17-110
| 22nd June 2017
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Axis-Parallel Tests for Tensor Product Codes

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR17-106
| 16th June 2017
__

Mateus de Oliveira Oliveira, Pavel Pudlak#### Representations of Monotone Boolean Functions by Linear Programs

__
TR17-105
| 14th June 2017
__

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden#### Pseudo-Deterministic Proofs

__
TR17-104
| 13th June 2017
__

Brett Hemenway, Noga Ron-Zewi, Mary Wootters#### Local List Recovery of High-rate Tensor Codes & Applications

__
TR17-103
| 12th June 2017
__

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Parameterized Property Testing of Functions

__
TR17-102
| 9th June 2017
__

Oded Goldreich#### Overview of the doubly-efficient interactive proof systems of RRR

__
TR17-101
| 8th June 2017
__

Oded Goldreich#### On the doubly-efficient interactive proof systems of GKR

__
TR17-100
| 7th June 2017
__

Dakshita Khurana, Amit Sahai#### How to Achieve Non-Malleability in One or Two Rounds

__
TR17-099
| 5th June 2017
__

Nir Bitansky, Omer Paneth, Yael Tauman Kalai#### Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 1

__
TR17-098
| 28th May 2017
__

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee#### Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 1

__
TR17-097
| 31st May 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### Multi Collision Resistant Hash Functions and their Applications

__
TR17-096
| 30th May 2017
__

Irit Dinur, Inbal Livni Navon#### Exponentially Small Soundness for the Direct Product Z-test

__
TR17-095
| 26th May 2017
__

Ran Gelles, Yael Tauman Kalai#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

__
TR17-092
| 10th May 2017
__

Shuichi Hirahara#### A Duality Between Depth-Three Formulas and Approximation by Depth-Two

__
TR17-091
| 17th May 2017
__

Andrej Bogdanov#### Small bias requires large formulas

__
TR17-090
| 15th May 2017
__

Chin Ho Lee, Emanuele Viola#### The coin problem for product tests

__
TR17-089
| 11th May 2017
__

Irit Dinur, Tali Kaufman#### High dimensional expanders imply agreement expanders

__
TR17-088
| 10th May 2017
__

Elena Grigorescu, Akash Kumar, Karl Wimmer#### K-Monotonicity is Not Testable on the Hypercube

__
TR17-087
| 9th May 2017
__

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar#### On Weak-Space Complexity over Complex Numbers

__
TR17-086
| 9th May 2017
__

C Ramya, Raghavendra Rao B V#### Linear Projections of the Vandermonde Polynomial

Revisions: 1

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR17-084
| 2nd May 2017
__

Iftach Haitner, Salil Vadhan#### The Many Entropies in One-Way Functions

__
TR17-083
| 5th May 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Weights at the Bottom Matter When the Top is Heavy

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR17-081
| 2nd May 2017
__

Badih Ghazi, Madhu Sudan#### The Power of Shared Randomness in Uncertain Communication

__
TR17-080
| 1st May 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### The Quest for Strong Inapproximability Results with Perfect Completeness

__
TR17-079
| 1st May 2017
__

Alexander A. Sherstov, Pei Wu#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

__
TR17-078
| 21st April 2017
__

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski#### Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model

__
TR17-077
| 30th April 2017
__

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan#### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

__
TR17-076
| 21st April 2017
__

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee#### New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 1

__
TR17-075
| 29th April 2017
__

Clement Canonne, Ilias Diakonikolas, Alistair Stewart#### Fourier-Based Testing for Families of Distributions

__
TR17-074
| 29th April 2017
__

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S#### Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

__
TR17-073
| 28th April 2017
__

Eric Allender, Shuichi Hirahara#### New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

__
TR17-072
| 25th April 2017
__

Eric Allender, Andreas Krebs, Pierre McKenzie#### Better Complexity Bounds for Cost Register Machines

__
TR17-071
| 14th April 2017
__

Young Kun Ko, Arial Schvartzman#### Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

Revisions: 1

__
TR17-070
| 15th April 2017
__

Shachar Lovett, Sankeerth Rao, Alex Vardy#### Probabilistic Existence of Large Sets of Designs

__
TR17-069
| 17th April 2017
__

Jacob Steinhardt#### Does robustness imply tractability? A lower bound for planted clique in the semi-random model

__
TR17-068
| 20th April 2017
__

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie#### Settling the query complexity of non-adaptive junta testing

__
TR17-067
| 21st April 2017
__

Benny Applebaum#### Garbled Circuits as Randomized Encodings of Functions: a Primer

__
TR17-066
| 20th April 2017
__

Josh Alman, Joshua Wang, Huacheng Yu#### Cell-Probe Lower Bounds from Online Communication Complexity

__
TR17-065
| 20th April 2017
__

Boaz Barak#### The Complexity of Public-Key Cryptograph

__
TR17-064
| 20th April 2017
__

Venkatesan Guruswami, Chaoping Xing, chen yuan#### Subspace Designs based on Algebraic Function Fields

__
TR17-063
| 10th April 2017
__

Benny Applebaum#### Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

__
TR17-062
| 9th April 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Dual polynomials and communication complexity of XOR functions

__
TR17-061
| 3rd April 2017
__

Anat Ganor, Karthik C. S.#### Communication Complexity of Correlated Equilibrium in Two-Player Games

__
TR17-060
| 9th April 2017
__

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari#### Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

__
TR17-059
| 6th April 2017
__

Ola Svensson, Jakub Tarnawski#### The Matching Problem in General Graphs is in Quasi-NC

__
TR17-058
| 7th April 2017
__

Noga Alon, Omri Ben-Eliezer, Eldar Fischer#### Testing hereditary properties of ordered graphs and matrices

Revisions: 1

__
TR17-057
| 7th April 2017
__

Alessandro Chiesa, Michael Forbes, Nicholas Spooner#### A Zero Knowledge Sumcheck and its Applications

__
TR17-056
| 7th April 2017
__

Paul Goldberg, Christos Papadimitriou#### Towards a Unified Complexity Theory of Total Functions

__
TR17-055
| 26th March 2017
__

Maya Leshkowitz#### Round Complexity Versus Randomness Complexity in Interactive Proofs

__
TR17-054
| 22nd March 2017
__

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay#### Lifting randomized query complexity to randomized communication complexity

Revisions: 1

__
TR17-053
| 22nd March 2017
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for BPP

__
TR17-052
| 19th March 2017
__

Dieter van Melkebeek, Gautam Prakriya#### Derandomizing Isolation in Space-Bounded Settings

__
TR17-051
| 16th March 2017
__

Mark Bun, Justin Thaler#### A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

__
TR17-050
| 15th March 2017
__

Joe Boninger, Joshua Brody, Owen Kephart#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

__
TR17-049
| 14th March 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

__
TR17-048
| 14th March 2017
__

Pavel Hrubes, Pavel Pudlak#### A note on monotone real circuits

__
TR17-047
| 10th March 2017
__

Kasper Green Larsen, Omri Weinstein, Huacheng Yu#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

__
TR17-046
| 8th March 2017
__

Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk#### Learning Residual Alternating Automata

__
TR17-045
| 7th March 2017
__

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere#### Random CNFs are Hard for Cutting Planes

Revisions: 1

__
TR17-044
| 21st February 2017
__

Olaf Beyersdorff, Luke Hinde, Ján Pich#### Reasons for Hardness in QBF Proof Systems

Revisions: 1

__
TR17-043
| 3rd March 2017
__

Alexey Milovanov, Nikolay Vereshchagin#### Stochasticity in Algorithmic Statistics for Polynomial Time

__
TR17-042
| 6th March 2017
__

Pavel Hrubes, Pavel Pudlak#### Random formulas, monotone circuits, and interpolation

__
TR17-041
| 6th March 2017
__

Amnon Ta-Shma#### Explicit, almost optimal, epsilon-balanced codes

__
TR17-040
| 4th March 2017
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

__
TR17-039
| 28th February 2017
__

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan#### Average-Case Fine-Grained Hardness

__
TR17-038
| 23rd February 2017
__

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan#### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

__
TR17-037
| 25th February 2017
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Understanding Cutting Planes for QBFs

__
TR17-036
| 22nd February 2017
__

Dean Doron, Francois Le Gall, Amnon Ta-Shma#### Probabilistic logarithmic-space algorithms for Laplacian solvers

__
TR17-035
| 23rd February 2017
__

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

__
TR17-034
| 21st February 2017
__

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam#### On algebraic branching programs of small width

Revisions: 1

__
TR17-033
| 19th February 2017
__

Daniel Kane, Shachar Lovett, Sankeerth Rao#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

__
TR17-032
| 17th February 2017
__

Olaf Beyersdorff, Joshua Blinkhorn#### Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds

__
TR17-031
| 15th February 2017
__

Thomas Watson#### Quadratic Simulations of Merlin-Arthur Games

__
TR17-030
| 15th February 2017
__

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari#### An Improved Dictatorship Test with Perfect Completeness

__
TR17-029
| 18th February 2017
__

Clement Canonne, Tom Gur#### An Adaptivity Hierarchy Theorem for Property Testing

Revisions: 1

__
TR17-028
| 17th February 2017
__

Mrinal Kumar#### A quadratic lower bound for homogeneous algebraic branching programs

Revisions: 1

__
TR17-027
| 16th February 2017
__

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma#### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate

__
TR17-026
| 17th February 2017
__

Valentine Kabanets, Daniel Kane, Zhenjian Lu#### A Polynomial Restriction Lemma with Applications

__
TR17-025
| 16th February 2017
__

Pooya Hatami, Avishay Tal#### Pseudorandom Generators for Low-Sensitivity Functions

__
TR17-024
| 16th February 2017
__

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for P^NP

__
TR17-023
| 15th February 2017
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### The Power of Natural Properties as Oracles

__
TR17-022
| 13th February 2017
__

Benjamin Rossman, Srikanth Srinivasan#### Separation of AC$^0[\oplus]$ Formulas and Circuits

__
TR17-021
| 11th February 2017
__

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas#### Reconstruction of full rank Algebraic Branching Programs

__
TR17-020
| 12th February 2017
__

Ran Raz#### A Time-Space Lower Bound for a Large Class of Learning Problems

__
TR17-019
| 8th February 2017
__

Andreas Krebs, Nutan Limaye, Michael Ludwig#### A Unified Method for Placing Problems in Polylogarithmic Depth

Revisions: 1

__
TR17-018
| 6th February 2017
__

Oded Goldreich, Guy Rothblum#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 2

__
TR17-017
| 5th February 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Lower Bounds for Space Bounded Learning

__
TR17-016
| 31st January 2017
__

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena#### Irreducibility and deterministic r-th root finding over finite fields

__
TR17-015
| 4th February 2017
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR17-012
| 17th January 2017
__

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau#### Emptiness Problems for Integer Circuits

__
TR17-011
| 22nd January 2017
__

Boaz Barak, Pravesh Kothari, David Steurer#### Quantum entanglement, sum of squares, and the log rank conjecture

__
TR17-010
| 18th January 2017
__

Xiaodi Wu, Penghui Yao, Henry Yuen#### Raz-McKenzie simulation with the inner product gadget

Revisions: 1

__
TR17-009
| 19th January 2017
__

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf#### Towards an algebraic natural proofs barrier via polynomial identity testing

__
TR17-008
| 14th January 2017
__

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan#### Low-Complexity Cryptographic Hash Functions

__
TR17-007
| 19th January 2017
__

Michael Forbes, Amir Shpilka, Ben Lee Volk#### Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

__
TR17-006
| 15th December 2016
__

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath#### Testing Ising Models

Revisions: 1

__
TR17-005
| 10th January 2017
__

Nir Bitansky#### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Revisions: 3

__
TR17-004
| 8th January 2017
__

Scott Aaronson#### P=?NP

__
TR17-003
| 24th November 2016
__

Yi Deng#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Revisions: 1

__
TR17-002
| 6th January 2017
__

Frantisek Duris#### Some notes on two lower bound methods for communication complexity

__
TR17-001
| 6th January 2017
__

Stephen Cook, Bruce Kapron#### A Survey of Classes of Primitive Recursive Functions

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

A Boolean function $f:\{0,1\}^d \to \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $\Omega(\frac{d}{\log d})$ queries. This result improves upon the $\Omega(\frac{d}{\log^2 d})$ lower bound for the same class of ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Mateus de Oliveira Oliveira, Pavel Pudlak

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of

computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.

2. MLP circuits are exponentially stronger than monotone span programs.

3. ...
more >>>

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where

the verifier is guaranteed with high probability to output the same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.

In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ...
more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

Oded Goldreich

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).

Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system

in which the prover runs polynomial time ...
more >>>

Oded Goldreich

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).

Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ...
more >>>

Dakshita Khurana, Amit Sahai

Despite over 25 years of research on non-malleable commitments in the plain model, their round complexity has remained open. The goal of achieving non-malleable commitment protocols with only one or two rounds has been especially elusive. Pass (TCC 2013, CC 2016) captured this difficulty by proving important impossibility results regarding ... more >>>

Nir Bitansky, Omer Paneth, Yael Tauman Kalai

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... more >>>

Irit Dinur, Inbal Livni Navon

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ...
more >>>

Ran Gelles, Yael Tauman Kalai

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

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

The paper investigates expansion properties of the Grassmann graph,

motivated by recent results of [KMS, DKKMS] concerning hardness

of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the

hypotheses put forward by these papers seems to first require a better

understanding of these expansion properties.

We consider the edge ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>

Shuichi Hirahara

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>>

Andrej Bogdanov

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

Chin Ho Lee, Emanuele Viola

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$

where the $X_i$ are independent and each $X_i$ equals $1$ with

probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We

consider the smallest value $\eps^*$ of $\eps$ such that the distributions

$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant

more >>>

Irit Dinur, Tali Kaufman

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree ... more >>>

Elena Grigorescu, Akash Kumar, Karl Wimmer

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates between $0$ and $1$ at most $k$ times on every ascending chain. Such functions represent a natural generalization ... more >>>

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>>

C Ramya, Raghavendra Rao B V

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

Iftach Haitner, Salil Vadhan

Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.

Moreover, the queries we use are comparison ...
more >>>

Badih Ghazi, Madhu Sudan

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

Alexander A. Sherstov, Pei Wu

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski

We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has ... more >>>

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

We present new protocols for conditional disclosure of secrets (CDS),

where two parties want to disclose a secret to a third party if and

only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,

we present two protocols that achieve ...
more >>>

Clement Canonne, Ilias Diakonikolas, Alistair Stewart

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

Eric Allender, Shuichi Hirahara

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

Young Kun Ko, Arial Schvartzman

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper ... more >>>

Shachar Lovett, Sankeerth Rao, Alex Vardy

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

Jacob Steinhardt

We consider a robust analog of the planted clique problem. In this analog, a set $S$ of vertices is chosen and all edges in $S$ are included; then, edges between $S$ and the rest of the graph are included with probability $\frac{1}{2}$, while edges not touching $S$ are allowed to ... more >>>

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

We prove that any non-adaptive algorithm that tests whether an unknown

Boolean function $f\colon \{0, 1\}^n\to\{0, 1\} $ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ...
more >>>

Benny Applebaum

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of \emph{randomized encoding} (RE) of functions. We review old and new constructions of REs, present some lower bounds, and describe some applications. ... more >>>

Josh Alman, Joshua Wang, Huacheng Yu

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>>

Boaz Barak

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This is a survey that appeared in a book of surveys in honor of ... more >>>

Venkatesan Guruswami, Chaoping Xing, chen yuan

Subspace designs are a (large) collection of high-dimensional subspaces $\{H_i\}$ of $\F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $W \cap H_i$ is at most some parameter $L$. The ... more >>>

Benny Applebaum

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,

we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. ...
more >>>

Anat Ganor, Karthik C. S.

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

Ola Svensson, Jakub Tarnawski

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.

We also explain how the proof can ...
more >>>

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

Paul Goldberg, Christos Papadimitriou

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>

Maya Leshkowitz

Consider an interactive proof system for some set S that has randomness complexity r(n) for instances of length n, and arbitrary round complexity. We show a public-coin interactive proof system for S of round complexity O(r(n)/log n). Furthermore, the randomness complexity is preserved up to a constant factor, and the ... more >>>

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>

Dieter van Melkebeek, Gautam Prakriya

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

Joe Boninger, Joshua Brody, Owen Kephart

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>>

Pavel Hrubes, Pavel Pudlak

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ...
more >>>

Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

Residuality plays an essential role for learning finite automata.

While residual deterministic and nondeterministic

automata have been understood quite well, fundamental

questions concerning alternating automata (AFA) remain open.

Recently, Angluin, Eisenstat, and Fisman have initiated

a systematic study of residual AFAs and proposed an algorithm called AL*

-an extension of ...
more >>>

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

The random k-SAT model is the most important and well-studied distribution over

k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for

satisfiablity algorithms, and lastly average-case hardness over this distribution has also

been linked to hardness of approximation via Feige’s hypothesis. In this ...
more >>>

Olaf Beyersdorff, Luke Hinde, Ján Pich

We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction.

The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>>

Alexey Milovanov, Nikolay Vereshchagin

A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for $x$ if it looks likely that $x$ was drawn at random with respect to that distribution. In this paper, we ... more >>>

Pavel Hrubes, Pavel Pudlak

We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>>

Amnon Ta-Shma

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\epsilon}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>>

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>

Dean Doron, Francois Le Gall, Amnon Ta-Shma

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system $L x=b$, where $L$ is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem.

more >>>

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

Daniel Kane, Shachar Lovett, Sankeerth Rao

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over

any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn

We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution.

Our technique exploits a clear semantic paradigm, showing the ... more >>>

Thomas Watson

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic ... more >>>

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

... more >>>Clement Canonne, Tom Gur

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>>

Mrinal Kumar

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>>

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

We show a reduction from the existence of explicit t-non-malleable

extractors with a small seed length, to the construction of explicit

two-source extractors with small error for sources with arbitrarily

small constant rate. Previously, such a reduction was known either

when one source had entropy rate above half [Raz05] or ...
more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>

Pooya Hatami, Avishay Tal

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).

We obtain new circuit lower bounds, as well as some hardness results for the relativized version ...
more >>>

Benjamin Rossman, Srikanth Srinivasan

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

Ran Raz

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples.

Our result is stated in terms of the norm ... more >>>

Andreas Krebs, Nutan Limaye, Michael Ludwig

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>>

Oded Goldreich, Guy Rothblum

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.

Specifically, such ...
more >>>

Michal Moshkovitz, Dana Moshkovitz

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

Boaz Barak, Pravesh Kothari, David Steurer

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

Michael Forbes, Amir Shpilka, Ben Lee Volk

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

Nir Bitansky

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>

Scott Aaronson

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, ... more >>>

Yi Deng

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;

-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any ...
more >>>

Frantisek Duris

We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions $f(x,y)$, $x,y\in\{0,1\}^n$, with rank of size $k$ and fooling set of size at least k, $k\in [1,2^n]$. Using these bounds ... more >>>

Stephen Cook, Bruce Kapron

This paper is a transcription of mimeographed course notes titled ``A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function

classes (and classes of relations based on these ...
more >>>