All reports in year 2024:

__
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

__
TR24-074
| 11th April 2024
__

Vaibhav Krishan, Sundar Vishwanathan#### Towards ACC Lower Bounds using Torus Polynomials

__
TR24-073
| 11th April 2024
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Trading Determinism for Noncommutativity in Edmonds' Problem

__
TR24-072
| 11th April 2024
__

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch#### Tropical proof systems

__
TR24-071
| 10th April 2024
__

Yahel Manor, Or Meir#### Lifting with Inner Functions of Polynomial Discrepancy

__
TR24-070
| 10th April 2024
__

Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing

__
TR24-069
| 8th April 2024
__

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch#### Character sums over AG codes

__
TR24-068
| 10th April 2024
__

Pravesh Kothari, Peter Manohar#### Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

__
TR24-067
| 10th April 2024
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Breaking Square-Root Loss Barriers via Min-Entropy

__
TR24-066
| 29th March 2024
__

Siu On Chan, Hiu Tsun Ng, Sijin Peng#### How Random CSPs Fool Hierarchies

__
TR24-065
| 6th April 2024
__

Meghal Gupta, Mihir Singhal, Hongxun Wu#### Optimal quantile estimation: beyond the comparison model

__
TR24-064
| 1st April 2024
__

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami#### No Complete Problem for Constant-Cost Randomized Communication

__
TR24-063
| 6th April 2024
__

Shuichi Hirahara, Mikito Nanashima#### One-Way Functions and Zero Knowledge

__
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

__
TR24-061
| 5th April 2024
__

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi#### Improved Lower Bounds for 3-Query Matching Vector Codes

__
TR24-060
| 4th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### Reverse Mathematics of Complexity Lower Bounds

__
TR24-059
| 4th April 2024
__

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

__
TR24-058
| 29th March 2024
__

Shuichi Hirahara, Nobutaka Shimizu#### Planted Clique Conjectures Are Equivalent

__
TR24-057
| 28th March 2024
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Computing a Fixed Point of Contraction Maps in Polynomial Queries

__
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

__
TR24-055
| 12th March 2024
__

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass#### Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement

__
TR24-054
| 13th March 2024
__

Karthik Gajulapalli, Alexander Golovnev, Samuel King#### On the Power of Adaptivity for Function Inversion

__
TR24-053
| 10th March 2024
__

Noam Mazor, Rafael Pass#### Gap MCSP is not (Levin) NP-complete in Obfustopia

__
TR24-052
| 15th March 2024
__

Justin Yirka#### Even quantum advice is unlikely to solve PP

__
TR24-051
| 5th March 2024
__

Yanyi Liu, Rafael Pass#### A Direct PRF Construction from Kolmogorov Complexity

__
TR24-050
| 5th March 2024
__

Omri Shmueli#### Quantum Algorithms in a Superposition of Spacetimes

Revisions: 1

__
TR24-049
| 7th March 2024
__

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich#### Oblivious Classes Revisited: Lower Bounds and Hierarchies

__
TR24-048
| 4th March 2024
__

Kuan Cheng, Yichuan Wang#### $BPL\subseteq L-AC^1$

__
TR24-047
| 8th March 2024
__

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

Revisions: 1

__
TR24-046
| 6th March 2024
__

Sasank Mouli#### Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable

__
TR24-045
| 6th March 2024
__

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria#### Redundancy for MaxSAT

__
TR24-044
| 28th February 2024
__

Rohit Gurjar, Taihei Oki, Roshan Raj#### Fractional Linear Matroid Matching is in quasi-NC

__
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

__
TR24-042
| 22nd February 2024
__

Lisa Jaser, Jacobo Toran#### Pebble Games and Algebraic Proof Systems Meet Again

Comments: 1

__
TR24-041
| 1st March 2024
__

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich#### Launching Identity Testing into (Bounded) Space

__
TR24-040
| 29th February 2024
__

Kuan Cheng, Ruiyang Wu#### Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

__
TR24-039
| 20th February 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

__
TR24-038
| 27th February 2024
__

Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann#### Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

__
TR24-037
| 26th February 2024
__

Yaroslav Alekseev, Yuval Filmus, Alexander Smal#### Lifting dichotomies

Revisions: 1

__
TR24-036
| 21st February 2024
__

Tal Yankovitz#### A stronger bound for linear 3-LCC

Revisions: 2

__
TR24-035
| 20th February 2024
__

Sreejata Bhattacharya#### Aaronson-Ambainis Conjecture Is True For Random Restrictions

Revisions: 1

__
TR24-034
| 19th February 2024
__

Bruno Loff, Alexey Milovanov#### The hardness of decision tree complexity

__
TR24-033
| 24th February 2024
__

Sam Buss, Emre Yolcu#### Regular resolution effectively simulates resolution

__
TR24-032
| 22nd February 2024
__

Joshua Cook, Dana Moshkovitz#### Explicit Time and Space Efficient Encoders Exist Only With Random Access

__
TR24-031
| 22nd February 2024
__

Daniel Kane, Anthony Ostuni, Kewen Wu#### Locality Bounds for Sampling Hamming Slices

Revisions: 1

__
TR24-030
| 22nd February 2024
__

Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann#### Proof Complexity of Propositional Model Counting

__
TR24-029
| 16th February 2024
__

Noel Arteche, Gaia Carenini, Matthew Gray#### Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

__
TR24-028
| 19th February 2024
__

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk#### Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

__
TR24-027
| 18th February 2024
__

Dor Minzer, Kai Zhe Zheng#### Near Optimal Alphabet-Soundness Tradeoff PCPs

__
TR24-026
| 15th February 2024
__

Pavel Hrubes#### A subquadratic upper bound on sum-of-squares compostion formulas

__
TR24-025
| 13th February 2024
__

Mason DiCicco, Vladimir Podolskii, Daniel Reichman#### Nearest Neighbor Complexity and Boolean Circuits

__
TR24-024
| 14th February 2024
__

Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan#### Strong Batching for Non-Interactive Statistical Zero-Knowledge

__
TR24-023
| 21st January 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

__
TR24-022
| 6th February 2024
__

Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak#### Exponential Separation Between Powers of Regular and General Resolution Over Parities

Revisions: 1

__
TR24-021
| 29th January 2024
__

Prasad Chaugule, Nutan Limaye#### On the closures of monotone algebraic classes and variants of the determinant

__
TR24-020
| 2nd February 2024
__

Mitali Bafna, Noam Lifshitz, Dor Minzer#### Constant Degree Direct Product Testers with Small Soundness

Revisions: 1

__
TR24-019
| 2nd February 2024
__

Yotam Dikstein, Irit Dinur, Alexander Lubotzky#### Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Revisions: 1

__
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

__
TR24-017
| 23rd January 2024
__

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun#### On Pigeonhole Principles and Ramsey in TFNP

__
TR24-016
| 27th January 2024
__

Swagato Sanyal#### Randomized query composition and product distributions

__
TR24-015
| 9th January 2024
__

Harpreet Bedi#### Degree 2 lower bound for Permanent in arbitrary characteristic

__
TR24-014
| 28th January 2024
__

Elette Boyle, Ilan Komargodski, Neekon Vafa#### Memory Checking Requires Logarithmic Overhead

__
TR24-013
| 26th January 2024
__

Oded Goldreich#### On locally-characterized expander graphs (a survey)

Revisions: 1

__
TR24-012
| 26th January 2024
__

Hamed Hatami, Pooya Hatami#### Structure in Communication Complexity and Constant-Cost Complexity Classes

__
TR24-011
| 24th January 2024
__

Paul Beame, Niels Kornerup#### Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

__
TR24-010
| 19th January 2024
__

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere#### Black-Box PPP is not Turing-Closed

__
TR24-009
| 20th January 2024
__

Dmytro Gavinsky#### Unambiguous parity-query complexity

Comments: 1

__
TR24-008
| 17th January 2024
__

Pavel Hrubes#### Hard submatrices for non-negative rank and communication complexity }

__
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

__
TR24-006
| 14th January 2024
__

Sabee Grewal, Justin Yirka#### The Entangled Quantum Polynomial Hierarchy Collapses

__
TR24-005
| 4th January 2024
__

Daniel Noble, Brett Hemenway, Rafail Ostrovsky#### MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Revisions: 1

__
TR24-004
| 7th January 2024
__

Omkar Baraskar, Agrim Dewan, Chandan Saha#### Testing equivalence to design polynomials

__
TR24-003
| 2nd January 2024
__

Noam Mazor, Rafael Pass#### Search-to-Decision Reductions for Kolmogorov Complexity

__
TR24-002
| 4th December 2023
__

Takashi Ishizuka#### PLS is contained in PLC

Revisions: 1

__
TR24-001
| 2nd January 2024
__

Sam Buss, Neil Thapen#### A Simple Supercritical Tradeoff between Size and Height in Resolution

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

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

Vaibhav Krishan, Sundar Vishwanathan

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

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

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

Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch

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

Yahel Manor, Or Meir

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

Xinyu Mao, Guangxu Yang, Jiapeng Zhang

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

Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch

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

Pravesh Kothari, Peter Manohar

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

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

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

Siu On Chan, Hiu Tsun Ng, Sijin Peng

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

Meghal Gupta, Mihir Singhal, Hongxun Wu

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

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

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

Shuichi Hirahara, Mikito Nanashima

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

Omar Alrabiah, Venkatesan Guruswami

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

Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi

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

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

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

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

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

Shuichi Hirahara, Nobutaka Shimizu

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

Xi Chen, Yuhao Li, Mihalis Yannakakis

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 >>>Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

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

Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass

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

Karthik Gajulapalli, Alexander Golovnev, Samuel King

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

Noam Mazor, Rafael Pass

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

Justin Yirka

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

Yanyi Liu, Rafael Pass

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

Omri Shmueli

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

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

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

Kuan Cheng, Yichuan Wang

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

Oded Goldreich

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

Sasank Mouli

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

Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

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

Rohit Gurjar, Taihei Oki, Roshan Raj

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

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

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

Lisa Jaser, Jacobo Toran

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

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

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

Kuan Cheng, Ruiyang Wu

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

Shuichi Hirahara, Naoto Ohsaka

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

Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann

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

Yaroslav Alekseev, Yuval Filmus, Alexander Smal

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

Tal Yankovitz

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

Sreejata Bhattacharya

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

Bruno Loff, Alexey Milovanov

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

Sam Buss, Emre Yolcu

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

Joshua Cook, Dana Moshkovitz

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

Daniel Kane, Anthony Ostuni, Kewen Wu

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

Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann

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

Noel Arteche, Gaia Carenini, Matthew Gray

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

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

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

Dor Minzer, Kai Zhe Zheng

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

Pavel Hrubes

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.

Mason DiCicco, Vladimir Podolskii, Daniel Reichman

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

Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan

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

Shuichi Hirahara, Naoto Ohsaka

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

Sreejata Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak

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

Prasad Chaugule, Nutan Limaye

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

Mitali Bafna, Noam Lifshitz, Dor Minzer

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

Yotam Dikstein, Irit Dinur, Alexander Lubotzky

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

Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz

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

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

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

Swagato Sanyal

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

Harpreet Bedi

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 >>>Elette Boyle, Ilan Komargodski, Neekon Vafa

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

Oded Goldreich

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

Hamed Hatami, Pooya Hatami

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

Paul Beame, Niels Kornerup

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

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

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

Dmytro Gavinsky

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

Pavel Hrubes

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

Karthik C. S., Pasin Manurangsi

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

Sabee Grewal, Justin Yirka

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

Daniel Noble, Brett Hemenway, Rafail Ostrovsky

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

Omkar Baraskar, Agrim Dewan, Chandan Saha

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

Noam Mazor, Rafael Pass

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

Takashi Ishizuka

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

Sam Buss, Neil Thapen

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