Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2023:
All reports in year 2023:
TR23-032 | 24th March 2023
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

#### Linear Independence, Alternants and Applications

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

TR23-031 | 23rd March 2023
Benny Applebaum, Eliran Kachlon, Arpita Patra

#### The Round Complexity of Statistical MPC with Optimal Resiliency

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

TR23-030 | 21st March 2023
Jan Krajicek

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

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

TR23-029 | 18th March 2023
Nicollas Sdroievski, Dieter van Melkebeek

#### Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols

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

TR23-028 | 15th March 2023
Rahul Santhanam

#### An Algorithmic Approach to Uniform Lower Bounds

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

TR23-027 | 8th March 2023
Joseph Zalewski

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

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

TR23-026 | 15th March 2023
Shuichi Hirahara, Nobutaka Shimizu

#### Hardness Self-Amplification: Simplified, Optimized, and Unified

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

TR23-025 | 10th March 2023
Vikraman Arvind, Pushkar Joglekar

#### Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

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

TR23-024 | 9th March 2023

#### Approximate degree lower bounds for oracle identification problems

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

TR23-023 | 13th March 2023
Xin Li

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

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

TR23-022 | 11th March 2023
Jiatu Li, Igor Carboni Oliveira

#### Unprovability of strong complexity lower bounds in bounded arithmetic

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

TR23-021 | 9th March 2023
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

#### Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

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

TR23-020 | 3rd March 2023
Scott Aaronson, Shih-Han Hung

#### Certified Randomness from Quantum Supremacy

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

TR23-019 | 2nd March 2023
Pooya Hatami, William Hoza

#### Theory of Unconditional Pseudorandom Generators

Revisions: 1

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

TR23-018 | 1st March 2023
Qipeng Liu, Ran Raz, Wei Zhan

#### Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

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

TR23-017 | 21st February 2023
Deepanshu Kush, Shubhangi Saraf

#### Near-Optimal Set-Multilinear Formula Lower Bounds

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

TR23-016 | 22nd February 2023
Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

#### Proving Unsatisfiability with Hitting Formulas

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

TR23-015 | 20th February 2023
Scott Aaronson, Harry Buhrman, William Kretschmer

#### A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

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

TR23-014 | 16th February 2023
Tameem Choudhury, Karteek Sreenivasaiah

#### Depth-3 Circuit Lower Bounds for k-OV

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

TR23-013 | 7th February 2023
Noam Mazor

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

Revisions: 1

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

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

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

TR23-011 | 13th February 2023
Mikhail Dektiarev, Nikolay Vereshchagin

#### Half-duplex communication complexity with adversary? can be less than the classical communication complexity

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

TR23-010 | 13th February 2023
Per Austrin, Kilian Risse

#### Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem

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

TR23-009 | 14th February 2023
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas

#### Towards Optimal Depth-Reductions for Algebraic Formulas

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

TR23-008 | 2nd February 2023
Ond?ej Ježil

#### Limits of structures and Total NP Search Problems

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

TR23-007 | 3rd February 2023
Jan Krajicek

#### Extended Nullstellensatz proof systems

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

TR23-006 | 20th January 2023

#### Superpolynomial Lower Bounds for Learning Monotone Classes

Revisions: 1

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

TR23-005 | 13th January 2023
Paul Beame, Niels Kornerup

#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

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

TR23-004 | 13th January 2023
Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

#### On linear-algebraic notions of expansion

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

TR23-003 | 11th January 2023
Shachar Lovett, Jiapeng Zhang

#### Streaming Lower Bounds and Asymmetric Set-Disjointness

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

TR23-002 | 5th January 2023
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

#### Diagonalization Games

Revisions: 2

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

TR23-001 | 5th January 2023
Prerona Chatterjee, Pavel Hrubes

#### New Lower Bounds against Homogeneous Non-Commutative Circuits

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

ISSN 1433-8092 | Imprint