Benjamin Rossman

CSL Conference 2025 Conference Paper

Equi-Rank Homomorphism Preservation Theorem on Finite Structures

• Benjamin Rossman

The Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to finite structures, as demonstrated by the author in [Rossman, 2008; Rossman, 2017] via distinct model-theoretic and circuit-complexity based proofs. In this paper, we present a third (and significantly simpler) proof of the finitary HPT based on a generalized Cai-Fürer-Immerman construction. This method establishes a tight correspondence between syntactic parameters of a homomorphism-preserved sentence (quantifier rank, variable width, alternation height) and structural parameters of its minimal models (tree-width, tree-depth, decomposition height). Consequently, we prove a conjectured "equi-rank" version of the finitary HPT. In contrast, previous versions of the finitary HPT possess additional properties, but incur blow-ups in the quantifier rank of the equivalent existential-positive sentence.

STOC Conference 2024 Conference Paper

Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication

• Benjamin Rossman

FOCS Conference 2020 Conference Paper

Tree-depth and the Formula Complexity of Subgraph Isomorphism

• Deepanshu Kush
• Benjamin Rossman

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 AC 0 formulas of size O(n td(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.

SODA Conference 2018 Conference Paper

A Polynomial Excluded-Minor Approximation of Treedepth

• Ken-ichi Kawarabayashi
• Benjamin Rossman

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 ≥ k c 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 2 k. 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 k c. 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].

FOCS Conference 2016 Conference Paper

Exponential Lower Bounds for Monotone Span Programs

• Robert Robere
• Toniann Pitassi
• Benjamin Rossman
• Stephen A. Cook

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.

STOC Conference 2016 Conference Paper

Poly-logarithmic Frege depth lower bounds via an expander switching lemma

• Toniann Pitassi
• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√log n ). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglog n ) lower bounds. The 3-CNF formulas which we use to establish this result are Tseitin contradictions on 3-regular expander graphs. In more detail, our main result is a proof that for every d , any depth- d Frege refutation of the Tseitin contradiction over these n -node graphs must have size n Ω((log n )/ d 2 ) . A key ingredient of our approach is a new switching lemma for a carefully designed random restriction process over these expanders. These random restrictions reduce a Tseitin instance on a 3-regular n -node expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3-regular n ′-node expander, for some n ′ which is not too much less than n . Our result involves Ω(√log n ) iterative applications of this type of random restriction.

FOCS Conference 2015 Conference Paper

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

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

FOCS Conference 2015 Conference Paper

The Average Sensitivity of Bounded-Depth Formulas

• Benjamin Rossman

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(n 1/d -1) ) lower bound on the size of depth d + 1 formulas computing the PARITY function. These results strengthen the corresponding O(log s) d and 2 Ω(n 1/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.

STOC Conference 2014 Conference Paper

Formulas vs. circuits for small distance connectivity

• Benjamin Rossman

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 ( kn 3 ). 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: (i) It follows that polynomial-size circuits for Distance k ( n ) Connectivity require depth Ω(log k ) for all k ( n ) ≤ log log n . This matches the upper bound from recursive doubling and improves a previous Ω(log log k ) lower bound of Beame, Impagliazzo and Pitassi [BIP98]. (ii) We get a tight lower bound of s Ω( d ) on the size required to simulate size- s depth- d circuits by depth- d formulas for all s ( n ) = n O (1) and d ( n ) ≤ log log log n . No lower bound better than s Ω(1) was previously known for any d ( n ) ≮ O (1). Our proof technique is centered on a new notion of pathset complexity , which roughly speaking measures the minimum cost of constructing a set of (partial) paths in a universe of size n via the operations of union and relational join, subject to certain density constraints. Half of our proof shows that bounded-depth formulas solving Distance k ( n ) Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity.

FOCS Conference 2014 Conference Paper

On the AC0 Complexity of Subgraph Isomorphism

• Yuan Li
• Alexander A. Razborov
• Benjamin Rossman

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 n C(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 SUBGRAP Have (P) under the distribution G(n, n -θ (P)), where θ(P) is the threshold exponent of P. Defining C col (P) and Cave(P) analogously to C(P), our main contributions can be summarized as follows. (1) C col (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 SUBGRAPH col (Q) is reducible to SUBGRAPH col (P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M 3 ) to SUBGRAPH(P 3 + M 2 ) (P 3 is 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.

FOCS Conference 2010 Conference Paper

The Monotone Complexity of k-clique on Random Graphs

• Benjamin Rossman

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(n k/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.

STOC Conference 2008 Conference Paper

On the constant-depth complexity of k-clique

• Benjamin Rossman

TCS Journal 2005 Journal Article

Semantic essence of AsmL

• Yuri Gurevich
• Benjamin Rossman
• Wolfram Schulte