Benjamin Rossman

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 10, 2024 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 ... Full text Cite

Symmetric Formulas for Products of Permutations

Conference Leibniz International Proceedings in Informatics, LIPIcs · January 1, 2023 We study the formula complexity of the word problem WordSn,k : (0, 1)kn2 → (0, 1): given n-by-n permutation matrices M1,..., Mk, compute the (1, 1)-entry of the matrix product M1 · · · Mk. An important feature of this function is that it is invariant under ... Full text Cite

TREE-DEPTH AND THE FORMULA COMPLEXITY OF SUBGRAPH ISOMORPHISM

Journal Article SIAM Journal on Computing · January 1, 2023 For a fixed "pattern"" graph G, the colored G-subgraph isomorphism problem (denoted by 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 paramete ... Full text Cite

Monotone Circuit Lower Bounds from Robust Sunflowers.

Journal Article Algorithmica · January 2022 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 ... Full text Cite

Shrinkage of decision lists and DNF formulas

Conference Leibniz International Proceedings in Informatics, LIPIcs · February 1, 2021 We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the p-random restriction Rp for all values of p ∈ [0, 1]. For a function f with domain {0, 1}n, let DL(f) denote the minimum size of a decision list that co ... Full text Cite

A polynomial excluded-minor approximation of treedepth

Journal Article Journal of the European Mathematical Society · January 1, 2021 Treedepth is a minor-monotone graph invariant in the family of "width measures"that includes treewidth and pathwidth. The characterization and approximation of these invariants in terms of excluded minors has been a topic of interest in the study of sparse ... Full text Cite

Tree-depth and the formula complexity of subgraph isomorphism

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · November 1, 2020 For a fixed'pattern' graph G, the colored G-subgraph isomorphism problem (denoted text{SUB}(G)) asks, given an n-vertex graph H and a coloring V(H) rightarrow V(G), whether H contains a properly colored copy of G. The complexity of this problem is tied to ... Full text Cite

Thresholds in the Lattice of Subspaces of Fqn

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 Let Q be an ideal (downward-closed set) in the lattice of linear subspaces of Fqn, ordered by inclusion. For 0 ⩽ k⩽ n, let μk(Q) denote the fraction of k-dimensional subspaces that belong to Q. We show that these densities satisfyμk(Q)=11+z⟹μk+1(Q)⩽11+qz.T ... Full text Cite

Monotone Circuit Lower Bounds from Robust Sunflowers

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020 Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity[14], DNF sparsification[6], randomness extractors[8], and recent advances on the Erdős-Rado sunflower conjecture[3, 9, 12]. The recent ... Full text Cite

Criticality of regular formulas

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2019 We define the criticality of a boolean function f : {0, 1}n → {0, 1} as the minimum real number λ ≥ 1 such that P DTdepth(fRp) ≥ t ≤ (pλ)t for all p ∈ [0, 1] and t ∈ N, where Rp is the p-random restriction and DTdepth is decision-tree depth. Criticality is ... Full text Cite

Separation of AC⁰[⊕] formulas and circuits

Journal Article Theory of Computing · January 1, 2019 We give the first separation between the power of formulas and circuits in the AC0[⊕] basis (unbounded fan-in AND, OR, NOT and MOD2 gates). We show that there exist poly(n)-size depth-d circuits that are not equivalent to any depth-d formula of size no(d) ... Full text Cite

Subspace-invariant AC⁰ formulas

Journal Article Logical Methods in Computer Science · January 1, 2019 We consider the action of a linear subspace U of {0, 1}n on the set of AC0 formulas with inputs labeled by literals in the set (formula presented), where an element u ∈ U acts on formulas by transposing the ith pair of literals for all i ∈ [n] such that ui ... Full text Cite

The Average Sensitivity of Bounded-Depth Formulas

Journal Article Computational Complexity · June 1, 2018 We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity O(1dlogs)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 stren ... Full text Cite

Formulas versus circuits for small distance connectivity

Conference SIAM Journal on Computing · January 1, 2018 We prove an nΩ (log k) lower bound on the AC0formula size of Distance k(n) Connectivity for all k(n) ≤ 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 ... Full text Cite

A polynomial excluded-minor approximation of treedepth

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2018 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 an ... Full text Cite

Lower bounds for subgraph isomorphism

Conference Proceedings of the International Congress of Mathematicians, ICM 2018 · January 1, 2018 We consider the problem of determining whether an Erdős–Rényi random graph contains a subgraph isomorphic to a fixed pattern, such as a clique or cycle of constant size. The computational complexity of this problem is tied to fundamental open questions inc ... Cite

An improved homomorphism preservation theorem from lower bounds in circuit complexity

Conference Leibniz International Proceedings in Informatics, LIPIcs · November 1, 2017 Previous work of the author [39] 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 bou ... Full text Cite

An average-case depth hierarchy theorem for boolean circuits

Journal Article Journal of the ACM · August 1, 2017 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 ... Full text Cite

The Query Complexity of Witness Finding

Journal Article Theory of Computing Systems · August 1, 2017 We study the following information-theoretic witness finding problem: for a hidden nonempty subset W of {0,1}n, how many non-adaptive randomized queries (yes/no questions about W) are needed to guess an element x∈{0,1}n such that x∈W with probability >1/2? ... Full text Cite

Separation of AC⁰[⊕] formulas and circuits

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2017 This paper gives the first separation between the power of formulas and circuits of equal depth in the AC0[⊕] basis (unbounded fan-in AND, OR, NOT and MOD2 gates). We show, for all d(n) ≤ O( log n/log log n ), that there exist polynomial-size depth-d circu ... Full text Cite

Subspace-invariant AC⁰ formulas

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2017 The n-variable PARITY function is computable (by a well-known recursive construction) by AC0 formulas of depth d + 1 and leafsize n·2dn1/d. These formulas are seen to possess a certain symmetry: they are syntactically invariant under the subspace P of even ... Full text Cite

On the AC⁰ complexity of subgraph isomorphism

Journal Article SIAM Journal on Computing · January 1, 2017 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 ... Full text Cite

Exponential Lower Bounds for Monotone Span Programs

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 14, 2016 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 cryptog ... Full text Cite

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

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2016 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, ... Full text Cite

An Average-Case Depth Hierarchy Theorem for Boolean Circuits

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 11, 2015 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 ... Full text Cite

The Average Sensitivity of Bounded-Depth Formulas

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 11, 2015 We show that unbounded fan-in boolean formulas of depth d + 1 and size s have average sensitivity O(log s/d)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 st ... Full text Cite

Correlation bounds against monotone NC¹

Conference Leibniz International Proceedings in Informatics, LIPIcs · June 1, 2015 This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC1 of polynomial-size O(log n)-depth monotone circuits. Our main theorem, proved using the pathset complexity framework intro ... Full text Cite

On the AC⁰ complexity of subgraph isomorphism

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · December 7, 2014 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 ... Full text Cite

The query complexity of witness finding

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2014 We study the following information-theoretic witness finding problem: for a hidden nonempty subset W of {0,1} n, how many non-adaptive randomized queries (yes/no questions about W) are needed to guess an element x∈ {0,1} n such that x∈ W with probability > ... Full text Cite

Formulas vs. circuits for small distance connectivity

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2014 We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance κ (n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a pat ... Full text Cite

The monotone complexity of k-clique on random graphs

Conference SIAM Journal on Computing · January 1, 2014 We present lower and upper bounds showing that the average-case complexity of the k-Clique problem on monotone circuits is nk/4+O(1). Similar bounds for AC0 circuits were shown in Rossman [Proceedings of the 40th Annual ACM Symposium on Theory of Computing ... Full text Cite

A tight upper bound on the number of variables for average-case k-clique on ordered graphs

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · September 24, 2012 A first-order sentence φ defines k-clique in the average-case if lim/n→∞ Pr/G=G(n,p) [G unknown sign φ ⇔ G contains a k-clique] = 1 where G = G(n,p) is the Erdos-Rényi random graph with p (= p(n)) the exact threshold such that Pr[G(n,p) has a k-clique] = 1 ... Full text Cite

The homomorphism domination exponent

Journal Article European Journal of Combinatorics · October 1, 2011 We initiate a study of the homomorphism domination exponent of a pair of graphs F and G, defined as the maximum real number c such that |Hom(F,T)|≥|Hom(G,T)|c for every graph T. The problem of determining whether HDE(F,G)≥1 is known as the homomorphism dom ... Full text Cite

Choiceless computation and symmetry

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · September 20, 2010 Many natural problems in computer science concern structures like graphs where elements are not inherently ordered. In contrast, Turing machines and other common models of computation operate on strings. While graphs may be encoded as strings (via an adjac ... Full text Cite

The monotone complexity of k-clique on random graphs

Conference Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 2010 It is widely suspected that Erdocombining double acute accents-Rényi 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 mono ... Full text Cite

Circuits, Logic, and Games

Conference Dagstuhl Seminar Proceedings · January 1, 2010 Cite

An optimal decomposition algorithm for tree edit distance

Journal Article ACM Transactions on Algorithms · December 1, 2009 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. I ... Full text Cite

Ehrenfeucht-Fraïssé Games on Random Structures

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · August 20, 2009 Certain results in circuit complexity (e.g., the theorem that AC 0 functions have low average sensitivity) [5, 17] imply the existence of winning strategies in Ehrenfeucht-Fraïssé games on pairs of random structures (e.g., ordered random graphs G∈=∈G(n,1/2 ... Full text Cite

Homomorphism preservation theorems

Journal Article Journal of the ACM · July 1, 2008 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 formul ... Full text Cite

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs

Journal Article Annals of Pure and Applied Logic · March 1, 2008 We consider Choiceless Polynomial Time (over(C, ̃) PT), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting (IFP + C) from P. ... Full text Cite

On the constant-depth complexity of k-clique

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 2008 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/59d2) due to Beame where d is the circuit depth. Our lower bound has the ad ... Full text Cite

Interactive small-step algorithms I: Axiomatization

Journal Article Logical Methods in Computer Science · November 5, 2007 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 acco ... Full text Cite

Interactive small-step algorithms II: Abstract state machines and the characterization theorem

Successor-invariant first-order logic on finite structures

Journal Article Journal of Symbolic Logic · June 1, 2007 We consider successor-invariant first-order logic (FO + succ) inv, consisting of sentences Φ involving an "auxiliary" binary relation S such that (Θ, S1) |= Φ ⇔ (Θ, S2) |= Φ for all finite structures Θ and successor relations S1, S2 on Θ. A successor-invar ... Full text Cite

An optimal decomposition algorithm for tree edit distance

Conference Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2007 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. I ... Full text Cite

Choiceless polynomial time, counting and the cai-fürer-immerman graphs: (Extended abstract)

Conference Electronic Notes in Theoretical Computer Science · January 6, 2006 We consider Choiceless Polynomial Time (C̃PT), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting (IFP + C) from P. This set ... Full text Cite

Existential positive types and preservation under homomorphisms

Conference Proceedings - Symposium on Logic in Computer Science · October 25, 2005 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 preserva ... Cite

Semantic essence of AsmL

Conference Theoretical Computer Science · October 17, 2005 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 ... Full text Cite

Semantic essence of asml: Extended abstract

Journal Article Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2004 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 datastructures, and is built around the notion of synchronous ... Full text Cite

Successor-invariance in the finite

Conference Proceedings - Symposium on Logic in Computer Science · January 1, 2003 A first-order sentence θ of vocabulary σ {S} is successor-invariant in the finite if for every finite σ-structure M and successor relations S1 and S2 on M, (M, S1) |= θ ⇔ (M, S2) |= θ. In this paper I give an example of a non-first-order definable class of ... Cite