All reports in year 2023:

__
TR23-082
| 1st June 2023
__

Ryan Williams#### Self-Improvement for Circuit-Analysis Problems

__
TR23-081
| 1st June 2023
__

Noga Amit, Guy Rothblum#### Constant-Round Arguments from One-Way Functions

__
TR23-080
| 1st June 2023
__

Halley Goldberg, Valentine Kabanets#### Improved Learning from Kolmogorov Complexity

__
TR23-079
| 31st May 2023
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

__
TR23-078
| 30th May 2023
__

Or Meir#### Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

__
TR23-077
| 25th May 2023
__

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan#### Batch Proofs are Statistically Hiding

__
TR23-076
| 24th May 2023
__

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam#### Polynomial-Time Pseudodeterministic Construction of Primes

__
TR23-075
| 17th May 2023
__

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj#### Border Complexity of Symbolic Determinant under Rank One Restriction

__
TR23-074
| 14th May 2023
__

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta#### Radical Sylvester-Gallai Theorem for Tuples of Quadratics

__
TR23-073
| 15th May 2023
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Reducing Tarski to Unique Tarski (in the Black-box Model)

__
TR23-072
| 18th May 2023
__

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren#### Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms

__
TR23-071
| 8th May 2023
__

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov#### Sampling and Certifying Symmetric Functions

__
TR23-070
| 9th May 2023
__

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren#### Bounded Relativization

__
TR23-069
| 11th May 2023
__

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira#### Constant-depth circuits vs. monotone circuits

__
TR23-068
| 10th May 2023
__

Ben Davis, Robert Robere#### Colourful TFNP and Propositional Proofs

__
TR23-067
| 7th May 2023
__

Guy Goldberg#### Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

__
TR23-066
| 4th May 2023
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Protecting Single-Hop Radio Networks from Message Drops

__
TR23-065
| 4th May 2023
__

Louis Golowich#### From Grassmannian to Simplicial High-Dimensional Expanders

__
TR23-064
| 3rd May 2023
__

Oded Goldreich#### On the Lower Bound on the Length of Relaxed Locally Decodable Codes

__
TR23-063
| 2nd May 2023
__

Jacobo Toran, Florian Wörz#### Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

__
TR23-062
| 2nd May 2023
__

Benny Applebaum, Eliran Kachlon#### Conflict Checkable and Decodable Codes and Their Applications

__
TR23-061
| 2nd May 2023
__

Abhimanyu Choudhury, Meena Mahajan#### Dependency schemes in CDCL-based QBF solving: a proof-theoretic study

__
TR23-060
| 17th April 2023
__

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan#### The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography

__
TR23-058
| 23rd April 2023
__

Xin Li, Yan Zhong#### Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

__
TR23-057
| 27th April 2023
__

Iddo Tzameret, Luming Zhang#### Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness

__
TR23-056
| 26th April 2023
__

Geoffrey Mon, Dana Moshkovitz, Justin Oh#### Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

__
TR23-055
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: II

__
TR23-054
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: III

__
TR23-053
| 19th April 2023
__

Leroy Chew#### Proof Simulation via Round-based Strategy Extraction for QBF

__
TR23-052
| 19th April 2023
__

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals#### Limits of CDCL Learning via Merge Resolution

__
TR23-051
| 18th April 2023
__

Benjamin Böhm, Olaf Beyersdorff#### QCDCL vs QBF Resolution: Further Insights

__
TR23-050
| 18th April 2023
__

Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen#### Communication complexity of half-plane membership

__
TR23-049
| 17th April 2023
__

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov#### Top-Down Lower Bounds for Depth-Four Circuits

__
TR23-048
| 4th April 2023
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

__
TR23-047
| 2nd April 2023
__

Hunter Monroe#### Ruling Out Short Proofs of Unprovable Sentences is Hard

__
TR23-046
| 13th April 2023
__

Yizhi Huang, Rahul Ilango, Hanlin Ren#### NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

__
TR23-045
| 13th April 2023
__

Vinayak Kumar#### Tight Correlation Bounds for Circuits Between AC0 and TC0

Revisions: 1

__
TR23-044
| 28th March 2023
__

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar#### Separations between Combinatorial Measures for Transitive Functions

__
TR23-043
| 9th April 2023
__

Yotam Dikstein, Irit Dinur#### Coboundary and cosystolic expansion without dependence on dimension or degree

__
TR23-042
| 3rd April 2023
__

Johan Håstad#### On small-depth Frege proofs for PHP

__
TR23-041
| 1st April 2023
__

Lila Fontes, Sophie Laplante, Mathieu Lauriere, Alexandre Nolin#### The communication complexity of functions with large outputs

__
TR23-040
| 28th March 2023
__

Edward Pyne, Ran Raz, Wei Zhan#### Certified Hardness vs. Randomness for Log-Space

__
TR23-039
| 28th March 2023
__

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan#### Query Complexity of Search Problems

__
TR23-038
| 28th March 2023
__

Rahul Ilango, Jiatu Li, Ryan Williams#### Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

__
TR23-037
| 28th March 2023
__

Shuichi Hirahara#### Capturing One-Way Functions via NP-Hardness of Meta-Complexity

__
TR23-036
| 27th March 2023
__

Dean Doron, Roei Tell#### Derandomization with Minimal Memory Footprint

__
TR23-035
| 22nd March 2023
__

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira#### A Duality Between One-Way Functions and Average-Case Symmetry of Information

__
TR23-034
| 24th March 2023
__

Oded Goldreich#### On teaching the approximation method for circuit lower bounds

Revisions: 1

__
TR23-033
| 24th March 2023
__

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi#### Fast Numerical Multivariate Multipoint Evaluation

Revisions: 1

__
TR23-032
| 24th March 2023
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Linear Independence, Alternants and Applications

__
TR23-031
| 23rd March 2023
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Statistical MPC with Optimal Resiliency

__
TR23-030
| 21st March 2023
__

Jan Krajicek#### A proof complexity conjecture and the Incompleteness theorem

__
TR23-029
| 18th March 2023
__

Nicollas Sdroievski, Dieter van Melkebeek#### Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

__
TR23-028
| 15th March 2023
__

Rahul Santhanam#### An Algorithmic Approach to Uniform Lower Bounds

__
TR23-027
| 8th March 2023
__

Joseph Zalewski#### Some Lower Bounds Related to the Missing String Problem

__
TR23-026
| 15th March 2023
__

Shuichi Hirahara, Nobutaka Shimizu#### Hardness Self-Amplification: Simplified, Optimized, and Unified

__
TR23-025
| 10th March 2023
__

Vikraman Arvind, Pushkar Joglekar#### Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

__
TR23-024
| 9th March 2023
__

Mark Bun, Nadezhda Voronova#### Approximate degree lower bounds for oracle identification problems

Revisions: 1

__
TR23-023
| 13th March 2023
__

Xin Li#### Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

Revisions: 1

__
TR23-022
| 11th March 2023
__

Jiatu Li, Igor Carboni Oliveira#### Unprovability of strong complexity lower bounds in bounded arithmetic

__
TR23-021
| 9th March 2023
__

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi#### Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

__
TR23-020
| 3rd March 2023
__

Scott Aaronson, Shih-Han Hung#### Certified Randomness from Quantum Supremacy

__
TR23-019
| 2nd March 2023
__

Pooya Hatami, William Hoza#### Theory of Unconditional Pseudorandom Generators

Revisions: 2

__
TR23-018
| 1st March 2023
__

Qipeng Liu, Ran Raz, Wei Zhan#### Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

__
TR23-017
| 21st February 2023
__

Deepanshu Kush, Shubhangi Saraf#### Near-Optimal Set-Multilinear Formula Lower Bounds

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

__
TR23-015
| 20th February 2023
__

Scott Aaronson, Harry Buhrman, William Kretschmer#### A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

__
TR23-014
| 16th February 2023
__

Tameem Choudhury, Karteek Sreenivasaiah#### Depth-3 Circuit Lower Bounds for k-OV

__
TR23-013
| 7th February 2023
__

Noam Mazor#### A Lower Bound on the Share Size in Evolving Secret Sharing

Revisions: 1

__
TR23-012
| 16th February 2023
__

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah#### Linear threshold functions in decision lists, decision trees, and depth-2 circuits

__
TR23-011
| 13th February 2023
__

Mikhail Dektiarev, Nikolay Vereshchagin#### Half-duplex communication complexity with adversary? can be less than the classical communication complexity

__
TR23-010
| 13th February 2023
__

Per Austrin, Kilian Risse#### Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

__
TR23-009
| 14th February 2023
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas#### Towards Optimal Depth-Reductions for Algebraic Formulas

__
TR23-008
| 2nd February 2023
__

Ond?ej Ježil#### Limits of structures and Total NP Search Problems

__
TR23-007
| 3rd February 2023
__

Jan Krajicek#### Extended Nullstellensatz proof systems

__
TR23-006
| 20th January 2023
__

Nader Bshouty#### Superpolynomial Lower Bounds for Learning Monotone Classes

Revisions: 1

__
TR23-005
| 13th January 2023
__

Paul Beame, Niels Kornerup#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

__
TR23-004
| 13th January 2023
__

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang#### On linear-algebraic notions of expansion

__
TR23-003
| 11th January 2023
__

Shachar Lovett, Jiapeng Zhang#### Streaming Lower Bounds and Asymmetric Set-Disjointness

__
TR23-002
| 5th January 2023
__

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran#### Diagonalization Games

Revisions: 2

__
TR23-001
| 5th January 2023
__

Prerona Chatterjee, Pavel Hrubes#### New Lower Bounds against Homogeneous Non-Commutative Circuits

Ryan Williams

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, $\#$Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit ... more >>>

Noga Amit, Guy Rothblum

We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.

Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash ...
more >>>

Halley Goldberg, Valentine Kabanets

Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in $\P/\poly$, under the uniform distribution and with membership queries. It is ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ...
more >>>

Or Meir

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq \mathbf{NC}^{1}$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity of a composition of functions $f \diamond g$ is roughly ... more >>>

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs ... more >>>

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta

We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Han65, Shp20]. Hansen's theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen's theorem to the setting of quadratic forms ... more >>>

Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding a Tarski fixed point over the $k$-dimensional grid $[n]^k$. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>

Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

The *range avoidance problem*, denoted as $\mathcal{C}$-$\rm Avoid$, asks to find a non-output of a given $\mathcal{C}$-circuit $C:\{0,1\}^n\to\{0,1\}^\ell$ with stretch $\ell>n$. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... more >>>

Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov

A circuit $\mathcal{C}$ samples a distribution $\mathbf{X}$ with an error $\epsilon$ if the statistical distance between the output of $\mathcal{C}$ on the uniform input and $\mathbf{X}$ is $\epsilon$. We study the hardness of sampling a uniform distribution over the set of $n$-bit strings of Hamming weight $k$ denoted by $\mathbf{U}^n_k$ ... more >>>

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits:

- For every $k \geq 1$, there is a monotone function in ${\rm AC^0}$ (constant-depth poly-size circuits) that requires monotone circuits of depth $\Omega(\log^k n)$. This significantly extends a classical result of Okol'nishnikova (1982) and Ajtai ... more >>>

Ben Davis, Robert Robere

Recent work has shown that many of the standard TFNP classes — such as PLS, PPADS, PPAD, SOPL, and EOPL — have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem ... more >>>

Guy Goldberg

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.

Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.

To prevent the ...
more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

Louis Golowich

In this paper, we present a new construction of simplicial complexes of subpolynomial degree with arbitrarily good local spectral expansion. Previously, the only known high-dimensional expanders (HDXs) with arbitrarily good expansion and less than polynomial degree were based on one of two constructions, namely Ramanujan complexes and coset complexes. ... more >>>

Oded Goldreich

We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error ... more >>>

Jacobo Toran, Florian Wörz

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>

Benny Applebaum, Eliran Kachlon

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the ... more >>>

Abhimanyu Choudhury, Meena Mahajan

We formalize the notion of proof systems obtained by adding normal dependency schemes into the QCDCL proof system underlying algorithms for solving Quantified Boolean Formulas, by exploring the addition of the dependency schemes via two approaches: one as a preprocessing tool, and second in propagation and learnings in the QCDCL ... more >>>

Sagnik Saha, Nikolaj Schwartzbach, Prashant Nalini Vasudevan

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a set of $k$ numbers that sum to $0$ modulo $M$ (this set is called a ``solution''). In the related $k$-XOR problem, given $k$ uniformly random Boolean vectors of length $\log{M}$, ... more >>>

Xin Li, Yan Zhong

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>

Iddo Tzameret, Luming Zhang

We develop the theory of cryptographic nondeterministic-secure pseudorandomness beyond the point reached by Rudich's original work (Rudich 1997), and apply it to draw new consequences in average-case complexity and proof complexity. Specifically, we show the following:

?*Demi-bit stretch*: Super-bits and demi-bits are variants of cryptographic pseudorandom generators which are ... more >>>

Geoffrey Mon, Dana Moshkovitz, Justin Oh

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property ... more >>>

Leroy Chew

The proof complexity of Quantified Boolean Formulas (QBF) relates to both QBF solving and OBF certification. One method to p-simulate a QBF proof system is by formalising the soundness of its strategy extraction in propositional logic. In this work we illustrate how to use extended QBF Frege to simulate LD-Q(Drrs)-Res, ... more >>>

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals

In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simulation, i.e., the question of how large this overhead needs to be. In this paper, ... more >>>

Benjamin Böhm, Olaf Beyersdorff

We continue the investigation on the relations of QCDCL and QBF resolution systems. In particular, we introduce QCDCL versions that tightly characterise QU-Resolution and (a slight variant of) long-distance Q-Resolution. We show that most QCDCL variants - parameterised by different policies for decisions, unit propagations and reductions -- lead to ... more >>>

Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen

We study the randomized communication complexity of the following problem. Alice receives the integer coordinates of a point in the plane, and Bob receives the integer parameters of a half-plane, and their goal is to determine whether Alice's point belongs to Bob's half-plane.

This communication task corresponds to determining ... more >>>

Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.

more >>>Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$. This complexity is independent of $n$, but ... more >>>

Hunter Monroe

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length $t$ proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string $x$ is Kolmogorov random ($x{\in}R$) is ... more >>>

Yizhi Huang, Rahul Ilango, Hanlin Ren

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>

Vinayak Kumar

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ ... more >>>

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.

For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.

A function $f:\{0,1\}^n \to \{0,1\}$ ...
more >>>

Yotam Dikstein, Irit Dinur

We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of $SL_n(F_q)$. The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and ... more >>>

Johan Håstad

We study Frege proofs for the one-to-one graph Pigeon Hole Principle

defined on the $n\times n$ grid where $n$ is odd.

We are interested in the case where each formula

in the proof is a depth $d$ formula in the basis given by

$\land$, $\lor$, and $\neg$. We prove that ...
more >>>

Lila Fontes, Sophie Laplante, Mathieu Lauriere, Alexandre Nolin

We study the two-party communication complexity of functions with large outputs, and show that the communication complexity can greatly vary depending on what output model is considered. We study a variety of output models, ranging from the open model, in which an external observer can compute the outcome, to the ... more >>>

Edward Pyne, Ran Raz, Wei Zhan

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$.

We ...
more >>>

Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at ... more >>>

Rahul Ilango, Jiatu Li, Ryan Williams

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

Shuichi Hirahara

A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way ... more >>>

Dean Doron, Roei Tell

Existing proofs that deduce BPL=L from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the minimal possible space overhead for derandomization.

We show that $BPSPACE[S] \subseteq DSPACE[c \cdot S]$ for $c \approx ...
more >>>

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) ... more >>>

Oded Goldreich

This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).

The textbook presentations of the latter result ...
more >>>

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both \emph{exact} and \emph{approximate} versions of the algorithm. The input to the algorithms are (1) coefficients of an $m$-variate polynomial $f$ with degree $d$ in each ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.

If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists ...
more >>>

Benny Applebaum, Eliran Kachlon, Arpita Patra

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We ... more >>>

Jan Krajicek

Given a sound first-order p-time theory $T$ capable of formalizing syntax of

first-order logic we define a p-time function $g_T$ that stretches all inputs by one

bit and we use its properties to show that $T$ must be incomplete. We leave it as an

open problem whether ...
more >>>

Nicollas Sdroievski, Dieter van Melkebeek

A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the ... more >>>

Rahul Santhanam

We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as ``NP is not in uniform ACC^0" and ``NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our ... more >>>

Joseph Zalewski

We prove that a $O(k \log k)$-probe local algorithm for $k$-Missing String presented by Vyas and Williams is asymptotically optimal among a certain class of algorithms for this problem. The best lower bound we are aware of for the general case is still $\Omega(k)$.

more >>>Shuichi Hirahara, Nobutaka Shimizu

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>

Vikraman Arvind, Pushkar Joglekar

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

Mark Bun, Nadezhda Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function.

We ... more >>>

Xin Li

A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show ... more >>>

Jiatu Li, Igor Carboni Oliveira

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory $\textbf{APC}_1$ (2007) and of higher levels of Buss's hierarchy $\textbf{S}^i_2$ (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory ... more >>>

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $NC^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ ... more >>>

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

Pooya Hatami, William Hoza

This is a survey of unconditional *pseudorandom generators* (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or read-once branching programs), we would like to design a PRG that ... more >>>

Qipeng Liu, Ran Raz, Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

Deepanshu Kush, Shubhangi Saraf

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this paper, we make ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>

Scott Aaronson, Harry Buhrman, William Kretschmer

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

Tameem Choudhury, Karteek Sreenivasaiah

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, ... more >>>

Noam Mazor

Secret sharing schemes allow sharing a secret between a set of parties in a way that ensures that only authorized subsets of the parties learn the secret. Evolving secret sharing schemes (Komargodski, Naor, and Yogev [TCC ’16]) allow achieving this end in a scenario where the parties arrive in an ... more >>>

Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>

Mikhail Dektiarev, Nikolay Vereshchagin

Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been ... more >>>

Per Austrin, Kilian Risse

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). ... more >>>

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result ... more >>>

Ond?ej Ježil

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables [7]. We prove ... more >>>

Jan Krajicek

For a finite set $\cal F$ of polynomials over a fixed finite prime field of size $p$ containing all polynomials $x^2 - x$, a Nullstellensatz proof of the unsolvability of the system

$$

f = 0\ ,\ \mbox{ all } f \in {\cal F}

$$

is a linear combination ...
more >>>

Nader Bshouty

Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time $n^{\tilde O(\log\log s)}$ for the classes of $n$-variable size-$s$ DNF, size-$s$ Decision Tree, and $\log s$-Junta by DNF (that returns a DNF hypothesis). Assuming a natural ... more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

Shachar Lovett, Jiapeng Zhang

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in ... more >>>

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... more >>>

Prerona Chatterjee, Pavel Hrubes

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>>