Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2019:
All reports in year 2019:
TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

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 >>>

TR19-042 | 18th March 2019
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

#### Determinant equivalence test over finite fields and over $\mathbf{Q}$

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 >>>

TR19-041 | 7th March 2019
Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

#### Quantum hardness of learning shallow classical circuits

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 >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

#### The Complexity of Finding {$S$}-factors in Regular Graphs

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 >>>

TR19-039 | 12th March 2019
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

#### Planarity, Exclusivity, and Unambiguity

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 >>>

TR19-038 | 7th March 2019
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 >>> TR19-037 | 5th March 2019 Chi-Ning Chou, Mrinal Kumar, Noam Solomon #### Closure of VP under taking factors: a short and simple proof 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 >>> TR19-036 | 5th March 2019 Pavel Hrubes #### On the complexity of computing a random Boolean function over the reals 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 >>> TR19-035 | 5th March 2019 Alexey Milovanov #### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials 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 >>> TR19-034 | 5th March 2019 Pavel Hrubes #### On$\epsilon$-sensitive monotone computations 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 >>>

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

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 >>>

TR19-032 | 4th March 2019
Srikanth Srinivasan

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

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 >>>

TR19-031 | 4th March 2019
Lijie Chen

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

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 >>>

TR19-030 | 19th February 2019
Claude Crépeau, Nan Yang

#### Non-Locality in Interactive Proofs

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 >>>

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

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 >>>

TR19-028 | 1st March 2019
Shachar Lovett, Noam Solomon, Jiapeng Zhang

#### From DNF compression to sunflower theorems via regularity

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 >>>

TR19-027 | 1st March 2019
Mark Bun, Nikhil Mande, Justin Thaler

#### Sign-Rank Can Increase Under Intersection

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 >>>

TR19-026 | 28th February 2019
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 >>> TR19-025 | 28th February 2019 Shuichi Hirahara, Osamu Watanabe #### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets 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 >>> TR19-024 | 20th February 2019 Russell Impagliazzo, Sasank Mouli, Toniann Pitassi #### The Surprising Power of Constant Depth Algebraic Proofs 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 >>> TR19-023 | 25th February 2019 Orr Paradise #### Smooth and Strong PCPs 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 >>> TR19-022 | 23rd February 2019 Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis #### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators 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 >>> TR19-021 | 19th February 2019 Rahul Ilango ####$AC^0[p]$Lower Bounds and NP-Hardness for Variants of MCSP 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 >>> TR19-020 | 4th February 2019 Ludmila Glinskih, Dmitry Itsykson #### On Tseitin formulas, read-once branching programs and treewidth Revisions: 1 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 >>> TR19-019 | 19th February 2019 Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi #### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits 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 >>> 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 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 >>> TR19-017 | 6th February 2019 Chin Ho Lee #### Fourier bounds and pseudorandom generators for product tests 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 >>> TR19-016 | 5th February 2019 Alexander A. Sherstov #### The hardest halfspace 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 >>> TR19-015 | 7th February 2019 William Kretschmer #### QMA Lower Bounds for Approximate Counting 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 >>> TR19-014 | 22nd January 2019 Himanshu Tyagi, Shun Watanabe #### A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem 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 >>> TR19-013 | 31st January 2019 Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami #### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations 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 >>> TR19-012 | 27th January 2019 Oded Goldreich #### Multi-pseudodeterministic algorithms 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 >>> TR19-011 | 27th January 2019 Benny Applebaum, Eliran Kachlon #### Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders 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 >>> TR19-010 | 21st January 2019 Dorit Aharonov, Alex Bredariol Grilo #### Stoquastic PCP vs. Randomness 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 >>> TR19-009 | 16th January 2019 Jiawei Gao, Russell Impagliazzo #### The Fine-Grained Complexity of Strengthenings of First-Order Logic Revisions: 1 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 >>> TR19-008 | 20th January 2019 Ashish Dwivedi, Rajat Mittal, Nitin Saxena #### Efficiently factoring polynomials modulo$p^4$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 >>>

TR19-007 | 17th January 2019

#### Lower Bounds for Linear Decision Lists

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 >>>

TR19-006 | 17th January 2019
Anna Gal, Ridwan Syed

#### Upper Bounds on Communication in terms of Approximate Rank

Revisions: 1

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 >>>

TR19-005 | 16th January 2019
Omar Alrabiah, Venkatesan Guruswami

#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

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 >>>

TR19-004 | 11th January 2019
Amey Bhangale, Subhash Khot

#### UG-hardness to NP-hardness by Losing Half

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 >>>

TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

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 >>>

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

#### Complexity of Linear Operators

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint