Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2020:
All reports in year 2020:
TR20-041 | 29th March 2020
Mrinal Kumar, Ben Lee Volk

#### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 1

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>

TR20-040 | 25th March 2020
Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

#### Topology and adjunction in promise constraint satisfaction

The approximate graph colouring problem concerns colouring a $k$-colourable
graph with $c$ colours, where $c\geq k$. This problem naturally generalises
to promise graph homomorphism and further to promise constraint satisfaction
problems. Complexity analysis of all these problems is notoriously difficult.
In this paper, we introduce ... more >>>

TR20-039 | 25th March 2020
Pranjal Dutta, Nitin Saxena, Thomas Thierauf

#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

TR20-038 | 15th March 2020
Ofer Grossman, Justin Holmgren

#### Error Correcting Codes for Uncompressed Messages

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

TR20-037 | 18th March 2020
Michal Garlik

#### Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It

We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then ... more >>>

TR20-036 | 9th March 2020
Olaf Beyersdorff, Joshua Blinkhorn, Tomáš Peitl

#### Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths

We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new tautology-free DQBF dependency scheme that generalises the reflexive resolution path dependency scheme. We establish soundness of the tautology-free scheme, implying that it can be used in any ... more >>>

TR20-035 | 23rd February 2020
Justin Holmgren

#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

We revisit one original motivation for the study of no-signaling multi-prover
interactive proofs (NS-MIPs): specifically, that two spatially separated
provers are guaranteed to be no-signaling by the physical principle that
information cannot travel from one point to another faster than light.

We observe that with ... more >>>

TR20-034 | 12th March 2020
Erfan Khaniki

#### On Proof complexity of Resolution over Polynomial Calculus

The refutation system ${Res}_R({PC}_d)$ is a natural extension of resolution refutation system such that it operates with disjunctions of degree $d$ polynomials over ring $R$ with boolean variables. For $d=1$, this system is called ${Res}_R({lin})$. Based on properties of $R$, ${Res}_R({lin})$ systems can be too strong to prove lower ... more >>>

TR20-033 | 12th March 2020
Suryajith Chillara

#### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 1

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

TR20-032 | 12th March 2020
Suryajith Chillara

#### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

TR20-031 | 10th March 2020
Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

TR20-030 | 9th March 2020
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

#### Barriers for Rectangular Matrix Multiplication

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

TR20-029 | 6th March 2020
Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the ... more >>>

TR20-028 | 27th February 2020
Nikhil Gupta, Chandan Saha, Bhargav Thankey

#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>

TR20-027 | 26th February 2020
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

#### The Power of Many Samples in Query Complexity

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

TR20-026 | 25th February 2020
Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>> TR20-025 | 20th February 2020 Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari #### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists. As a consequence, we obtain that deciding whether the ... more >>> TR20-024 | 20th February 2020 Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari #### Randomized and Symmetric Catalytic Computation A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>> TR20-023 | 10th February 2020 Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan #### Non-Malleability against Polynomial Tampering We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials. Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>> TR20-022 | 19th February 2020 Klim Efremenko, Gillat Kol, Raghuvansh Saxena #### Interactive Error Resilience Beyond$\frac{2}{7}$Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against? For the non-adaptive channel, where the parties must agree ... more >>> TR20-021 | 21st February 2020 Rahul Ilango, Bruno Loff, Igor Carboni Oliveira #### NP-Hardness of Circuit Minimization for Multi-Output Functions Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>> TR20-020 | 21st February 2020 Nikhil Mande, Justin Thaler, Shuchen Zhu #### Improved Approximate Degree Bounds For$k$-distinctness An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the$k$-distinctness function on inputs of size$N$. While the case of$k=2$(also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>> TR20-019 | 19th February 2020 Siddharth Bhandari, Prahladh Harsha #### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions. more >>> TR20-018 | 18th February 2020 Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira #### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates The class$FORMULA[s] \circ \mathcal{G}$consists of Boolean functions computable by size-$s$de Morgan formulas whose leaves are any Boolean functions from a class$\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for$FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes$\mathcal{G}$of functions with low communication complexity. Let$R^{(k)}(\mathcal{G})$be ... more >>> TR20-017 | 18th February 2020 Alexander Kozachinskiy, Vladimir Podolskii #### Multiparty Karchmer-Wigderson Games and Threshold Circuits We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>> TR20-016 | 17th February 2020 Kuan Cheng, William Hoza #### Hitting Sets Give Two-Sided Derandomization of Small Space A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>> TR20-015 | 18th February 2020 Emanuele Viola #### New lower bounds for probabilistic degree and AC0 with parity gates Revisions: 1 We prove new lower bounds for computing some functions$f:\{0,1\}^{n}\to\{0,1\}$in$E^{NP}$by polynomials modulo$2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include: (1)$\Omega(n/\log^{2}n)$lower bounds probabilistic degree. This is optimal up to a factor$O(\log^{2}n)$. The previous best lower bound was$\Omega(\sqrt{n})$proved in ... more >>> TR20-014 | 16th February 2020 Gil Cohen, Shahar Samocha #### Palette-Alternating Tree Codes A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from$0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>> TR20-013 | 17th February 2020 Noga Ron-Zewi, Mary Wootters, Gilles Z\'{e}mor #### Linear-time Erasure List-decoding of Expander Codes We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let$r > 0$be any integer. Given an inner code$\cC_0$of length$d$, and a$d$-regular bipartite expander graph$G$with$n$vertices on each side, we give an algorithm to list-decode the expander code$\cC ... more >>>

TR20-012 | 14th February 2020
Dmitry Sokolov

#### (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

One of the major open problems in proof complexity is to prove lower bounds on $AC_0[p]$-Frege proof
systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove
lower bounds on the size for Polynomial Calculus over the $\{\pm 1\}$ basis. In this ... more >>>

TR20-011 | 9th February 2020
Dominik Scheder, Navid Talebanfard

#### Super Strong ETH is true for strong PPSZ

We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>>

TR20-010 | 12th February 2020
Lijie Chen, Hanlin Ren

#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>

TR20-009 | 6th February 2020
Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

#### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL
Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a
new approach: looking at the first Fourier level of the function after a suitable random restriction and
applying the Log-Sobolev ... more >>>

TR20-008 | 26th January 2020
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined authorized'' sets of parties can reconstruct the secret, and all other unauthorized'' sets learn nothing about $s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

TR20-007 | 19th December 2019
Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang

#### Practical Relativistic Zero-Knowledge for NP

In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers ... more >>>

TR20-006 | 22nd January 2020
Anup Rao, Amir Yehudayoff

#### The Communication Complexity of the Exact Gap-Hamming Problem

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>

TR20-005 | 17th January 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

TR20-004 | 17th January 2020
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

#### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

TR20-003 | 15th January 2020
Giuseppe Persiano, Kevin Yeo

#### Tight Static Lower Bounds for Non-Adaptive Data Structures

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

TR20-002 | 6th January 2020
Sophie Laplante, Reza Naserasr, Anupa Sunny

#### Sensitivity lower bounds from linear dependencies

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we ... more >>>

TR20-001 | 31st December 2019
Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

ISSN 1433-8092 | Imprint