Benjamin Rossman

activity

20062026

most citedAn O(n^3)-Time Algorithm for Tree Edit Distance

206 citations · 246 across the 10 of their papers we have counts for

collaborators

15 papers

cs.CC2026

On Top-Down and Local Lower Bounds for $A C^{0}$ Circuits

Gülce Kardeş, Benjamin Rossman

Classical lower bounds for $A C^{0}$ circuits proceed bottom-up by simplifying or approximating gates beginning at the input layer. We introduce a complementary top-down mode…

cs.CC2022

Symmetric Formulas for Products of Permutations

William He, Benjamin Rossman

We study the formula complexity of the word problem $Word_{S_{n}, k} : {0, 1}^{k n^{2}} \to {0, 1}$ : given $n$ -by- $n$ permutation matrices $M_{1}, \dots, M_{k}$ , compute the $(1, 1)$ …

cs.CC2020

Shrinkage of Decision Lists and DNF Formulas

Benjamin Rossman

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 \in [0, 1]$ . For a…

cs.CC2020★ 4 cited

Monotone Circuit Lower Bounds from Robust Sunflowers

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent adva…

cs.CC2020

Tree-depth and the Formula Complexity of Subgraph Isomorphism

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$ , the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted $SUB (G)$ ) asks, given an $n$ -vertex graph $H$ and a coloring $V(H) \to V(…

math.CO2019

Thresholds in the Lattice of Subspaces of $(F_{q})^{n}$

Benjamin Rossman

Let $Q$ be an ideal (downward-closed set) in the lattice of linear subspaces of $(F_{q})^{n}$ , ordered by inclusion. For $0 \leq k \leq n$ , let $μ_{k} (Q)$ denote the fraction of $k…

On Top-Down and Local Lower Bounds for AC0 Circuits

Symmetric Formulas for Products of Permutations

Shrinkage of Decision Lists and DNF Formulas

Monotone Circuit Lower Bounds from Robust Sunflowers

Tree-depth and the Formula Complexity of Subgraph Isomorphism

Thresholds in the Lattice of Subspaces of (Fq​)n

On Top-Down and Local Lower Bounds for $A C^{0}$ Circuits

Thresholds in the Lattice of Subspaces of $(F_{q})^{n}$