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 2015Show all

2 papers · 1 filter

cs.CC2015

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 (\frac{1}{d} lo g s)^{d}$ . In particular, this gives a tight $2^{Ω(d(n^{1/d}-1))}…

cs.CC2015

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…