Assistant Professor of Mathematics and Computer Science, University of Toronto
Bahen 6214 and Sandford Fleming 2302B
ben.rossman [at] utoronto.ca
I am an assistant professor at the University of Toronto with a joint appointment in the mathematics and computer science departments.
Previously, I was an assistant professor at the National Institute of Informatics in Tokyo, Japan and a postdoc at the Tokyo Institute of Technology and the Simons Institute for the Theory of Computing in Berkeley. I completed my Ph.D. at MIT where I was fortunate to be advised by Madhu Sudan.
My research lies in computational complexity theory, specifically the areas of circuit complexity and finite model theory. I am supported by grants from NSERC, the Ontario Early Researcher Award and a Sloan Research Fellowship.
My CV is available here.
In Fall 2018 I am coorganizing a semester program on Lower Bounds in Computational Complexity at the Simons Institute.
In Winter 2018 I am teaching CSC 463 (Computational Complexity and Computability) and CSC 2429/MAT 1304 (Circuit Complexity).
MAT 309: Introduction to Mathematical Logic (Winter 2017 and Winter 2018),
Mini-course on Boolean Circuit Complexity at the 4th Swedish Summer School in Computer Science (July 2017),
CSC 2429/MAT 1304: Circuit Complexity (Fall 2016)
Recent and Selected Publications (see all)
Sharp Bounds for Regular Formulas
manuscript (subsumes an earlier note on an entropy proof of the switching lemma)
Lower Bounds for Subgraph Isomorphism
survey for ICM 2018
A Polynomial Excluded-Minor Approximation of Treedepth
Separation of AC0[⊕] Formulas and Circuits
Subspace-Invariant AC0 Formulas
An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity
Homomorphism Preservation Theorems, J.ACM 2008)
Exponential Lower Bounds for Monotone Span Programs
Toni Pitassi and
The Average Sensitivity of Bounded-Depth Formulas
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
(with Rocco Servedio and Li-Yang Tan)
FOCS 2015 (best paper award)
Correlation Bounds Against Monotone NC1
CCC 2015 (best paper award)
Formulas vs. Circuits for Small Distance Connectivity
STOC 2014 (journal version: SIAM Journal of Computing, Vol. 47, No 5, 2018, pages 1986-2028)
On the AC0 Complexity of Subgraph Isomorphism
(with Yuan Li and Alexander Razborov)
FOCS 2014 (journal version: SIAM Journal on Computing, Vol. 46, No 3, 2017, pages 936-971)