In this paper, we rule out a natural programme for proving VF ≠ VNP via set-multilinear formula lower bounds. The programme combines two ingredients present in the literature: the n^Ω(log n) set-multilinear formula lower bound of Kush and Saraf (CCC 2022) for any full-rank polynomial, and an IMM-style self-reducibility that propagates such a bound to small degree, where Raz’s set-multilinearisation (J. ACM 2013) converts it to a general formula lower bound. Each ingredient has been realised separately, yet no polynomial family is known to combine them. We prove that no such family can exist: under any polynomial-width IMM-style self-reducibility - i.e., a small-width expression g = ∑_{k=1}^w L_k ⋅ R_k with each summand factoring across a balanced split - full-rankness forces width n^Ω(d), and even approximate full-rankness across a near-balanced split forces width n^Ω(√d). This rules out the full-rank/self-reducible route to VF ≠ VNP.

The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a major challenge to understand the precise connections between PIT and lower bounds. In particular, a main goal has been to understand which lower bounds suffice to obtain efficient PIT algorithms, and how close are they to lower bounds that are necessary for the conclusion. We construct polynomial-time PIT algorithms from lower bounds that are, up to relatively minor remaining gaps, necessary for the existence of such algorithms. That is, we prove that these lower bounds are, up to the mentioned minor gaps, both sufficient and necessary for polynomial-time PIT, over fields of characteristic zero. Over sufficiently large finite fields, we show a similar result wherein the PIT algorithm runs in time $n^{\log^{(c)}(n)}$, i.e. a power of $c$-iterated log for an arbitrarily large constant $c>1$. The key to these improvements is studying PIT versus lower bounds in the uniform setting, in which we focus on proving lower bounds for uniform arithmetic circuits and their variants (and on deducing algorithms from such lower bounds). Indeed, by working in this setting we obtain results that are significantly tighter than previously known results concerning polynomial-time PIT vs lower bounds, and are in fact also tighter than known hardness-vs-randomness connections in the Boolean setting. Our results are obtained by combining recent techniques from Boolean hardness vs randomness, and in particular the generator of Chen and Tell (FOCS 2021), with the algebraic hitting-set generator of Guo, Kumar, Saptharishi, and Solomon (SIAM J. Computing 2022) along with the bootstrapping ideas of Agrawal, Ghosh, and Saxena (STOC 2018) and of Kumar, Saptharishi, and Tengse (SODA 2019).

Abstract. For a fixed “pattern” graph [Formula: see text], the colored [Formula: see text]- subgraph isomorphism problem (denoted by [Formula: see text]) asks, given an [Formula: see text]-vertex graph [Formula: see text] and a coloring [Formula: see text], whether [Formula: see text] contains a properly colored copy of [Formula: see text]. The complexity of this problem is tied to parameterized versions of [Formula: see text] and [Formula: see text], among other questions. An overarching goal is to understand the complexity of [Formula: see text], under different computational models, in terms of natural invariants of the pattern graph [Formula: see text]. In this paper, we establish a close relationship between the formula complexity of [Formula: see text] and an invariant known as tree-depth (denoted by[Formula: see text]). [Formula: see text] is known to be solvable by monotone [Formula: see text] formulas of size [Formula: see text]. Our main result is an [Formula: see text] lower bound for formulas that are monotone or have sublogarithmic depth. This complements a lower bound of Li, Razborov, and Rossman [ SIAM J. Comput., 46 (2017), pp. 936–971] relating tree-width and [Formula: see text] circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures [B. Rossman, An improved homomorphism preservation theorem from lower bounds in circuit complexity, in 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 27]. The technical core of this result is an [Formula: see text] lower bound in the special case where [Formula: see text] is a complete binary tree of height [Formula: see text], which we establish using the pathset framework introduced in B. Rossman [ SIAM J. Comput., 47 (2018), pp. 1986–2028]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [W. Czerwiński, W. Nadara, and M. Pilipczuk, SIAM J. Discrete Math., 35 (2021), pp. 934–947; K. Kawarabayashi and B. Rossman, A polynomial excluded-minor approximation of treedepth, in Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, 2018, pp. 234–246]. Additional results of this paper extend the pathset framework and improve upon both the best known upper and lower bounds on the average-case formula size of [Formula: see text] when [Formula: see text] is a path.

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial f in VNP defined over n² variables, and of degree n, such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). The hard polynomial f comes from the class of Nisan-Wigderson (NW) design-based polynomials. Our lower bounds improve upon the recent work of Limaye, Srinivasan and Tavenas (STOC 2022), where a lower bound of the form (log n)^Ω(Δ n^{1/Δ}) was shown for the size of product-depth Δ set-multilinear formulas computing the iterated matrix multiplication (IMM) polynomial of the same degree and over the same number of variables as f. Moreover, our lower bounds are novel for any Δ ≥ 2. The precise quantitative expression in our lower bound is interesting also because the lower bounds we obtain are "sharp" in the sense that any asymptotic improvement would imply general set-multilinear circuit lower bounds via depth reduction results. In the setting of general set-multilinear formulas, a lower bound of the form n^Ω(log n) was already obtained by Raz (J. ACM 2009) for the more general model of multilinear formulas. The techniques of LST (which extend the techniques of the same authors in (FOCS 2021)) give a different route to set-multilinear formula lower bounds, and allow them to obtain a lower bound of the form (log n)^Ω(log n) for the size of general set-multilinear formulas computing the IMM polynomial. Our proof techniques are another variation on those of LST, and enable us to show an improved lower bound (matching that of Raz) of the form n^Ω(log n), albeit for the same polynomial f in VNP (the NW polynomial). As observed by LST, if the same n^Ω(log n) size lower bounds for unbounded-depth set-multilinear formulas could be obtained for the IMM polynomial, then using the self-reducibility of IMM and using hardness escalation results, this would imply super-polynomial lower bounds for general algebraic formulas.

A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide class of distance metrics, including all norms. In particular, these data structures achieve approximation on the order of p for 𝓁_p^d norms with space complexity nearly linear in the dataset size n and polynomial in the dimension d, and query time sub-linear in n and polynomial in d. The main shortcoming is the exponential in d pre-processing time required for their construction. In this paper, we describe a more direct framework for constructing NNS data structures for general norms. More specifically, we show via an algorithmic reduction that an efficient NNS data structure for a metric ℳ is implied by an efficient average distortion embedding of ℳ into 𝓁₁ or the Euclidean space. In particular, the resulting data structures require only polynomial pre-processing time, as long as the embedding can be computed in polynomial time. As a concrete instantiation of this framework, we give an NNS data structure for 𝓁_p with efficient pre-processing that matches the approximation factor, space and query complexity of the aforementioned data structure of Andoni et al. On the way, we resolve a question of Naor (Analysis and Geometry in Metric Spaces, 2014) and provide an explicit, efficiently computable embedding of 𝓁_p, for p ≥ 1, into 𝓁₁ with average distortion on the order of p. Furthermore, we also give data structures for Schatten-p spaces with improved space and query complexity, albeit still requiring exponential pre-processing when p ≥ 2. We expect our approach to pave the way for constructing efficient NNS data structures for all norms.

For a fixed “pattern” graph G, the colored G-subgraph isomorphism problem (denoted SUB(G)) asks, given an n-vertex graph H and a coloring V(H)→ V(G), whether H contains a properly colored copy of G. The complexity of this problem is tied to parameterized versions of P=? NP and L=? NL, among other questions. An overarching goal is to understand the complexity of SUB(G), under different computational models, in terms of natural invariants of the pattern graph G. In this paper, we establish a close relationship between the formula complexity of SUB(G) and an invariant known as tree-depth (denoted td ( G)). SUB(G) is known to be solvable by monotone AC0formulas of size O(ntd(G)). Our main result is an n~Ω(td(G)1/3) lower bound for formulas that are monotone or have sub-logarithmic depth. This complements a lower bound of Li, Razborov and Rossman [8] relating tree-width and AC° circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures [14]. The technical core of this result is an nΩ(k)lower bound in the special case where G is a complete binary tree of height k, which we establish using the pathset framework introduced in [15]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [4], [6].) Additional results of this paper extend the pathset framework and improve upon both, the best known upper and lower bounds on the average-case formula size of SUB(G) when G is a path.

Proving super-polynomial size lower bounds for $\textsf{TC}^0$, the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity theory. A major frontier is to prove that $\textsf{NEXP}$ does not have poly-size $\textsf{THR} \circ \textsf{THR}$ circuit (depth-two circuits with linear threshold gates). In recent years, R.~Williams proposed a program to prove circuit lower bounds via improved algorithms. In this paper, following Williams' framework, we show that the above frontier question can be resolved by devising slightly faster algorithms for several fundamental problems: 1. Shaving Logs for $\textsf{$\ell_2$-Furthest-Pair}$. An $n^2 \textrm{poly}(d) / \log^{ω(1)} n$ time algorithm for $\textsf{$\ell_2$-Furthest-Pair}$ in $\mathbb{R}^d$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. The same holds for Hopcroft's problem, $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ and Integer $\textsf{Max-IP}$. 2. Shaving Logs for Approximate $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$. An $n^2 \textrm(d) / \log^{ω(1)} n$ time algorithm for $(1+1/\log^{ω(1)} n)$-approximation to $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ or $\textsf{Bichrom.-$\ell_1$-Closest-Pair}$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{SYM}\circ\textsf{THR}$ circuits. 3. Shaving Logs for Modest Dimension Boolean $\textsf{Max-IP}$. An $n^2 / \log^{ω(1)} n$ time algorithm for Bichromatic Maximum Inner Product with vector dimension $d = n^ε$ for any small constant $ε$ would imply $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. Note there is an $n^2\textrm{polylog}(n)$ time algorithm via fast rectangle matrix multiplication. Our results build on two structure lemmas for threshold circuits.