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-201 | 4th December 2024
Marius Zimand

On one-way functions and the average time complexity of almost-optimal compression

We show that one-way functions exist if and only there exists an efficient distribution relative to which almost-optimal compression is hard on average. The result is obtained by combining a theorem of Ilango, Ren, and Santhanam [STOC 2022] and one by Bauwens and Zimand [JACM, 2023].

more >>>

TR24-200 | 4th December 2024
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on $\{0,1\}^n$, where $n$ is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by ... more >>>


TR24-199 | 3rd December 2024
Vladimir Podolskii, Alexander Shekhovtsov

Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity

We study query-to-communication lifting. The major open problem in this area is to prove a lifting theorem for gadgets of constant size. The recent paper (Beame, Koroth, 2023) introduces semi-structured communication complexity, in which one of the players can only send parities of their input bits. They have shown that ... more >>>


TR24-198 | 10th November 2024
G V Sumukha Bharadwaj, Raja S

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits

Revisions: 1

In this paper, we address the black-box polynomial identity testing (PIT) problem for non-commutative polynomials computed by $+$-regular circuits, a class of homogeneous circuits introduced by Arvind, Joglekar, Mukhopadhyay, and Raja (STOC 2017, Theory of Computing 2019). These circuits can compute polynomials with a number of monomials that are doubly ... more >>>


TR24-197 | 29th November 2024
Pranjal Dutta, Amit Sinhababu, Thomas Thierauf

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

For a polynomial $f$ from a class $\mathcal{C}$ of polynomials, we show that the problem to compute all the constant degree irreducible factors of $f$ reduces in polynomial time to polynomial identity tests (PIT) for class $\mathcal{C}$ and divisibility tests of $f$ by constant degree polynomials. We apply the result ... more >>>


TR24-196 | 2nd December 2024
Clement Canonne, Sayantan Sen, Qiping Yang

Settling the complexity of testing grainedness of distributions, and application to uniformity testing in the Huge Object model

In this work, we study the problem of testing $m$-\emph{grainedness} of probability distributions over an $n$-element universe $\mathcal{U}$, or, equivalently, of whether a probability distribution is induced by a multiset $S\subseteq \mathcal{U}$ of size $|S|=m$. Recently, Goldreich and Ron (Computational Complexity, 2023) proved that $\Omega(n^c)$ samples are necessary for testing ... more >>>


TR24-195 | 28th November 2024
Yanyi Liu, Noam Mazor, Rafael Pass

On White-Box Learning and Public-Key Encryption

We consider a generalization of the Learning With Error problem, referred to as the white-box learning problem: You are given the code of a sampler that with high probability produces samples of the form $y, f (y) + \epsilon$ where $\epsilon$ is small, and $f$ is computable in polynomial-size, and ... more >>>


TR24-194 | 28th November 2024
Yanyi Liu, Noam Mazor, Rafael Pass

On Witness Encryption and Laconic Zero-Knowledge Arguments

Witness encryption (WE) (Garg et al, STOC’13) is a powerful cryptographic primitive that is closely related to the notion of indistinguishability obfuscation (Barak et, JACM’12, Garg et al, FOCS’13). For a given NP-language $L$, WE for $L$ enables encrypting a message $m$ using an instance $x$ as the public-key, while ... more >>>


TR24-193 | 22nd November 2024
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

Reasonable Bounds for Combinatorial Lines of Length Three

We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log\log\log\log n)^{-c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, with $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for all $i = 1, 2, \dots, n$. This improves on the previous best bound of $3^{-n}|A| ... more >>>


TR24-192 | 22nd November 2024
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

On Approximability of Satisfiable k-CSPs: VII

Let $\Sigma_1,\ldots,\Sigma_k$ be finite alphabets, and let $\mu$ be a distribution over $\Sigma_1 \times \dots \times \Sigma_k$ in which the probability of each atom is at least $\alpha$. We prove that if $\mu$ does not admit Abelian embeddings, and $f_i: \Sigma_i \to \mathbb{C}$ are $1$-bounded functions (for $i=1,\ldots,k$) such that ... more >>>


TR24-191 | 22nd November 2024
Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

On Approximability of Satisfiable k-CSPs: VI

We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\mu$ be a distribution over $\Sigma \times \Gamma \times \Phi$ such that the supports of $\mu_{xy}$, $\mu_{xz}$, and $\mu_{yz}$ are all connected, and let $f: \Sigma^n \to \mathbb{C}$, $g: \Gamma^n \to \mathbb{C}$, $h: \Phi^n \to ... more >>>


TR24-190 | 22nd November 2024
Jiawei Li, Yuhao Li, Hanlin Ren

Metamathematics of Resolution Lower Bounds: A TFNP Perspective

This paper studies the \emph{refuter} problems, a family of decision-tree $\mathrm{TFNP}$ problems capturing the metamathematical difficulty of proving proof complexity lower bounds. Suppose $\varphi$ is a hard tautology that does not admit any length-$s$ proof in some proof system $P$. In the corresponding refuter problem, we are given (query ... more >>>


TR24-189 | 21st November 2024
Arpon Basu, Junting Hsieh, Pravesh Kothari, Andrew Lin

Improved Lower Bounds for all Odd-Query Locally Decodable Codes

We prove that for every odd $q\geq 3$, any $q$-query binary, possibly non-linear locally decodable code ($q$-LDC) $E:\{\pm 1\}^k \rightarrow \{\pm 1\}^n$ must satisfy $k \leq \tilde{O}(n^{1-2/q})$. For even $q$, this bound was established in a sequence of works (Katz and Trevisan (2000), Goldreich, Karloff, Schulman, and Trevisan (2002), and ... more >>>


TR24-188 | 21st November 2024
Edward Pyne, Nathan Sheffield, William Wang

Catalytic Communication

The study of space-bounded computation has drawn extensively from ideas and results in the field of communication complexity. Catalytic Computation (Buhrman, Cleve, Koucký, Loff and Speelman, STOC 2013) studies the power of bounded space augmented with a pre-filled hard drive that can be used non-destructively during the computation. Presently, many ... more >>>


TR24-187 | 21st November 2024
Oliver Janzer, Peter Manohar

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-query locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by querying a corrupted string $\tilde{x}$ of the codeword $x = C(b)$ in at most $q$ coordinates. For $2$ ... more >>>


TR24-186 | 21st November 2024
Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov

Supercritical Tradeoffs for Monotone Circuits

We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the first size-depth tradeoff result for monotone circuits in the so-called supercritical regime. Our proof is based on an analogous result in proof complexity: ... more >>>


TR24-185 | 21st November 2024
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman

We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the ... more >>>


TR24-184 | 7th November 2024
Fernando Jeronimo, Nir Magrafta, Joseph Slote, Pei Wu

Coherence in Property Testing: Quantum-Classical Collapses and Separations

Understanding the power and limitations of classical and quantum information, and how they differ, is an important endeavor. On the classical side, property testing of distributions is a fundamental task: a tester, given samples of a distribution over a typically large domain such as $\{0,1\}^n$, is asked to verify properties ... more >>>


TR24-183 | 20th November 2024
Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan

Improved PIR Schemes using Matching Vectors and Derivatives

In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector
based PIRs of Yekhanin and Efremenko. Previously ... more >>>


TR24-182 | 17th November 2024
Lijie Chen, Jiatu Li, Jingxun Liang

Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice ($AMEXP_{/2^{n^{\varepsilon}}}$) requires circuit complexity at least $2^n/n$. Previously, the best known such near-maximum lower bounds were for symmetric exponential time by Chen, Hirahara, and Ren (STOC'24) and Li (STOC'24), or randomized exponential time with MCSP oracle and ... more >>>


TR24-181 | 13th November 2024
Tomer Gewirtzman, Ron Rothblum

Zero-Knowledge in Streaming Interactive Proofs

In a recent work, Cormode, Dall'Agnol, Gur and Hickey (CCC, 2024) introduced the model of Zero-Knowledge Streaming Interactive Proofs (zkSIPs).
Loosely speaking, such proof-systems enable a prover to convince astreaming verifier that the input $x$, to which it has read-once streaming access, satisfies some property, in such a way that ... more >>>


TR24-180 | 13th November 2024
Daniel Kane, Anthony Ostuni, Kewen Wu

Locally Sampleable Uniform Symmetric Distributions

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{0,1\}^m\to\{0,1\}^n$ be a Boolean function where each output bit of $f$ depends only on $O(1)$ input bits. Assume the output distribution of $f$ on uniform input bits is close to a uniform distribution $\mathcal D$ with ... more >>>


TR24-179 | 21st October 2024
Norbert Blum

On the approximation method and the P versus NP problem

First of all we give some reasons that “natural proofs” built not a barrier to prove P not= NP using Boolean complexity. Then we investigate the approximation method for its extension to prove super-polynomial lower bounds for the non-monotone complexity of suitable Boolean functions in NP or to understand why ... more >>>


TR24-178 | 5th November 2024
Noah Fleming, Yuichi Yoshida

Sensitivity Lower Bounds for Approximaiton Algorithms

Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms. In this work, we establish the ... more >>>


TR24-177 | 29th October 2024
Swastik Kopparty, Harry Sha

Small Shadow Partitions

We study the problem of partitioning the unit cube $[0,1]^n$ into $c$ parts so that each $d$-dimensional axis-parallel projection has small volume.

This natural combinatorial/geometric question was first studied by Kopparty and Nagargoje [KN23] as a reformulation of the problem of determining the achievable parameters for seedless multimergers -- which ... more >>>


TR24-176 | 12th November 2024
Dean Doron, Joao Ribeiro

Nearly-Linear Time Seeded Extractors with Short Seeds

Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameters. However, existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n \log(1/\varepsilon))$ and often slower, where $n$ is the input ... more >>>


TR24-175 | 4th November 2024
Mark Braverman, Or Zamir

Optimality of Frequency Moment Estimation

Estimating the second frequency moment of a stream up to $(1\pm\varepsilon)$ multiplicative error requires at most $O(\log n / \varepsilon^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $\Omega(\log n + 1/\varepsilon^{2})$ space is needed.
We prove an ... more >>>


TR24-174 | 13th November 2024
Albert Atserias, Iddo Tzameret

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets

The Schwartz-Zippel Lemma states that if a low-degree multivariate polynomial with coefficients in a field is not zero everywhere in the field, then it has few roots on every finite subcube of the field. This fundamental fact about multivariate polynomials has found many applications in algorithms, complexity theory, coding theory, ... more >>>


TR24-173 | 29th October 2024
Songhua He, Yuanzhi Li, Periklis Papakonstantinou, Xin Yang

Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL

This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL). ... more >>>


TR24-172 | 5th November 2024
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

Quantum Communication Advantage in TFNP

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of ... more >>>


TR24-171 | 6th November 2024
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

Condensing against Online Adversaries

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective random sources for which it is known that extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks $\mathbf{X} = (\mathbf{X}_1, \dots, \mathbf{X}_{\ell})\sim (\{0, 1\}^{n})^{\ell}$, where ... more >>>


TR24-170 | 5th November 2024
Michael Jaber, Shachar Lovett, Anthony Ostuni

Corners in Quasirandom Groups via Sparse Mixing

We improve the best known upper bounds on the density of corner-free sets over quasirandom groups from inverse poly-logarithmic to quasi-polynomial. We make similarly substantial improvements to the best known lower bounds on the communication complexity of a large class of permutation functions in the 3-player Number-on-Forehead model. Underpinning both ... more >>>


TR24-169 | 4th November 2024
Clément Canonne, Francis Su, Salil Vadhan

The Randomness Complexity of Differential Privacy

We initiate the study of the *randomness complexity* of differential privacy, i.e., how many random bits an algorithm needs in order to generate accurate differentially private releases. As a test case, we focus on the task of releasing the results of $d$ counting queries, or equivalently all one-way marginals on ... more >>>


TR24-168 | 3rd November 2024
Ronen Shaltiel

Multiplicative Extractors for Samplable Distributions

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions as a possible solution to the problem of extracting random keys for cryptographic protocols from weak sources of randomness.
They showed that under a very strong complexity theoretic assumption, there exists a constant $\alpha>0$ such that ... more >>>


TR24-167 | 31st October 2024
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang

Space-bounded quantum interactive proof systems

We introduce two models of space-bounded quantum interactive proof systems, $\mathbf{QIPL}$ and $\mathbf{QIP_\mathrm{U}L}$. The $\mathbf{QIP_\mathrm{U}L}$ model, a space-bounded variant of quantum interactive proofs ($\mathbf{QIP}$) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, $\mathbf{QIPL}$ allows logarithmically many intermediate measurements per ... more >>>


TR24-166 | 16th October 2024
John Bostanci, Yeongwoo Hwang

Commuting Local Hamiltonians Beyond 2D

Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely ... more >>>


TR24-165 | 21st October 2024
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Online Condensing of Unpredictable Sources via Random Walks

A natural model of a source of randomness consists of a long stream of symbols $X = X_1\circ\ldots\circ X_t$, with some guarantee on the entropy of $X_i$ conditioned on the outcome of the prefix $x_1,\dots,x_{i-1}$. We study unpredictable sources, a generalization of the almost Chor--Goldreich (CG) sources considered in [DMOZ23]. ... more >>>


TR24-164 | 25th October 2024
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

Low Degree Local Correction Over the Boolean Cube

In this work, we show that the class of multivariate degree-$d$ polynomials mapping $\{0,1\}^{n}$ to any Abelian group $G$ is locally correctable with $\widetilde{O}_{d}((\log n)^{d})$ queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials ... more >>>


TR24-163 | 24th October 2024
Roei Tell

On defining PPT-search problems and PPT-optimization problems

This note revisits the study of search problems that are solvable in probabilistic polynomial time. Previously, Goldreich (2011) introduced a class called ``$\mathcal{BPP}$-search'', and studied search-to-decision reductions for problems in this class.

In Goldreich's original formulation, the definition of what counts as ``successfully solving'' a $\mathcal{BPP}$-search problem is implicit, and ... more >>>


TR24-162 | 24th October 2024
Agnes Schleitzer, Olaf Beyersdorff

Computationally Hard Problems Are Hard for QBF Proof Systems Too

Revisions: 1

There has been tremendous progress in the past decade in the field of quantified Boolean formulas (QBF), both in practical solving as well as in creating a theory of corresponding proof systems and their proof complexity analysis. Both for solving and for proof complexity, it is important to have interesting ... more >>>


TR24-161 | 24th October 2024
Oded Goldreich

On defining PPT-search problems

We propose a new definition of the class of search problems that correspond to BPP.
Specifically, a problem in this class is specified by a polynomial-time approximable function $q:\{0,1\}^*\times\{0,1\}^*\to[0,1]$ that associates, with each possible solution $y$ to an instance $x$, a quality $q(x,y)$.
Intuitively, quality 1 corresponds to perfectly ... more >>>


TR24-160 | 1st October 2024
igor razgon

The splitting power of branching programs of bounded repetition and CNFs of bounded width

In this paper we study syntactic branching programs of bounded repetition
representing CNFs of bounded treewidth.
For this purpose we introduce two new structural graph
parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted
by $pw_d(G)$ and $cpw_d(G)$ where $G$ is a graph.
We show that $cpw_2(G) \leq O(tw(G) \Delta(G))$ ... more >>>


TR24-159 | 19th October 2024
Dean Doron

Binary Codes with Distance Close to Half

We survey recent and classical results and techniques concerning binary codes in the large distance (or, high-noise) regime, and the closely related notion of $\varepsilon$-balanced codes. Our (hopefully small-biased) column will mainly discuss encoding, and decoding from adversarial errors.

A previous version of this text originally appeared as an ACM ... more >>>


TR24-158 | 18th October 2024
Xin Li, Songtao Mao

Improved Explicit Near-Optimal Codes in the High-Noise Regimes

Revisions: 1

We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding ... more >>>


TR24-157 | 17th October 2024
Yupan Liu, Qisheng Wang

On estimating the trace of quantum state powers

We investigate the computational complexity of estimating the trace of quantum state powers $\text{tr}(\rho^q)$ for an $n$-qubit mixed quantum state $\rho$, given its state-preparation circuit of size $\text{poly}(n)$. This quantity is closely related to and often interchangeable with the Tsallis entropy $\text{S}_q(\rho) = \frac{1-\text{tr}(\rho^q)}{q-1}$, where $q = 1$ corresponds to ... more >>>


TR24-156 | 7th October 2024
Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall

A Meta-Complexity Characterization of Quantum Cryptography

We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity. Therefore, we characterize one-way puzzles by the average-case hardness of a ... more >>>


TR24-155 | 11th October 2024
Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

The coding theorem for Kolmogorov complexity states that any string sampled from a computable distribution has a description length close to its information content. A coding theorem for resource-bounded Kolmogorov complexity is the key to obtaining fundamental results in average-case complexity, yet whether any samplable distribution admits a coding theorem ... more >>>


TR24-154 | 10th October 2024
Jesse Goodman, Xin Li, David Zuckerman

Improved Condensers for Chor-Goldreich Sources

One of the earliest models of weak randomness is the Chor-Goldreich (CG) source. A $(t,n,k)$-CG source is a sequence of random variables $\mathbf{X}=(\mathbf{X}_1,\dots,\mathbf{X}_t) \sim (\{0,1\}^n)^t$, where each $\mathbf{X}_i$ has min-entropy $k$ conditioned on any fixing of $\mathbf{X}_1,\dots,\mathbf{X}_{i-1}$. Chor and Goldreich proved that there is no deterministic way to extract randomness ... more >>>


TR24-152 | 5th October 2024
Alexander A. Sherstov, Andrey Storozhenko

The Communication Complexity of Approximating Matrix Rank

We fully determine the communication complexity of approximating matrix rank, over any finite field $\mathbb{F}$. We study the most general version of this problem, where $0\leq r < R\leq n$ are given integers, Alice and Bob's inputs are matrices $A,B\in\mathbb{F}^{n\times n}$, respectively, and they need to distinguish between the cases ... more >>>


TR24-151 | 2nd October 2024
Vijay Bhattiprolu, Euiwoong Lee

Inapproximability of Sparsest Vector in a Real Subspace

Revisions: 1

We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace (where sparsity refers to the number of nonzero entries). Formally we show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor. By simple tensoring the inapproximability ... more >>>


TR24-150 | 2nd October 2024
Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

Characterizing and Testing Principal Minor Equivalence of Matrices

Two matrices are said to be principal minor equivalent if they have equal
corresponding principal minors of all orders. We give a characterization of
principal minor equivalence and a deterministic polynomial time algorithm to
check if two given matrices are principal minor equivalent. Earlier such
results were known for ... more >>>


TR24-149 | 24th September 2024
Noor Athamnah, Ron D. Rothblum, Eden Florentz – Konopnicki

Rate-1 Zero-Knowledge Proofs from One-Way Functions

We show that every NP relation that can be verified by a bounded-depth polynomial-sized circuit, or a bounded-space polynomial-time algorithm, has a computational zero-knowledge proof (with statistical soundness) with communication that is only additively larger than the witness length. Our construction relies only on the minimal assumption that one-way functions ... more >>>


TR24-148 | 5th October 2024
Swastik Kopparty, Mrinal Kumar, Harry Sha

High Rate Multivariate Polynomial Evaluation Codes

Revisions: 1

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes ... more >>>


TR24-147 | 4th October 2024
Shanthanu Rai

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree $d$ over finite field $\mathbb{F}_q$. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time $\tilde{O}(d^4 \log^4{q})$.

Our construction extends Shoup's deterministic algorithm ... more >>>


TR24-146 | 27th September 2024
Zhenjian Lu, Noam Mazor, Igor Oliveira, Rafael Pass

Lower Bounds on the Overhead of Indistinguishability Obfuscation

We consider indistinguishability obfuscation (iO) for multi-output circuits $C:\{0,1\}^n\to\{0,1\}^n$ of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP $\nsubseteq$ BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size $s + o(s/ \log s)$. ... more >>>


TR24-145 | 2nd October 2024
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas

Provability of the Circuit Size Hierarchy and Its Consequences

The Circuit Size Hierarchy CSH$^a_b$ states that if $a > b \geq 1$ then the set of functions on $n$ variables computed by Boolean circuits of size $n^a$ is strictly larger than the set of functions computed by circuits of size $n^b$. This result, which is a cornerstone of circuit ... more >>>


TR24-144 | 16th September 2024
Dar Gilboa, Siddhartha Jain, Jarrod McClean

Consumable Data via Quantum Communication

Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds $m$ inputs, and he wants to compute $m$ instances of a bipartite relation ... more >>>


TR24-143 | 25th September 2024
Noga Amir, Oded Goldreich, Guy Rothblum

Doubly Sub-linear Interactive Proofs of Proximity

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which

1. The query-complexity of verification is significantly smaller than the query-complexity of testing.

2. The query-complexity of the ... more >>>


TR24-142 | 17th September 2024
Ryan Williams

The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential ... more >>>


TR24-141 | 12th September 2024
Tal Herman

Public Coin Interactive Proofs for Label-Invariant Distribution Properties

Assume we are given sample access to an unknown distribution $D$ over a large domain $[N]$. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, ... more >>>


TR24-140 | 11th September 2024
Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, Jayalal Sarma

Almost-catalytic Computation

Revisions: 1

Designing algorithms for space bounded models with restoration requirements on (most of) the space used by the algorithm is an important challenge posed about the catalytic computation model introduced by Buhrman et al (2014). Motivated by the scenarios where we do not need to restore unless $w$ is "useful", we ... more >>>


TR24-139 | 11th September 2024
Jiatu Li, Edward Pyne, Roei Tell

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness

This paper revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the ``reconstruction paradigm'' in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and ... more >>>


TR24-138 | 8th September 2024
Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker

Fully Characterizing Lossy Catalytic Computation

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. ... more >>>


TR24-137 | 9th September 2024
Dean Doron, William Hoza

Implications of Better PRGs for Permutation Branching Programs

We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let $c \in [1, 2)$ be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-$6$ length-$n$ permutation ROBPs with error $1/n$ and seed length $\widetilde{O}(\log^c n)$, then there are explicit hitting set generators ... more >>>


TR24-136 | 4th September 2024
Shuichi Hirahara, Zhenjian Lu, Igor Oliveira

One-Way Functions and pKt Complexity

We introduce $\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathrm{Kt}$ complexity. Using $\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following ... more >>>


TR24-133 | 7th September 2024
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao

Two-Sided Lossless Expanders in the Unbalanced Setting

Revisions: 1

We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our work, all known explicit constructions in the unbalanced setting achieved only one-sided lossless expansion.

Specifically, we show ... more >>>


TR24-132 | 6th September 2024
Arkadev Chattopadhyay, Pavel Dvorak

Super-critical Trade-offs in Resolution over Parities Via Lifting

Razborov [J. ACM, 2016] exhibited the following surprisingly strong trade-off phenomenon in propositional proof complexity: for a parameter $k = k(n)$, there exists $k$-CNF formulas over $n$ variables, having resolution refutations of $O(k)$ width, but every tree-like refutation of width $n^{1-\epsilon}/k$ needs size $\text{exp}\big(n^{\Omega(k)}\big)$. We extend this result to tree-like ... more >>>


TR24-131 | 5th September 2024
Hadar Strauss

Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model

Revisions: 1

Interactive proofs of proximity (IPPs) for a property are relaxed proof systems analogous to property testers in which the goal is for the verifier to be convinced to accept inputs that are in the property, and to not be fooled into accepting inputs that are far from the property.

... more >>>

TR24-130 | 30th August 2024
Sabee Grewal, Vinayak Kumar

Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits

Revisions: 1

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss ... more >>>


TR24-129 | 27th August 2024
Amey Bhangale, Subhash Khot, Dor Minzer

On Approximability of Satisfiable k-CSPs: V

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs.

Our framework is based on a new hybrid approximation algorithm, which uses ... more >>>


TR24-128 | 27th August 2024
Yaroslav Alekseev, Dmitry Itsykson

Lifting to regular resolution over parities via games

Revisions: 1

The propositional proof system resolution over parities (Res($\oplus$)) combines resolution and the linear algebra over GF(2). It is a challenging open question to prove a superpolynomial lower bound on the proof size in this system. For many years, superpolynomial lower bounds were known only in tree-like cases. Recently, Efremenko, Garlik, ... more >>>


TR24-127 | 28th July 2024
Bill Fefferman, Soumik Ghosh, Wei Zhan

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits

We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random ... more >>>


TR24-126 | 17th June 2024
Takashi Ishizuka

On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König

One of the most famous TFNP subclasses is PPP, which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [ECCC TR24-002 2024] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon, and ... more >>>


TR24-125 | 19th July 2024
Pavel Hrubes, Pushkar Joglekar

On read-$k$ projections of the determinant

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>


TR24-124 | 26th July 2024
Oded Goldreich

Solving Tree Evaluation in $o(\log n \cdot \log\log n)$ space

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings,and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, where ... more >>>


TR24-123 | 22nd July 2024
Vishwas Bhargava, Devansh Shringi

Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

We present a deterministic $2^{k^{\mathcal{O}(1)}} \text{poly}(n,d)$ time algorithm for decomposing $d$-dimensional, width-$n$ tensors of rank at most $k$ over $\mathbb{R}$ and $\mathbb{C}$. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes $2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d)$ time and the deterministic $n^{k^k}$ time algorithms of Bhargava, Saraf, ... more >>>


TR24-122 | 28th June 2024
Antoine Joux, Anand Kumar Narayanan

A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants

We present a new algorithm for solving homogeneous multilinear equations, which are high dimensional generalisations of solving homogeneous linear equations. First, we present a linear time reduction from solving generic homogeneous multilinear equations to computing hyperdeterminants, via a high dimensional Cramer's rule. Hyperdeterminants are generalisations of determinants, associated with tensors ... more >>>


TR24-121 | 16th July 2024
Nader Bshouty

Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Revisions: 1

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>


TR24-120 | 15th July 2024
Halley Goldberg, Valentine Kabanets

Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK$^t$P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, ... more >>>


TR24-119 | 14th July 2024
Vishwas Bhargava, Anamay Tengse

Explicit Commutative ROABPs from Partial Derivatives

The dimension of partial derivatives (Nisan and Wigderson, 1997) is a popular measure for proving lower bounds in algebraic complexity. It is used to give strong lower bounds on the Waring decomposition of polynomials (called Waring rank). This naturally leads to an interesting open question: does this measure essentially characterize ... more >>>


TR24-118 | 9th July 2024
Amnon Ta-Shma, Ron Zadiario

The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

Numerous works have studied the probability that a length $t-1$ random walk on an expander is confined to a given rectangle $S_1 \times \ldots \times S_t$, providing both upper and lower bounds for this probability.
However, when the densities of the sets $S_i$ may depend on the walk length (e.g., ... more >>>


TR24-117 | 12th June 2024
Ludmila Glinskih, Artur Riazanov

Partial Minimum Branching Program Size Problem is ETH-hard

We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-$k$ branching programs and OBDDs.

Combining these results with our recent result (Glinskih ... more >>>


TR24-116 | 6th July 2024
Lijie Chen, Ron D. Rothblum, Roei Tell

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.

Our results concern fundamental questions in ... more >>>


TR24-115 | 14th July 2024
Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

On the Complexity of Avoiding Heavy Elements

We introduce and study the following natural total search problem, which we call the {\it heavy element avoidance} (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N) \ge 1/\poly(N)$ fixed in advance, output an $N$-bit string that has ... more >>>


TR24-114 | 12th July 2024
Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu

Dot-Product Proofs and Their Applications

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can ... more >>>


TR24-113 | 4th July 2024
Nikhil Vyas, Ryan Williams

On Oracles and Algorithmic Methods for Proving Lower Bounds

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.

1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let ... more >>>


TR24-112 | 3rd July 2024
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

The Rate of Interactive Codes is Bounded Away from 1

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this ... more >>>


TR24-111 | 1st July 2024
Siddharth Iyer, Anup Rao

An XOR Lemma for Deterministic Communication Complexity

We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log rk(f)} -\log rk(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the ... more >>>


TR24-110 | 1st July 2024
Joshua Cook, Dana Moshkovitz

Time and Space Efficient Deterministic Decoders

Revisions: 1

Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.
Gronemeier showed that any non-adaptive deterministic decoder for a good code running ... more >>>


TR24-109 | 29th June 2024
Oded Goldreich

On the Cook-Mertz Tree Evaluation procedure

Revisions: 1

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.
The desired output is the value of the root, ... more >>>


TR24-108 | 28th June 2024
Benny Applebaum, Eliran Kachlon

Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC

The problem of minimizing the share size of threshold secret-sharing schemes is a basic research question that has been extensively studied. Ideally, one strives for schemes in which the share size equals the secret size. While this is achievable for large secrets (Shamir, CACM '79), no similar solutions are known ... more >>>


TR24-107 | 23rd June 2024
Benjamin Rossman

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication

We study the formula complexity of Iterated Sub-Permutation Matrix Multiplication, the logspace-complete problem of computing the product of $k$ $n$-by-$n$ Boolean matrices with at most a single $1$ in each row and column. For all $d \le \log k$, this problem is solvable by $n^{O(dk^{1/d})}$ size monotone formulas of two ... more >>>


TR24-106 | 17th June 2024
James Cook, Jiatu Li, Ian Mertz, Edward Pyne

The Structure of Catalytic Space: Capturing Randomness and Time via Compression

In the catalytic logspace ($CL$) model of (Buhrman et.~al.~STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. This ... more >>>


TR24-105 | 13th June 2024
Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran

Communication Complexity vs Randomness Complexity in Interactive Proofs

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random ... more >>>


TR24-104 | 12th June 2024
Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>


TR24-103 | 11th June 2024
Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal

Relations between monotone complexity measures based on decision tree complexity

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to $\log n$ factor, for any Boolean function composed with $AND$ function as the inner gadget. One of the main tools in this result was the relationship between monotone analogues of ... more >>>


TR24-102 | 29th May 2024
Inbar Ben Yaacov, Yotam Dikstein, Gal Maor

Sparse High Dimensional Expanders via Local Lifts

Revisions: 1

High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex ... more >>>


TR24-101 | 21st May 2024
Or Keret, Ron Rothblum, Prashant Nalini Vasudevan

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK protocol for proving that $x_1,\dots,x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. ... more >>>


TR24-100 | 21st May 2024
Changrui Mu, Prashant Nalini Vasudevan

Instance-Hiding Interactive Proofs

Revisions: 2

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn ... more >>>


TR24-099 | 5th June 2024
Pavel Hrubes

A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials

For every $n$, we construct a sum-of-squares identity
$ (\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.

As an application to ... more >>>


TR24-098 | 26th May 2024
Noga Amit, Orr Paradise, Guy Rothblum, shafi goldwasser

Models That Prove Their Own Correctness

Revisions: 2

How can we trust the correctness of a learned model on a particular input of interest? Model accuracy is typically measured $on\ average$ over a distribution of inputs, giving no guarantee for any fixed input. This paper proposes a theoretically-founded solution to this problem: to train $Self$-$Proving\ models$ that prove ... more >>>


TR24-097 | 31st May 2024
Zhiyang Xun, David Zuckerman

Near-Optimal Averaging Samplers

Revisions: 4

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity for natural parameter choices. Specifically, for any constant $\alpha > 0$, for $\delta > 2^{-\mathrm{poly}(1 / \varepsilon)}$, it uses $m + O(\log (1 / \delta))$ random bits to output $t = O(\log(1 ... more >>>


TR24-096 | 27th May 2024
Noga Amit, Guy Rothblum

Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions

Revisions: 2

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on ... more >>>


TR24-095 | 23rd May 2024
Yanyi Liu, Noam Mazor, Rafael Pass

A Note on Zero-Knowledge for NP and One-Way Functions

Revisions: 1

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be ... more >>>


TR24-094 | 19th May 2024
Tal Herman, Guy Rothblum

Interactive Proofs for General Distribution Properties

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using ... more >>>


TR24-093 | 16th May 2024
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

Low-Degree Polynomials Are Good Extractors

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>


TR24-092 | 16th May 2024
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

Hilbert Functions and Low-Degree Randomness Extractors

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>


TR24-091 | 14th May 2024
Dean Doron, Jonathan Mosheiff, Mary Wootters

When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound?

Revisions: 1

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.

One hope to ... more >>>


TR24-090 | 12th May 2024
Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz

A Study of Error Reduction Polynomials

Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, ... more >>>


TR24-089 | 8th May 2024
Gil Cohen, Itay Cohen, Gal Maor

Tight Bounds for the Zig-Zag Product

The Zig-Zag product of two graphs, $Z = G \circ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of ... more >>>


TR24-088 | 29th April 2024
Tamer Mour, Alon Rosen, Ron Rothblum

Locally Testable Tree Codes

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good ... more >>>


TR24-087 | 27th April 2024
Renato Ferreira Pinto Jr.

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach

Revisions: 1

This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further ... more >>>


TR24-086 | 24th April 2024
Hao Wu

A nearly-$4\log n$ depth lower bound for formulas with restriction on top

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. ... more >>>


TR24-085 | 25th April 2024
Zhenjian Lu, Rahul Santhanam

Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity

We develop new characterizations of Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the intractability of conditional Kolmogorov complexity $\mathrm{K}$ and conditional probabilistic time-bounded Kolmogorov complexity $\mathrm{pK}^t$.

In our first set of results, we show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently in the worst case ... more >>>


TR24-084 | 24th April 2024
Vikraman Arvind, Pushkar Joglekar

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Revisions: 1

We study the \emph{noncommutative rank} problem, $\NCRANK$, of computing the rank of matrices with linear entries in $n$ noncommuting variables and the problem of \emph{noncommutative Rational Identity Testing}, $\RIT$, which is to decide if a given rational formula in $n$ noncommuting variables is zero on its domain of definition.

... more >>>


TR24-083 | 18th April 2024
Lijie Chen, Jiatu Li, Igor Carboni Oliveira

On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. ... more >>>


TR24-082 | 17th April 2024
Yotam Dikstein, Max Hopkins

Chernoff Bounds and Reverse Hypercontractivity on HDX

Revisions: 1

We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let $X$ be a $k$-dimensional HDX. We show for any $i \leq k$ and function $f: X(i) \to [0,1]$:
\[
\Pr_{s \in X(k)}\left[\left|\underset{{t \subseteq s}}{\mathbb{E}}[f(t)] - \mu \right| \geq \varepsilon \right] \leq \exp\left(-\varepsilon^2 \frac{k}{i}\right).
\]
Using ... more >>>


TR24-081 | 2nd April 2024
Sravanthi Chede, Leroy Chew, Anil Shukla

Circuits, Proofs and Propositional Model Counting

Revisions: 1

In this paper we present a new proof system framework CLIP (Cumulation Linear Induction Proposition) for propositional model counting. A CLIP proof firstly involves a circuit, calculating the cumulative function (or running count) of models counted up to a point, and secondly a propositional proof arguing for the correctness of ... more >>>


TR24-080 | 16th April 2024
Robert Andrews, Avi Wigderson

Constant-Depth Arithmetic Circuits for Linear Algebra Problems

We design polynomial size, constant depth (namely, $AC^0$) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Our GCD algorithm extends to any ... more >>>


TR24-079 | 20th April 2024
Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for
deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ... more >>>


TR24-078 | 19th April 2024
Oded Goldreich

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

Revisions: 1

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

Revisions: 5

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 1

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

Revisions: 2

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

Revisions: 1

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

Revisions: 1

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 }

Revisions: 1

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

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

Revisions: 1

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