All reports in year 2019:

__
TR19-043
| 12th March 2019
__

Toniann Pitassi, Morgan Shirley, Thomas Watson#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

__
TR19-042
| 18th March 2019
__

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha#### Determinant equivalence test over finite fields and over $\mathbf{Q}$

__
TR19-041
| 7th March 2019
__

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram#### Quantum hardness of learning shallow classical circuits

__
TR19-040
| 19th February 2019
__

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis#### The Complexity of Finding {$S$}-factors in Regular Graphs

__
TR19-039
| 12th March 2019
__

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee#### Planarity, Exclusivity, and Unambiguity

__
TR19-038
| 7th March 2019
__

Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Nalini Vasudevan#### Statistical Difference Beyond the Polarizing Regime

__
TR19-037
| 5th March 2019
__

Chi-Ning Chou, Mrinal Kumar, Noam Solomon#### Closure of VP under taking factors: a short and simple proof

__
TR19-036
| 5th March 2019
__

Pavel Hrubes#### On the complexity of computing a random Boolean function over the reals

__
TR19-035
| 5th March 2019
__

Alexey Milovanov#### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials

__
TR19-034
| 5th March 2019
__

Pavel Hrubes#### On $\epsilon$-sensitive monotone computations

__
TR19-033
| 20th February 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

__
TR19-032
| 4th March 2019
__

Srikanth Srinivasan#### Strongly Exponential Separation Between Monotone VP and Monotone VNP

__
TR19-031
| 4th March 2019
__

Lijie Chen#### Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

__
TR19-030
| 19th February 2019
__

Claude Crépeau, Nan Yang#### Non-Locality in Interactive Proofs

__
TR19-029
| 20th February 2019
__

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman#### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

__
TR19-028
| 1st March 2019
__

Shachar Lovett, Noam Solomon, Jiapeng Zhang#### From DNF compression to sunflower theorems via regularity

__
TR19-027
| 1st March 2019
__

Mark Bun, Nikhil Mande, Justin Thaler#### Sign-Rank Can Increase Under Intersection

__
TR19-026
| 28th February 2019
__

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff#### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

__
TR19-025
| 28th February 2019
__

Shuichi Hirahara, Osamu Watanabe#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

__
TR19-024
| 20th February 2019
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### The Surprising Power of Constant Depth Algebraic Proofs

__
TR19-023
| 25th February 2019
__

Orr Paradise#### Smooth and Strong PCPs

__
TR19-022
| 23rd February 2019
__

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

__
TR19-021
| 19th February 2019
__

Rahul Ilango#### $AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP

__
TR19-020
| 4th February 2019
__

Ludmila Glinskih, Dmitry Itsykson#### On Tseitin formulas, read-once branching programs and treewidth

Revisions: 1

__
TR19-019
| 19th February 2019
__

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi#### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR19-017
| 6th February 2019
__

Chin Ho Lee#### Fourier bounds and pseudorandom generators for product tests

__
TR19-016
| 5th February 2019
__

Alexander A. Sherstov#### The hardest halfspace

__
TR19-015
| 7th February 2019
__

William Kretschmer#### QMA Lower Bounds for Approximate Counting

__
TR19-014
| 22nd January 2019
__

Himanshu Tyagi, Shun Watanabe#### A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem

__
TR19-013
| 31st January 2019
__

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

__
TR19-012
| 27th January 2019
__

Oded Goldreich#### Multi-pseudodeterministic algorithms

__
TR19-011
| 27th January 2019
__

Benny Applebaum, Eliran Kachlon#### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

__
TR19-010
| 21st January 2019
__

Dorit Aharonov, Alex Bredariol Grilo#### Stoquastic PCP vs. Randomness

__
TR19-009
| 16th January 2019
__

Jiawei Gao, Russell Impagliazzo#### The Fine-Grained Complexity of Strengthenings of First-Order Logic

Revisions: 1

__
TR19-008
| 20th January 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Efficiently factoring polynomials modulo $p^4$

__
TR19-007
| 17th January 2019
__

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh#### Lower Bounds for Linear Decision Lists

__
TR19-006
| 17th January 2019
__

Anna Gal, Ridwan Syed#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

__
TR19-005
| 16th January 2019
__

Omar Alrabiah, Venkatesan Guruswami#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

__
TR19-004
| 11th January 2019
__

Amey Bhangale, Subhash Khot#### UG-hardness to NP-hardness by Losing Half

__
TR19-003
| 2nd January 2019
__

Alexander A. Sherstov, Pei Wu#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

__
TR19-002
| 31st December 2018
__

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii#### Complexity of Linear Operators

__
TR19-001
| 5th January 2019
__

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov#### On OBDD-based algorithms and proof systems that dynamically change order of variables

Toniann Pitassi, Morgan Shirley, Thomas Watson

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.

The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ...
more >>>

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

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

The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1)\geq\alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq ... more >>>

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

Pavel Hrubes

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:

(i) every $f$ can be defined by a formula of size $O(n)$,

(ii) if $A$ is required to have at most $k\geq 1$ ...
more >>>

Alexey Milovanov

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.

This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ...
more >>>

Pavel Hrubes

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

Srikanth Srinivasan

We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$

more >>>Lijie Chen

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ...
more >>>

Claude Crépeau, Nan Yang

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new ... more >>>

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

Shachar Lovett, Noam Solomon, Jiapeng Zhang

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... more >>>

Mark Bun, Nikhil Mande, Justin Thaler

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets $S_1,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>>

Shuichi Hirahara, Osamu Watanabe

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... more >>>

Orr Paradise

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs:

- ...
more >>>

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Rahul Ilango

The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>

Ludmila Glinskih, Dmitry Itsykson

We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an $n\times n$ grid graph has size at least $2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph $G(V,E)$ any nondeterministic read-once branching program that computes ... more >>>

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Chin Ho Lee

We study the Fourier spectrum of functions $f\colon \{0,1\}^{mk} \to \{-1,0,1\}$ which can be written as a product of $k$ Boolean functions $f_i$ on disjoint $m$-bit inputs. We prove that for every positive integer $d$,

\[

\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .

\]

Our upper bound ...
more >>>

Alexander A. Sherstov

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>>

William Kretschmer

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>

Himanshu Tyagi, Shun Watanabe

We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced ... more >>>

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

Oded Goldreich

In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).

Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>>

Benny Applebaum, Eliran Kachlon

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>

Dorit Aharonov, Alex Bredariol Grilo

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>

Jiawei Gao, Russell Impagliazzo

The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols;

first-order on ordered structures; adding various notions ...
more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.

We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Anna Gal, Ridwan Syed

We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity ... more >>>

Omar Alrabiah, Venkatesan Guruswami

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a ... more >>>

Amey Bhangale, Subhash Khot

The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction ... more >>>

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>