Benjamin Rossman
Assistant Professor of Mathematics and Computer Science, University of Toronto
Office:
Bahen 6214 and Sandford Fleming 2302B
Email:
ben.rossman [at] utoronto.ca
As of January 2020, I have moved to Duke University.
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.
Teaching
MAT 309: Introduction to Mathematical Logic (Fall 2019)
CSC 463: Computational Complexity and Computability (Winter 2019)
CSC 2429 / MAT 1304: Topics in the Theory of Computation - Circuit Complexity (Winter 2019)
Publications
-
Thresholds in the Lattice of Subspaces of (Fq)n
-
Monotone Circuit Lower Bounds from Robust Sunflowers
(with
Bruno Pasqualotto Cavalar
and Mrinal Kumar)
-
Criticality of Regular Formulas
CCC 2019
-
Lower Bounds for Subgraph Isomorphism
survey article for ICM 2018
-
A Polynomial Excluded-Minor Approximation of Treedepth
(with
Ken-ichi Kawarabayashi)
SODA 2018
-
Separation of AC0[⊕] Formulas and Circuits
(with
Srikanth Srinivasan)
ICALP 2017
-
Subspace-Invariant AC0 Formulas
ICALP 2017
-
An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity
ITCS 2017
-
Exponential Lower Bounds for Monotone Span Programs
(with
Robert Robere,
Toni Pitassi and
Steve Cook)
FOCS 2016
-
Poly-Logarithmic Frege Depth Lower Bounds Via an Expander Switching Lemma
(with
Toni Pitassi,
Rocco Servedio
and
Li-Yang Tan)
STOC 2016
-
The Average Sensitivity of Bounded-Depth Formulas
FOCS 2015 (journal version: Computational Complexity, Vol. 27, Issue 2, 2018, pages 209-223)
-
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
(with Rocco Servedio and Li-Yang Tan)
FOCS 2015 (best paper award)
-
The Polynomial Hierarchy, Random Oracles and Boolean Circuits
(with Rocco Servedio and Li-Yang Tan)
SIGACT News (Complexity Theory Column), December 2015
-
Correlation Bounds Against Monotone NC1
CCC 2015 (best paper award)
-
Formulas vs. Circuits for Small Distance Connectivity
STOC 2014 (journal version: SIAM Journal on 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)
-
The Query Complexity of Witness Finding
(with Akinori Kawachi and Osamu Watanabe)
CSR 2014 (best paper award)
-
The Monotone Complexity of k-Clique on Random Graphs
SIAM Journal on Computation, Volume 43, Issue 1: 256-279, 2014
-
The Number of Variables for Average-Case k-Clique on Ordered Graphs
WoLLIC 2012
-
The Homomorphism Domination Exponent
(with Swastik Kopparty)
European Journal of Combinatorics, Volume 32, Issue 7: 1097-1114, 2011
-
An Optimal Decomposition Algorithm for Tree Edit Distance
(with Erik Demaine, Shay Mozes and Oren Weimann)
ACM Transactions on Algorithms, Volume 6 (1:2): 1-19, 2011
-
Average-Case Complexity of Detecting Cliques
PhD thesis, 2010
-
Choiceless Computation and Symmetry
In "Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday", LNCS, Volume 6300, Springer-Verlag, 565-580, 2010
-
Ehrenfeucht-Fraïssé Games on Random Graphs
WoLLIC 2009
-
On the Constant-Depth Complexity of k-Clique
STOC 2008
-
Homomorphism Preservation Theorems
Journal of the ACM, Volume 55, Issue 3: 1-53, 2008
-
Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs
(with Anuj Dawar and David Richerby)
Annals of Pure and Applied Logic, 152: 31-50, 2008
-
Coin-Flipping Magic
(with Nadia Benbernou, Erik Demaine and Martin Demaine)
manuscript (presented at Gathering for Gardner 8), April 2008
-
Successor-Invariant First-Order Logic on Finite Structures
Journal of Symbolic Logic, Volume 72, Issue 2: 601-619, 2007
-
Interactive Small-Step Algorithms I: Axiomatization
(with Andreas Blass, Yuri Gurevich and Dean Rosenzweig)
Logical Methods in Computer Science, Volume 3 (4:3): 1-29, 2007
-
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem
(with Andreas Blass, Yuri Gurevich and Dean Rosenzweig)
Logical Methods in Computer Science,
Volume 3 (4:4): 1-35, 2007
-
Semantic Essence of AsmL
(with Yuri Gurevich and Wolfram Schulte)
Theoretical Computer Science, Volume 343, Issue 3: 370-412, 2005
-
Explicit Graphs with Extension Properties
(with Andreas Blass)
Bulletin of the European Association for Theoretical Computer Science, Number 86: 166-175, 2005
Some notes and slides