Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > 2024:
All reports in year 2024:
TR24-078 | 19th April 2024
Oded Goldreich

On the relaxed LDC of BGHSV: A survey that corrects the record

A locally decodable code (LDC) is an error correcting code that allows for recovery of any desired bit in the message based on a constant number of randomly selected bits in the possibly corrupted codeword.
A relaxed LDC requires correct recovery only in case of actual codewords, while requiring that ... more >>>


TR24-077 | 19th April 2024
Divesh Aggarwal, JinMing Leong, Alexandra Veliche

Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness - the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle ... more >>>


TR24-076 | 10th April 2024
Oliver Korten, Toniann Pitassi

Strong vs. Weak Range Avoidance and the Linear Ordering Principle

In a pair of recent breakthroughs \cite{CHR,Li} it was shown that the classes $S_2^E, ZPE^{NP}$, and $\Sigma_2^E$ require exponential circuit complexity, giving the first unconditional improvements to a classical result of Kannan. These results were obtained by designing a surprising new algorithm for the total search problem Range Avoidance: given ... more >>>


TR24-075 | 13th April 2024
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant $\varepsilon> 0$ such that for any computable function $f:\mathbb{N}\to\mathbb{N}$, no $f(k)\cdot n^{O(1)}$-time algorithm can, on input a $k$-variable CSP instance with domain size $n$, find an assignment satisfying ... more >>>


TR24-074 | 11th April 2024
Vaibhav Krishan, Sundar Vishwanathan

Towards ACC Lower Bounds using Torus Polynomials

The class $ACC$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC$. The Boolean ... more >>>


TR24-073 | 11th April 2024
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Trading Determinism for Noncommutativity in Edmonds' Problem

Let $X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$ be a partitioned set of variables such that the variables in each part $X_i$ are noncommuting but for any $i\neq j$, the variables $x \in X_i$ commute with the variables $x' \in X_j$. Given as input a square matrix $T$ whose entries are linear forms over ... more >>>


TR24-072 | 11th April 2024
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

Tropical proof systems

Propositional proof complexity deals with the lengths of polynomial-time verifiable proofs for Boolean tautologies. An abundance of proof systems is known, including algebraic and semialgebraic systems, which work with polynomial equations and inequalities, respectively. The most basic algebraic proof system is based on Hilbert's Nullstellensatz (Beame et al., 1996). Tropical ... more >>>


TR24-071 | 10th April 2024
Yahel Manor, Or Meir

Lifting with Inner Functions of Polynomial Discrepancy

Lifting theorems are theorems that bound the communication complexity
of a composed function $f\circ g^{n}$ in terms of the query complexity
of $f$ and the communication complexity of $g$. Such theorems
constitute a powerful generalization of direct-sum theorems for $g$,
and have seen numerous applications in recent years.

We prove ... more >>>


TR24-070 | 10th April 2024
Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

The notion of query-to-communication lifting theorems is a generic framework to convert query lower bounds into two-party communication lower bounds. Though this framework is very generic and beautiful, it has some inherent limitations such as it only applies to lifted functions. In order to address this issue, we propose gadgetless ... more >>>


TR24-069 | 8th April 2024
Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch

Character sums over AG codes

The Stepanov-Bombieri proof of the Hasse-Weil bound also gives non-trivial bounds on the bias of character sums over curves with small genus, for any low-degree function $f$ that is not completely biased. For high genus curves, and in particular for curves used in AG codes over constant size fields, the ... more >>>


TR24-068 | 10th April 2024
Pravesh Kothari, Peter Manohar

Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove:

(1) If $C$ is a linear design 3-LCC, then $n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every ... more >>>


TR24-067 | 10th April 2024
Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Breaking Square-Root Loss Barriers via Min-Entropy

Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. ... more >>>


TR24-066 | 29th March 2024
Siu On Chan, Hiu Tsun Ng, Sijin Peng

How Random CSPs Fool Hierarchies

Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), afinfe integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound ... more >>>


TR24-065 | 6th April 2024
Meghal Gupta, Mihir Singhal, Hongxun Wu

Optimal quantile estimation: beyond the comparison model

Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this ... more >>>


TR24-064 | 1st April 2024
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

No Complete Problem for Constant-Cost Randomized Communication

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with ... more >>>


TR24-063 | 6th April 2024
Shuichi Hirahara, Mikito Nanashima

One-Way Functions and Zero Knowledge

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of ... more >>>


TR24-062 | 5th April 2024
Omar Alrabiah, Venkatesan Guruswami

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

Revisions: 1

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a ... more >>>


TR24-061 | 5th April 2024
Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

Improved Lower Bounds for 3-Query Matching Vector Codes

A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m \ge 2$ is a pair of ordered lists $\mathcal{U} = (\mathbf{u}_1, \cdots, \mathbf{u}_K)$ and $\mathcal{V} = (\mathbf{v}_1, \cdots, \mathbf{v}_K)$ where $\mathbf{u}_i, \mathbf{v}_j \in \mathbb{Z}_m^n$ with the following property: for any $i \in [K]$, the inner product $\langle \mathbf{u}_i, \mathbf{v}_i \rangle ... more >>>


TR24-060 | 4th April 2024
Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Reverse Mathematics of Complexity Lower Bounds

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are necessary to prove a given theorem. In this work, we systematically explore the reverse mathematics of complexity lower bounds. We explore reversals in the setting of bounded arithmetic, with Cook's theory $\mathbf{PV}_1$ as the base ... more >>>


TR24-059 | 4th April 2024
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a ... more >>>


TR24-058 | 29th March 2024
Shuichi Hirahara, Nobutaka Shimizu

Planted Clique Conjectures Are Equivalent

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size $k \ll \sqrt{n}$ in an $n$-vertex Erd\H{o}s--R\'enyi random graph with a $k$-clique planted. In this paper, we prove the equivalence among many (in fact, \emph{most}) variants of planted clique conjectures, such as search ... more >>>


TR24-057 | 28th March 2024
Xi Chen, Yuhao Li, Mihalis Yannakakis

Computing a Fixed Point of Contraction Maps in Polynomial Queries

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.

more >>>

TR24-056 | 29th March 2024
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

Local Correction of Linear Functions over the Boolean Cube

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain $\{0,1\}^n$ over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance $1/2$ and we give local-correction algorithms correcting up to nearly $1/4$-fraction errors making $\widetilde{\mathcal{O}}(\log n)$ queries. This ... more >>>


TR24-055 | 12th March 2024
Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

Only a handful candidates for computational assumptions that imply secure key-agreement protocols (KA) are known, and even fewer are believed to be quantum safe. In this paper, we present a new hardness assumption---the worst-case hardness of a promise problem related to an interactive version of Kolmogorov Complexity.
Roughly speaking, the ... more >>>


TR24-054 | 13th March 2024
Karthik Gajulapalli, Alexander Golovnev, Samuel King

On the Power of Adaptivity for Function Inversion

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>


TR24-053 | 10th March 2024
Noam Mazor, Rafael Pass

Gap MCSP is not (Levin) NP-complete in Obfustopia

We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions.

In more detail:
- Assuming the existence of indistinguishability obfuscation, and ... more >>>


TR24-052 | 15th March 2024
Justin Yirka

Even quantum advice is unlikely to solve PP

We give a corrected proof that if PP $\subseteq$ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson, CCC 2006]. This recovers the related unconditional claim that PP does not have circuits of any fixed size $n^k$ even with quantum advice. We do so by proving that YQP*, ... more >>>


TR24-051 | 5th March 2024
Yanyi Liu, Rafael Pass

A Direct PRF Construction from Kolmogorov Complexity

While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.

Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various ... more >>>


TR24-050 | 5th March 2024
Omri Shmueli

Quantum Algorithms in a Superposition of Spacetimes

Revisions: 1

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>


TR24-049 | 7th March 2024
Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

Oblivious Classes Revisited: Lower Bounds and Hierarchies

In this work we study oblivious complexity classes. Among our results:
1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.
2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ... more >>>


TR24-048 | 4th March 2024
Kuan Cheng, Yichuan Wang

$BPL\subseteq L-AC^1$

Whether $BPL=L$ (which is conjectured to be equal), or even whether $BPL\subseteq NL$, is a big open problem in theoretical computer science. It is well known that $L-NC^1\subseteq L\subseteq NL\subseteq L-AC^1$. In this work we will show that $BPL\subseteq L-AC^1$, which was not known before. Our proof is based on ... more >>>


TR24-047 | 8th March 2024
Oded Goldreich

On the query complexity of testing local graph properties in the bounded-degree graph model

Revisions: 1

We consider the query complexity of testing local graph properties in the bounded-degree graph model.
A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.
Indeed, this formulation yields a generalized ... more >>>


TR24-046 | 6th March 2024
Sasank Mouli

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

For every $n >0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$ variables of size $O(n^3polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{\Omega(n)}$. This shows that Polynomial Calculus ... more >>>


TR24-045 | 6th March 2024
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

Redundancy for MaxSAT

The concept of redundancy in SAT lead to more expressive and powerful proof search techniques, e.g. able to express various inprocessing techniques, and to interesting hierarchies of proof systems [Heule et.al’20, Buss-Thapen’19].
We propose a general way to integrate redundancy rules in MaxSAT, that is we define MaxSAT variants of ... more >>>


TR24-044 | 28th February 2024
Rohit Gurjar, Taihei Oki, Roshan Raj

Fractional Linear Matroid Matching is in quasi-NC

The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose ... more >>>


TR24-043 | 4th March 2024
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>


TR24-042 | 22nd February 2024
Lisa Jaser, Jacobo Toran

Pebble Games and Algebraic Proof Systems Meet Again

Comments: 1

Analyzing refutations of the well known
pebbling formulas we prove some new strong connections between pebble games and algebraic proof system, showing that
there is a parallelism between the reversible, black and black-white pebbling games on one side, and
the three algebraic proof systems NS, MC and ... more >>>


TR24-041 | 1st March 2024
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Launching Identity Testing into (Bounded) Space

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).
First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ... more >>>


TR24-040 | 29th February 2024
Kuan Cheng, Ruiyang Wu

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant ... more >>>


TR24-039 | 20th February 2024
Shuichi Hirahara, Naoto Ohsaka

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

In the Minmax Set Cover Reconfiguration problem, given a set system $\mathcal{F}$ over a universe and its two covers $\mathcal{C}^\mathrm{start}$ and $\mathcal{C}^\mathrm{goal}$ of size $k$, we wish to transform $\mathcal{C}^\mathrm{start}$ into $\mathcal{C}^\mathrm{goal}$ by repeatedly adding or removing a single set of $\mathcal{F}$ while covering the universe in any intermediate state. ... more >>>


TR24-038 | 27th February 2024
Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann

Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

We initiate an in-depth proof-complexity analysis of polynomial calculus (Q-PC) for Quantified Boolean Formulas (QBF). In the course of this we establish a tight proof-size characterisation of Q-PC in terms of a suitable circuit model (polynomial decision lists). Using this correspondence we show a size-degree relation for Q-PC, similar in ... more >>>


TR24-037 | 26th February 2024
Yaroslav Alekseev, Yuval Filmus, Alexander Smal

Lifting dichotomies

Revisions: 1

Lifting theorems are used for transferring lower bounds between Boolean function complexity measures. Given a lower bound on a complexity measure $A$ for some function $f$, we compose $f$ with a carefully chosen gadget function $g$ and get essentially the same lower bound on a complexity measure $B$ for the ... more >>>


TR24-036 | 21st February 2024
Tal Yankovitz

A stronger bound for linear 3-LCC

Revisions: 2

A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the ... more >>>


TR24-035 | 20th February 2024
Sreejata Bhattacharya

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Revisions: 1

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial ... more >>>


TR24-034 | 19th February 2024
Bruno Loff, Alexey Milovanov

The hardness of decision tree complexity

Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is ... more >>>


TR24-033 | 24th February 2024
Sam Buss, Emre Yolcu

Regular resolution effectively simulates resolution

Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist sequences of formulas that require exponential-size proofs in regular resolution while admitting polynomial-size proofs in resolution. Thus, with ... more >>>


TR24-032 | 22nd February 2024
Joshua Cook, Dana Moshkovitz

Explicit Time and Space Efficient Encoders Exist Only With Random Access

We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes ... more >>>


TR24-031 | 22nd February 2024
Daniel Kane, Anthony Ostuni, Kewen Wu

Locality Bounds for Sampling Hamming Slices

Revisions: 1

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of ... more >>>


TR24-030 | 22nd February 2024
Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann

Proof Complexity of Propositional Model Counting

Recently, the proof system MICE for the model counting problem #SAT was introduced by Fichte, Hecher and Roland (SAT’22). As demonstrated by Fichte et al., the system MICE can be used for proof logging for state-of-the-art #SAT solvers.
We perform a proof-complexity study of MICE. For this we first simplify ... more >>>


TR24-029 | 16th February 2024
Noel Arteche, Gaia Carenini, Matthew Gray

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and ... more >>>


TR24-028 | 19th February 2024
Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>


TR24-027 | 18th February 2024
Dor Minzer, Kai Zhe Zheng

Near Optimal Alphabet-Soundness Tradeoff PCPs

We show that for all $\varepsilon>0$, for sufficiently large prime power $q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs ... more >>>


TR24-026 | 15th February 2024
Pavel Hrubes

A subquadratic upper bound on sum-of-squares compostion formulas

For every $n$, we construct a sum-of-squares identitity
\[ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2\,,\]
where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.
The same bound holds over any field of positive characteristic.

more >>>

TR24-025 | 13th February 2024
Mason DiCicco, Vladimir Podolskii, Daniel Reichman

Nearest Neighbor Complexity and Boolean Circuits

A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(x) = 1$ if and only if the closest anchor to $x$ is labeled by $1$. This model was introduced by Hajnal, Liu, and Turán (2022), who studied ... more >>>


TR24-024 | 14th February 2024
Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan

Strong Batching for Non-Interactive Statistical Zero-Knowledge

A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by ... more >>>


TR24-023 | 21st January 2024
Shuichi Hirahara, Naoto Ohsaka

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at ... more >>>


TR24-022 | 6th February 2024
Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak

Exponential Separation Between Powers of Regular and General Resolution Over Parities

Revisions: 1

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities, is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret (2008). Very recently, Efremenko, Garlik and Itsykson (2023) proved the first exponential lower bounds ... more >>>


TR24-021 | 29th January 2024
Prasad Chaugule, Nutan Limaye

On the closures of monotone algebraic classes and variants of the determinant

In this paper we prove the following two results.
* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. ... more >>>


TR24-020 | 2nd February 2024
Mitali Bafna, Noam Lifshitz, Dor Minzer

Constant Degree Direct Product Testers with Small Soundness

Revisions: 1

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>


TR24-019 | 2nd February 2024
Yotam Dikstein, Irit Dinur, Alexander Lubotzky

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Revisions: 1

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>


TR24-018 | 28th January 2024
Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = ... more >>>


TR24-017 | 23rd January 2024
Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

On Pigeonhole Principles and Ramsey in TFNP

The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t + 1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a ... more >>>


TR24-016 | 27th January 2024
Swagato Sanyal

Randomized query composition and product distributions

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... more >>>


TR24-015 | 9th January 2024
Harpreet Bedi

Degree 2 lower bound for Permanent in arbitrary characteristic

An elementary proof of quadratic lower bound for determinantal complexity of the permanent in positive characteristic is stated. This is achieved by constructing a sequence of matrices with zero permanent, but the rank of Hessian is bounded below by a degree two polynomial.

more >>>

TR24-014 | 28th January 2024
Elette Boyle, Ilan Komargodski, Neekon Vafa

Memory Checking Requires Logarithmic Overhead

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote ... more >>>


TR24-013 | 26th January 2024
Oded Goldreich

On locally-characterized expander graphs (a survey)

Revisions: 1

We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.
Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness.

We survey the work ... more >>>


TR24-012 | 26th January 2024
Hamed Hatami, Pooya Hatami

Structure in Communication Complexity and Constant-Cost Complexity Classes

Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often ... more >>>


TR24-011 | 24th January 2024
Paul Beame, Niels Kornerup

Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>


TR24-010 | 19th January 2024
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Black-Box PPP is not Turing-Closed

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>


TR24-009 | 20th January 2024
Dmytro Gavinsky

Unambiguous parity-query complexity

Comments: 1

We give a lower bound of ?(?n) on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over {0,1}? whose value is "0" if the Hamming weight of the input is at most n/3, is "1" if ... more >>>


TR24-008 | 17th January 2024
Pavel Hrubes

Hard submatrices for non-negative rank and communication complexity }

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always ... more >>>


TR24-007 | 25th December 2023
Karthik C. S., Pasin Manurangsi

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Revisions: 1

The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over ... more >>>


TR24-006 | 14th January 2024
Sabee Grewal, Justin Yirka

The Entangled Quantum Polynomial Hierarchy Collapses

We introduce the entangled quantum polynomial hierarchy $QEPH$ as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove $QEPH$ collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. ... more >>>


TR24-005 | 4th January 2024
Daniel Noble, Brett Hemenway, Rafail Ostrovsky

MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Revisions: 1

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, ... more >>>


TR24-004 | 7th January 2024
Omkar Baraskar, Agrim Dewan, Chandan Saha

Testing equivalence to design polynomials

An $n$-variate polynomial $g$ of degree $d$ is a $(n,d,t)$ design polynomial if the degree of the gcd of every pair of monomials of $g$ is at most $t-1$. The power symmetric polynomial $\mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i$ and the sum-product polynomial $\mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j}$ are instances of design polynomials ... more >>>


TR24-003 | 2nd January 2024
Noam Mazor, Rafael Pass

Search-to-Decision Reductions for Kolmogorov Complexity

A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-$t$ program generating a given string $x$ is at most $s$.

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


TR24-002 | 4th December 2023
Takashi Ishizuka

PLS is contained in PLC

Revisions: 1

Recently, Pasarkar, Papadimitriou, and Yannakakis (ITCS 2023) have introduced the new TFNP subclass called PLC that contains the class PPP; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the Sunflower lemma) belong to PLC. This short paper shows that the class ... more >>>


TR24-001 | 2nd January 2024
Sam Buss, Neil Thapen

A Simple Supercritical Tradeoff between Size and Height in Resolution

We describe CNFs in n variables which, over a range of parameters, have small resolution refutations but are such that any small refutation must have height larger than n (even exponential in n), where the height of a refutation is the length of the longest path in it. This is ... more >>>




ISSN 1433-8092 | Imprint