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

Showing 2020Show all

3 papers · 1 filter

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(…