papers
Publications (9)
cs.CC2017
Separation of AC$^0[\oplus]$ Formulas and Circuits
Benjamin Rossman, Srikanth Srinivasan
math.CO2010
The Homomorphism Domination Exponent
Swastik Kopparty, Benjamin Rossman
cs.CC2016
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
Benjamin Rossman
cs.CC2015
The Average Sensitivity of Bounded-Depth Formulas
Benjamin Rossman
cs.CC2015
An average-case depth hierarchy theorem for Boolean circuits
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
cs.DS2006
An O(n^3)-Time Algorithm for Tree Edit Distance
Erik D. Demaine, Shay Mozes, Benjamin Rossman +1
cs.LO2007
Interactive Small-Step Algorithms II: Abstract State Machines and the<br> Characterization Theorem
Andreas Blass, Yuri Gurevich, Dean Rosenzweig +1
cs.LO2007
Interactive Small-Step Algorithms I: Axiomatization
Andreas Blass, Yuri Gurevich, Dean Rosenzweig +1
cs.CC2013
Formulas vs. Circuits for Small Distance Connectivity
Benjamin Rossman