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 (F_q)ⁿ
  
  
• 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 AC⁰[⊕] Formulas and Circuits (with Srikanth Srinivasan)
  ICALP 2017
  
  
• Subspace-Invariant AC⁰ 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 NC¹
  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 AC⁰ 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

• Approximate Sunflowers
  
  
• Criticality and Decision Tree Size of AC⁰
  A proof that AC⁰ circuits have decision trees of size 2^(1-ε)n where ε = 1/O(log s)^d-1
  
  
• An Entropy Proof of the Switching Lemma
  
  
• A Switching Lemma Tutorial
  Slides from a talk at the Low-Depth Complexity Workshop in St. Petersburg, Russia, 2016
  
  
• PARITY ∉ AC⁰ from DNF Sparsification
  A lower bound for PARITY using the DNF sparsification theorem of Gopalan, Meka and Reingold