Korten and Pitassi (FOCS, 2024) defined a new complexity class L₂^P as the polynomial-time Turing closure of the Linear Ordering Principle (a total function extending finding the minimum of an order [M. Chiari and J. Krajíček, 1998] to the case where the order is not linear). They put it between MA (Merlin-Arthur protocols) and S₂^P (the second symmetric level of the polynomial hierarchy). In this paper we sandwich L₂^P between P^prMA and P^prSBP. (The oracles here are promise problems, and SBP is the only known class between MA and AM.) The containment in P^prSBP is proved via an iterative process that uses a prSBP oracle to estimate the average order rank of a subset and find the minimum of a linear order. Another containment result of this paper is P^prO₂^P ⊆ O₂^P (where O₂^P is the input-oblivious version of S₂^P). These containment results altogether have several byproducts: - We give an affirmative answer to an open question posed by Chakaravarthy and Roy (Computational Complexity, 2011) whether P^prMA ⊆ S₂^P, thereby settling the relative standing of the existing (non-oblivious) Karp–Lipton–style collapse results of [V. T. Chakaravarthy and S. Roy, 2011] and [J.-Y. Cai, 2007], - We give an affirmative answer to an open question of Korten and Pitassi whether a Karp-Lipton-style collapse can be proven for L₂^P, - We show that the Karp-Lipton-style collapse to P^prOMA is actually better than both known collapses to P^prMA due to Chakaravarthy and Roy (Computational Complexity, 2011) and to O₂^P also due to Chakaravarthy and Roy (STACS, 2006). Thus we resolve the controversy between previously incomparable Karp-Lipton collapses stemming from these two lines of research.

Abstract. We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence lemma which states the following. If the polynomials [Formula: see text] over [Formula: see text] are [Formula: see text]-linearly independent then there exists a subset [Formula: see text] of size at most [Formula: see text] such that [Formula: see text] are also [Formula: see text]-linearly independent. We show how to effectively combine this lemma with the use of the alternant matrix to analyze linear independence of polynomials. We also give applications of our technique to the questions of polynomial identity testing and arithmetic circuit reconstruction. (1) We give a general technique for lifting efficient polynomial identity testing algorithms from basic classes of circuits, satisfying some closure properties, to more general classes of circuits. As one of the corollaries of this result, we obtain the first algorithm for polynomial identity testing for depth-4, constant-occur circuits that works over all fields. This strengthens a result by M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena [ SIAM J. Comput., 45 (2016), pp. 1533–1562] that works in the case when the characteristic is 0 or sufficiently large. Another corollary is an identity testing algorithm for a special case of depth-5 circuits. To the best of our knowledge, this is the first algorithm for this class of circuits. (2) We give new and efficient black-box reconstruction algorithms for the class of set-multilinear depth-3 circuits of constant top fan-in, where the set-multilinear variable partition is unknown. This generalizes the results of V. Bhargava, S. Saraf, and I. Volkovich [STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, pp. 809–822] and S. Peleg, A. Shpilka, and B. Volk [15th Innovations in Theoretical Computer Science Conference, ITCS 2024, pp. 87:1–87:20] which work in the case of known variable partition, and correspond to tensor decomposition of constant-rank tensors.

We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown.

We propose a new, simple characterization of the output of the Factor Refinement Algorithm, formally introduced and analyzed in [3]. Our characterization relies only on basic linear algebra. As applications, we obtain a non-adaptive algorithm that computes the square-free part of an integer, given oracle access to Euler’s Totient function, and identify a class of multiplicative functions which is polynomial-time equivalent to computing radicals.

We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a Small Witness for Linear Independence (SWLI) lemma which states the following. If the polynomials f1,f2, …, fk ∈ F[X] over X={x1, …, xn} are F-linearly independent then there exists a subset S ⊆ X of size at most k−1 such that f1,f2, …, fk are also F(X∖ S)-linearly independent.

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2. Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recent results of Ren and Santhanam (CCC 2021), we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.

In this work we devise the first efficient deterministic algorithm for approximating ω(N) - the number of prime factors of an integer N ∈ ℕ, given in addition oracle access to Euler’s Totient function Φ(⋅). We also show that the algorithm can be extended to handle a more general class of additive functions that "depend solely on the exponents in the prime factorization of an integer". In particular, our result gives the first algorithm that approximates ω(N) without necessarily factoring N. Indeed, all the previously known algorithms for computing or even approximating ω(N) entail factorization of N, and therefore are either randomized [M. O. Rabin, 1980; D. L. Long, 1981] or require the Generalized Riemann Hypothesis (GRH) [G. L. Miller, 1976]. Our approach combines an application of Coppersmith’s method for finding non-trivial factors of integers whose prime factors satisfy certain "relative size" conditions of [F. Morain et al., 2018], together with a new upper bound on Φ(N) in terms of ω(N) which could be of independent interest.

We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’).

We present a deterministic algorithm for reconstructing multilinear ƩпƩп(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. For any fixed k, given black-box access to a polynomial f ϵ 픽[x1, x2, …, xn] computable by a multilinear ƩпƩп(k) circuit of size s, the algorithm runs in time quasi-poly(n, s, |픽|) and outputs a multilinear ƩпƩп(k) circuit of size quasi-poly(n, s) that computes f. Our result solves an open problem posed in [15] (STOC, 2012). Indeed, prior to our work, efficient reconstruction algorithms for multilinear ƩпƩп(k) circuits were known only for the case of k = 2 [15, 52].

In this article, we study the problem of deterministic factorization of sparse polynomials. We show that if f ∈ F[ x 1 , x 2 ,… , x n ] is a polynomial with s monomials, with individual degrees of its variables bounded by d , then f can be deterministically factored in time s poly( d )log n . Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d =1 and d =2, only exponential time-deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show that if f is an s -sparse polynomial in n variables, with individual degrees of its variables bounded by d , then the sparsity of each factor of f is bounded by s (9 d 2 log n ) . This is the first non-trivial bound on factor sparsity for d > 2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Carathéodory’s Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen [1985] who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.

A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^{MCSP} !subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^{NP} !subseteq P/poly. We also show that, assuming the existence of Indistinguishability Obfuscators (IO), SAT and MCSP are equivalent in the sense that one has a ZPP algorithm if and only the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions.

In arithmetic circuit complexity the standard operations are +,x. Yet, in some scenarios exponentiation gates are considered as well. In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power. Among applications, we show that: * A reconstruction algorithm for a circuit class c can be extended to handle f^e for f in C. * There exists an efficient deterministic algorithm for factoring sparse multiquadratic polynomials. * There is a deterministic algorithm for testing a factorization of sparse polynomials, with constant individual degrees, into sparse irreducible factors. That is, testing if f = g_1 x ... x g_m when f has constant individual degrees and g_i-s are irreducible. * There is a deterministic reconstruction algorithm for multilinear depth-4 circuits with two multiplication gates. * There exists an efficient deterministic algorithm for testing whether two powers of sparse polynomials are equal. That is, f^d = g^e when f and g are sparse.

In this paper we study the identity testing problem of arithmetic read-once formulas (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the operations are {+,x} and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for read-once formulas, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of [Shpilka-Volkovich, 2015]

An \empharithmetic circuit is a directed acyclic graph in which the operations are {+,\times}. In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems. In particular, we show that: \beginitemize \item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds. \item General circuits and formulas can be learned efficiently with membership and equivalence queries iff they can be learned efficiently with membership queries only. \item Low-query learning algorithms for certain classes of circuits imply explicit rigid matrices. \item Learning algorithms for multilinear depth-3 and depth-4 circuits must compute square roots. \enditemize

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors and sums of univariate polynomials. Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in [von zur Gathen/Kaltofen, J. Comp. Sys. Sci., 1985] to devise an efficient deterministic algorithm for factoring (general) sparse polynomials. We achieve our goal by introducing essential factorization schemes which can be thought of as a relaxation of the regular factorization notion.

An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are $${\left\{+, \times \right\}}$$ and such that every input variable labels at most one leaf. A preprocessed ROF (PROF for short) is a ROF in which we are allowed to replace each variable x i with a univariate polynomial T i (x i ). In this paper, we study the problems of designing deterministic identity testing algorithms for models related to preprocessed ROFs. Our main result gives PIT algorithms for the sum of k preprocessed ROFs, of individual degrees at most d (i.e., each T i (x i ) is of degree at most d), that run in time $${(nd)^{\mathcal{O}(k)}}$$ in the white-box setting and in time $${(nd)^{\mathcal{O}(k + \log n)}}$$ in the black-box setting. We also obtain better algorithms when the formulas have a small depth that lead to an improvement in the best PIT algorithm for multilinear depth-3 $${\Sigma\Pi\Sigma(k)}$$ circuits. Our main technique is to prove a hardness of representation result, namely a theorem showing a relatively mild lower bound on the sum of k PROFs. We then use this lower bound in order to design our PIT algorithm.

We give the first subexponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 multilinear circuits with a plus gate at the top (also known as $\Sigma\Pi\Sigma\Pi$ circuits) and has a running time of $\exp(\mathrm{poly}(\log(n),\log(s),k))$ where $n$ is the number of variables, $s$ is the size of the circuit, and $k$ is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. Prior to this work, sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-$4$ circuits. The main ingredient in our proof is a new structural theorem for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits. Roughly, this theorem shows that any nonzero multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit contains an “embedded” nonzero multilinear $\Sigma\Pi\Sigma(k)$ circuit. Using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits.

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Before our work no subexponential-time deterministic algorithm was known for this class of formulae. We also present a deterministic algorithm that works in a blackbox fashion and runs in quasi-polynomial time in general, and polynomial time for constant depth. Finally, we extend our results and allow the inputs to be replaced with sparse polynomials. Our results encompass recent deterministic identity tests for sums of a constant number of read-once formulae, and for multilinear depth-four circuits.

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ΣΠΣΠ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. In [AV08], it was shown that derandomizing polynomial identity testing for general ΣΠΣΠ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. Prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits.