The \emph{sum-of-squares (SoS) complexity} of a $d$-multiquadratic polynomial $f$ (quadratic in each of $d$ blocks of $n$ variables) is the minimum $s$ such that $f = \sum_{i=1}^s g_i^2$ with each $g_i$ $d$-multilinear. In the case $d=2$, Hrubeš, Wigderson and Yehudayoff (2011) showed that an $n^{1+Ω(1)}$ lower bound on the SoS complexity of explicit biquadratic polynomials implies an exponential lower bound for non-commutative arithmetic circuits. In this paper, we establish an analogous connection between general \emph{multiquadratic sum-of-squares} and \emph{commutative arithmetic formulas}. Specifically, we show that an $n^{d-o(\log d)}$ lower bound on the SoS complexity of explicit $d$-multiquadratic polynomials, for any $d = d(n)$ with $ω(1) \le d(n) \le O(\frac{\log n}{\log\log n})$, would separate the algebraic complexity classes VNC$^1$ and VNP.

Motivated by an application in Algebraic Circuit Complexity, we introduce a complexity measure on even-order tensors called rife rank. The riffle rank of a tensor f : [n] 2k → F, denoted R riffle ( f ), is the minimum m ≥ 0 such that f admits a sum-product decomposition of the form f(a 1 ,b 1 ,…a k ,b k ) = ∑ ℓ=1 m A ℓ,1 (a 1 )⋅A ℓ,2 (b 1 ,a 2 )⋅…⋅A ℓ,k (b 1 ,…,b k−1 ,a k )⋅B ℓ (b 1 ,…,b k ) where A ℓ,i : [ n ] i → F and B ℓ : [ n ] k → F. Riffle rank is at most n k for all f and at least (1/2 − o(1))n k for almost all f . We advance a conjecture that the k-fold identity tensor , I n ⊗k (a 1 ,b 1 ,…,a k ,b k ) = {1 if (a 1 ,…,a k ) = (b 1 ,…,b k ), 0 otherwise, has (nearly if not exactly) the maximum possible riffle rank n k . As a rationale for studying this conjecture, we show that an n k - o (lo g k ) lower bound on R riffle (I n ⊗k ) would imply an n Ω(log k) lower bound on the arithmetic formula size of the Iterated Matrix Multiplication polynomial IMM n , k and thus separate complexity classes VNC 1 and VBP.

Iterated Sub-Permutation Matrix Multiplication is the problem of computing the product of k n-by-n Boolean matrices with at most a single 1 in each row and column. For all d ≤ logk, this problem is solvable by size nO(dk1/d) monotone AC0 formulas of depth d+1, as well as semi-unbounded fan-in “SAC0” formulas of ∧-depth d and ∧-fan-in O(k1/d). In this paper, we prove matching nΩ(dk1/d) lower bounds for monotone AC0 and SAC0 formulas for all k ≤ loglogn, and slightly weaker nΩ(dk1/2d) lower bounds for non-monotone AC0 and SAC0 formulas. These size-depth tradeoffs converge at d = logk to known asymptotically tight nΩ(logk) lower bounds for both unbounded-depth monotone formulas and bounded-depth non-monotone formulas. Our lower bounds for non-monotone formulas extend to the Iterated Permutation Matrix Multiplication problem, improving the previous best known nkexp(−O(d)) tradeoff.

We study the formula complexity of the word problem $\mathsf{Word}_{S_n,k} : \{0,1\}^{kn^2} \to \{0,1\}$: given $n$-by-$n$ permutation matrices $M_1,\dots,M_k$, compute the $(1,1)$-entry of the matrix product $M_1\cdots M_k$. An important feature of this function is that it is invariant under action of $S_n^{k-1}$ given by \[ (π_1,\dots,π_{k-1})(M_1,\dots,M_k) = (M_1π_1^{-1},π_1M_2π_2^{-1},\dots,π_{k-2}M_{k-1}π_{k-1}^{-1},π_{k-1}M_k). \] This symmetry is also exhibited in the smallest known unbounded fan-in $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formulas for $\mathsf{Word}_{S_n,k}$, which have size $n^{O(\log k)}$. In this paper we prove a matching $n^{Ω(\log k)}$ lower bound for $S_n^{k-1}$-invariant formulas computing $\mathsf{Word}_{S_n,k}$. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes $\mathsf{NC}^1$ and $\mathsf{Logspace}$. Our more general main theorem gives a nearly tight $n^{d(k^{1/d}-1)}$ lower bound on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{MAJ},\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size of $\mathsf{Word}_{G,k}$ for any finite simple group $G$ whose minimum permutation representation has degree~$n$. We also give nearly tight lower bounds on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{AND},\mathsf{OR},\mathsf{NOT}\}$-formula size in the case where $G$ is an abelian group.

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.

Abstract Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1–13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a w-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $$\exp (n^{1/2-o(1)})$$ exp ( n 1 / 2 - o ( 1 ) ) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous best known $$\exp (n^{1/3-o(1)})$$ exp ( n 1 / 3 - o ( 1 ) ) due to Andreev (Algebra and Logic, 26:1–18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an $$\exp (\varOmega (n))$$ exp ( Ω ( n ) ) lower bound on the monotone arithmetic circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $$n^{\varOmega (k)}$$ n Ω ( k ) lower bound on the monotone circuit size of the CLIQUE function for all $$k \leqslant n^{1/3-o(1)}$$ k ⩽ n 1 / 3 - o ( 1 ) , strengthening the bound of Alon and Boppana (Combinatorica, 7:1–22, 1987).

We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the p-random restriction R_p for all values of p ∈ [0,1]. For a function f with domain {0,1}ⁿ, let DL(f) denote the minimum size of a decision list that computes f. We show that E[DL(f ↾ R_p)] ≤ DL(f)^log_{2/(1-p)}((1+p)/(1-p)). For example, this bound is √{DL(f)} when p = √5-2 ≈ 0.24. For Boolean functions f, we obtain the same shrinkage bound with respect to DNF formula size plus 1 (i.e., replacing DL(⋅) with DNF(⋅)+1 on both sides of the inequality).

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.

We define the criticality of a boolean function f : {0,1}^n -> {0,1} as the minimum real number lambda >= 1 such that Pr [DT_{depth}(f|R_p) >= t] <= (p lambda)^t for all p in [0,1] and t in N, where R_p is the p-random restriction and DT_{depth} is decision-tree depth. Criticality is a useful parameter: it implies an O(2^((1- 1/(2 lambda))n)) bound on the decision-tree size of f, as well as a 2^{-Omega(k/lambda)} bound on Fourier weight of f on coefficients of size >= k. In an unpublished manuscript [Rossmann, 2018], the author showed that a combination of Håstad’s switching and multi-switching lemmas [Håstad, 1986; Håstad, 2014] implies that AC^0 circuits of depth d+1 and size s have criticality at most O(log s)^d. In the present paper, we establish a stronger O(1/d log s)^d bound for regular formulas: the class of AC^0 formulas in which all gates at any given depth have the same fan-in. This result is based on (i) a novel switching lemma for bounded size (unbounded width) DNF formulas, and (ii) an extension of (i) which analyzes a canonical decision tree associated with an entire depth-d formula. As corollaries of our criticality bound, we obtain an improved #SAT algorithm and tight Linial-Mansour-Nisan Theorem for regular formulas, strengthening previous results for AC^0 circuits due to Impagliazzo, Matthews, Paturi [Impagliazzo et al., 2012] and Tal [Tal, 2017]. As a further corollary, we increase from o(log n /(log log n)) to o(log n) the number of quantifier alternations for which the QBF-SAT (quantified boolean formula satisfiability) algorithm of Santhanam and Williams [Santhanam and Williams, 2014] beats exhaustive search.

Treedepth is a well-studied graph invariant in the family of “width measures” that includes treewidth and pathwidth. Understanding these invariants in terms of excluded minors has been an active area of research. The recent Grid Minor Theorem of Chekuri and Chuzhoy [12] establishes that treewidth is polynomially approximated by the largest k × k grid minor. In this paper, we give a similar polynomial excluded-minor approximation for treedepth in terms of three basic obstructions: grids, tree, and paths. Specifically, we show that there is a constant c such that every graph of treedepth ≥ kc contains one of the following minors (each of treedepth ≥ k): the k × k grid, the complete binary tree of height k, the path of order 2k. Let us point out that we cannot drop any of the above graphs for our purpose. Moreover, given a graph G we can, in randomized polynomial time, find either an embedding of one of these minors or conclude that treedepth of G is at most kc. This result has potential applications in a variety of settings where bounded treedepth plays a role. In addition to some graph structural applications, we describe a surprising application in circuit complexity and finite model theory from recent work of the second author [28].

We prove an $n^{\Omega(\log k)}$ lower bound on the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity for all $k(n) \le \log\log n$ and formulas up to depth $\log n/(\log\log n)^{O(1)}$. This lower bound strongly separates the power of bounded-depth formulas versus circuits, since Distance $k(n)$ Connectivity is solvable by polynomial-size $\mathsf{AC^0}$ circuits of depth $O(\log k)$. For all $d(n) \le \log\log\log n$, it follows that polynomial-size depth-$d$ circuits---which are a semantic subclass of $n^{O(d)}$-size depth-$d$ formulas---are not a semantic subclass of $n^{o(d)}$-size formulas of much higher depth $\log n/(\log\log n)^{O(1)}$. Our lower bound technique probabilistically associates each gate in an $\mathsf{AC^0}$ formula with an object called a pathset. We show that with high probability these random pathsets satisfy a family of density constraints called smallness, a property akin to low average sensitivity. We then study a complexity measure on small pathsets, which lower bounds the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity. The heart of our technique is an $n^{\Omega(\log k)}$ lower bound on this pathset complexity measure.

The n-variable PARITY function is computable (by a well-known recursive construction) by AC^0 formulas of depth d+1 and leaf size n2^{dn^{1/d}}. These formulas are seen to possess a certain symmetry: they are syntactically invariant under the subspace P of even-weight elements in {0,1}^n, which acts (as a group) on formulas by toggling negations on input literals. In this paper, we prove a 2^{d(n^{1/d}-1)} lower bound on the size of syntactically P-invariant depth d+1 formulas for PARITY. Quantitatively, this beats the best 2^{Omega(d(n^{1/d}-1))} lower bound in the non-invariant setting.

This paper gives the first separation between the power of formulas and circuits of equal depth in the AC^0[\oplus] basis (unbounded fan-in AND, OR, NOT and MOD_2 gates). We show, for all d(n) <= O(log n/log log n), that there exist polynomial-size depth-d circuits that are not equivalent to depth-d formulas of size n^{o(d)} (moreover, this is optimal in that n^{o(d)} cannot be improved to n^{O(d)}). This result is obtained by a combination of new lower and upper bounds for Approximate Majorities, the class of Boolean functions {0,1}^n to {0,1} that agree with the Majority function on 3/4 fraction of inputs. AC^0[\oplus] formula lower bound. We show that every depth-d AC^0[\oplus] formula of size s has a (1/8)-error polynomial approximation over F_2 of degree O((log s)/d)^{d-1}. This strengthens a classic $O(log s)^{d-1}$ degree approximation for circuits due to Razborov. Since the Majority function has approximate degree Theta(\sqrt n), this result implies an \exp(\Omega(dn^{1/2(d-1)})) lower bound on the depth-d AC^0[\oplus] formula size of all Approximate Majority functions for all d(n) <= O(log n). Monotone AC^0 circuit upper bound. For all d(n) <= O(log n/log log n), we give a randomized construction of depth-d monotone AC^0 circuits (without NOT or MOD_2 gates) of size \exp(O(n^{1/2(d-1)}))} that compute an Approximate Majority function. This strengthens a construction of formulas of size \exp(O(dn^{1/2(d-1)})) due to Amano.

Previous work of the author [Rossmann'08] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC0 formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence of quantifier-rank k is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence of quantifier-rank poly(k). Quantitatively, this improves the result of [Rossmann'08], where the upper bound on quantifier-rank is a non-elementary function of k.

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n -variable Boolean function f , computed by a linear-size depth- d formula, which is such that any depth-( d −1) circuit that agrees with f on (1/2 + o n (1)) fraction of all inputs must have size exp( n Ω (1/d) ). This answers an open question posed by Håstad in his Ph.D. thesis (Håstad 1986b). Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Håstad (1986a), Cai (1986), and Babai (1987). We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan (Linial et al. 1993) and (Boppana 1997) on the total influence of bounded-depth circuits. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Let $P$ be a fixed graph (hereafter called a “pattern''), and let ${\sc Subgraph}(P)$ denote the problem of deciding whether a given graph $G$ contains a subgraph isomorphic to $P$. We are interested in $AC^0$-complexity of this problem, determined by the smallest possible exponent $C(P)$ for which ${\sc Subgraph}(P)$ possesses bounded-depth circuits of size $n^{C(P)+o(1)}$. Motivated by the previous research in the area, we also consider its “colorful” version ${\sc Subgraph}_\mathsf{col}(P)$ in which the target graph $G$ is $V(P)$-colored, and the average-case version ${\sc Subgraph}_\mathsf{ave}(P)$ under the distribution $G(n,n^{-\theta(P)})$, where $\theta(P)$ is the threshold exponent of $P$. Defining $C_\mathsf{col}(P)$ and $C_\mathsf{ave}(P)$ analogously to $C(P)$, our main contributions can be summarized as follows: (1) $C_\mathsf{col}(P)$ coincides with the treewidth of the pattern $P$ up to a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, and Zwick [ J. ACM, 42 (1995), pp. 844--856] is almost tight. (2) We give a characterization of $C_\mathsf{ave}(P)$ in purely combinatorial terms up to a multiplicative factor of 2. This shows that the lower bound technique of Rossman [ Proceedings of the 40th ACM Symposium on Theory of Computing, 2008, pp. 721--730] is essentially tight for any pattern $P$ whatsoever. (3) We prove that if $Q$ is a minor of $P$, then ${\sc Subgraph}_\mathsf{col}(Q)$ is reducible to ${\sc Subgraph}_\mathsf{col}(P)$ via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces ${\sc Subgraph}(M_3)$ to ${\sc Subgraph}(P_3 + M_2)$ ($P_3$ is a path on three vertices, $M_k$ is a matching with $k$ edges, and “+” stands for the disjoint union). This result strongly suggests that the colorful version of the subgraph isomorphism problem is much better structured and well-behaved than the standard (worst-case, uncolored) one.

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993 [1]. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because they use non-monotone operations to compute monotone functions, in fact, the best known lower bounds are quasipolynomial for a function in (nonmonotone) P [2]. A fundamental open problem is to prove exponential lower bounds on monotone span program size for any explicit function. We resolve this open problem by giving exponential lower bounds on monotone span program size for a function in monotone P. This also implies the first exponential lower bounds for linear secret sharing schemes. Our result is obtained by proving exponential lower bounds using Razborov's rank method [3], a measure that is strong enough to prove lower bounds for many monotone models. As corollaries we obtain new proofs of exponential lower bounds for monotone formula size, monotone switching network size, and the first lower bounds for monotone comparator circuit size for a function in monotone P. We also obtain new polynomial degree lower bounds for Nullstellensatz refutations using an interpolation theorem of Pudlak and Sgall [4]. Finally, we obtain quasipolynomial lower bounds on the rank measure for the st-connectivity function, implying tight bounds for st-connectivity in all of the computational models mentioned above.

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√logn). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglogn) lower bounds.

We show that unbounded fan-in boolean formulas of depth d + 1 and size s have average sensitivity O(1/d log s)d. In particular, this gives a tight 2Ω(d(n1/d-1)) lower bound on the size of depth d + 1 formulas computing the PARITY function. These results strengthen the corresponding O(log s)dand 2Ω(n1/d)bounds for circuits due to Boppana (1997) and Hastad (1986). Our proof technique studies a random process associated with formulas, in which the Switching Lemma is efficiently applied to subformulas.

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d - 1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size exp(nΩ(1/d)). This answers an open question posed by Hastad in his Ph.D. thesis [Has86b]. Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Hastad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14]. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Let P be a fixed graph (hereafter called a “pattern”), and let SUBGRAPH(P) denote the problem of deciding whether a given graph G contains a subgraph isomorphic to P. We are interested in AC0-complexity of this problem, determined by the smallest possible exponent C(P) for which SUBGRAPH(P) possesses bounded-depth circuits of size nC(P)+o(1). Motivated by the previous research in the area, we also consider its “colorful” version SUBGRAPHcol(P) in which the target graph G is V(P)colored, and the average-case version SUBGRAPHave(P) under the distribution G(n, n-θ(P)), where θ(P) is the threshold exponent of P. Defining Ccol(P) and Cave(P) analogously to C(P), our main contributions can be summarized as follows. (1) Ccol(P) coincides with the tree-width of the pattern P within a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, Zwick [3] is almost tight. (2) We give a characterization of Cave(P) in purely combinatorial terms within a multiplicative factor of 2. This shows that the lower bound technique of Rossman [21] is essentially tight, for any pattern P whatsoever. (3) We prove that if Q is a minor of P then SUBGRAPHcol(Q) is reducible to SUBGRAPHcol(P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M3) to SUBGRAPH(P3+ M2) (P3is a path on 3 vertices, Mk is a matching with k edges, and “+” stands for the disjoint union). This result strongly suggests that the colorful version of the subgraph isomorphism problem is much better structured and well-behaved than the standard (worstcase, uncolored) one.

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance k(n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a path of length at most k(n). This problem is solvable (by the recursive doubling technique) on circuits of depth O(log k) and size O(kn3). In contrast, we show that solving this problem on formulas of depth log n/(log log n)O(1) requires size nΩ(log k) for all k(n) ≤ log log n. As corollaries:

We present lower and upper bounds showing that the average-case complexity of the $k$-Clique problem on monotone circuits is $n^{k/4 + O(1)}$. Similar bounds for $\mathsf{AC}^0$ circuits were shown in Rossman [Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 721--730] and Amano [Comput. Complexity, 19 (2010), pp. 183--210].

It is widely suspected that Erdös-Renyi random graphs are a source of hard instances for clique problems. Giving further evidence for this belief, we prove the first average-case hardness result for the k-clique problem on monotone circuits. Specifically, we show that no monotone circuit of size O(nk/4) solves the k-clique problem with high probability on G(n,p) for two sufficiently far-apart threshold functions p(n) (for instance n-2/(k-1)and 2n-2/(k-1)). Moreover, the exponent k/4 in this result is tight up to an additive constant. One technical contribution of this paper is the introduction of quasi-sunflowers, a new relaxation of sunflowers in which petals may overlap slightly on average. A "quasi-sunflower lemma" (à la the Erdös-Rado sunflower lemma) leads to our novel lower bounds within Razborov's method of approximations.

Ehrenfeucht-Fraisse games are a useful technique for proving inexpressibility results in first-order logic. Strategies for a few basic games (on long paths, set-powerset structures and random graphs, to name a few) can be used as building blocks for strategies in more complicated games. In this talk, the author discusses a few general methods for combining strategies. Applications include results on the expressive power of successor-invariant logic and k-variable logic.

The edit distance between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this article, we present a worst-case O ( n 3 )-time algorithm for the problem when the two trees have size n , improving the previous best O ( n 3 log n )-time algorithm. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of decomposition strategy algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of Ω( n 2 log 2 n ) to Ω( n 3 ), matching our algorithm's running time. Furthermore, we obtain matching upper and lower bounds for decomposition strategy algorithms of Θ( nm 2 (1 + log n / m )) when the two trees have sizes m and n and m < n .

We prove a lower bound of ω(nk/4) on the size of constant-depth circuits solving the k-clique problem on n-vertex graphs (for every constant k). This improves a lower bound of ω(nk/89d2) due to Beame where d is the circuit depth. Our lower bound has the advantage that it does not depend on the constant d in the exponent of n, thus breaking the mold of the traditional size-depth tradeoff.

The homomorphism preservation theorem (h.p.t.), a result in classical model theory, states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory, we prove that the h.p.t. remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the Łoś--Tarski theorem and Lyndon's positivity theorem). Applications of this result extend to constraint satisfaction problems and to database theory via a correspondence between existential-positive formulas and unions of conjunctive queries. A further result of this article strengthens the classical h.p.t.: we show that a first-order formula is preserved under homomorphisms on all structures if and only if it is equivalent to an existential-positive formula of equal quantifier-rank .

Abstract We consider successor-invariant first-order logic (FO + succ) inv , consisting of sentences Φ involving an “auxiliary” binary relation S such that ( , S 1 ) ⊨ Φ ⇔ ( , S 2 ) ⊨ Φ for all finite structures and successor relations S 1 , S 2 on . A successor-invariant sentence Φ has a well-defined semantics on finite structures with no given successor relation: one simply evaluates Φ on ( , S ) for an arbitrary choice of successor relation S . In this article, we prove that (FO + succ) inv is more expressive on finite structures than first-order logic without a successor relation. This extends similar results for order-invariant logic [8] and epsilon-invariant logic [10].

In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. Here we extend the axiomatization and, in a companion paper, the proof, to cover interactive small-step algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment's replies but also the order in which the replies were received.

In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. In Part I (Interactive Small-Step Algorithms I: Axiomatization), the axiomatization was extended to cover interactive small-step algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment's replies but also the order in which the replies were received. In order to prove the thesis for algorithms of this generality, we extend here the definition of abstract state machines to incorporate explicit attention to the relative timing of replies and to the possible absence of replies. We prove the characterization theorem for extended abstract state machines with respect to general algorithms as axiomatized in Part I.

We prove the finite homomorphism preservation theorem: a first-order formula is preserved under homomorphisms on finite structures iff it is equivalent in the finite to an existential positive formula. We also strengthen the classical homomorphism preservation theorem by showing that a formula is preserved under homomorphisms on all structures iff it is equivalent to an existential positive formula of the same quantifier rank. Our method involves analysis of existential positive types and a new notion of existential positive saturation.

The Abstract State Machine Language, AsmL, is a novel executable specification language based on the theory of Abstract State Machines. AsmL is object-oriented, provides high-level mathematical data-structures, and is built around the notion of synchronous updates and finite choice. AsmL is fully integrated into the .NET framework and Microsoft development tools. In this paper, we explain the design rationale of AsmL and provide static and dynamic semantics for a kernel of the language.

A first-order sentence /spl theta/ of vocabulary /spl sigma/ /spl cup/ {S} is successor-invariant in the finite if for every finite /spl sigma/-structure M and successor relations S/sub 1/ and S/sub 2/ on M, (M, S/sub 1/) /spl vDash/ /spl theta/ /spl hArr/ (M, S/sub 2/) /spl vDash/ /spl theta/. In this paper I give an example of a non-first-order definable class of finite structures, which is, however, defined by a successor-invariant first-order sentence. This strengthens a corresponding result for order-invariant in the finite, due to Y. Gurevich.