Benjamin Rossman
Associate Professor of Computer Science, Duke University
Levine Science Research Center, Room D110
308 Research Drive ·
Durham, NC 27708
E-mail: benjamin.rossman [at] duke.edu
I am an associate professor in the Computer Science and Mathematics Departments and a member of the Theory Group at Duke University.
Previously, I held a faculty position at the University of Toronto and postdocs at the Tokyo Institute of Technology and National Institute of Informatics in Japan.
I completed my PhD at MIT under the supervision of Madhu Sudan.
My research seeks to understand how the structural properties of combinatorial problems influence their computational and descriptive complexity. My most significant results establish unconditional lower bounds in various circuit models for subgraph isomorphism problems, such as clique and connectivity in random graphs.
I have openings for PhD students in the upcoming academic year. Feel free to contact me if interested.
Teaching
- CompSci 335: Computational Complexity (Fall 2025)
Publications
Recent
- Equirank Homomorphism Preservation Theorem on Finite Structures (CSL'25)
- Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication (STOC'24)
- Multi-Quadratic Sum-of-Squares and Lower Bounds for Arithmetic Formulas (with Davidson Zhu) (preprint)
- On Sidorenko’s Conjecture for Bipartite Möbius Ladders (preprint)
- Riffle Rank (preprint)
Complexity of average-case subgraph isomorphism problems (k-clique, k-stconn)
- Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
- Treedepth and the Formula Complexity of Subgraph Isomorphism (with Deepanshu Kush)
- Formulas vs. Circuits for Small Distance Connectivity
- Correlation Bounds Against Monotone NC1
- On the AC0 Complexity of Subgraph Isomorphism (with Yuan Li and Alexander Razborov)
- The Monotone Complexity of k-Clique on Random Graphs
- On the Constant-Depth Complexity of k-Clique
- Average-Case Complexity of Detecting Cliques (Ph.D. thesis)
- Lower Bounds for Subgraph Isomorphism (survey article)
Other complexity papers
- Multi-Quadratic Sum-of-Squares and Lower Bounds for Arithmetic Formulas (with Davidson Zhu) (preprint)
- Riffle Rank (preprint)
- Symmetric Formulas for Products of Permutations (with William He)
- Shrinkage of Decision Lists and DNF Formulas
- Monotone Circuit Lower Bounds from Robust Sunflowers (with Bruno Pasqualotto Cavalar and Mrinal Kumar)
- Criticality of Regular Formulas
- Separation of AC0[⊕] Formulas and Circuits (with Srikanth Srinivasan)
- Subspace-Invariant AC0 Formulas
- The Average Sensitivity of Bounded-Depth Formulas
- Exponential Lower Bounds for Monotone Span Programs (with Robert Robere, Toni Pitassi and Steve Cook)
- Poly-Logarithmic Frege Depth Lower Bounds Via an Expander Switching Lemma (with Toni Pitassi, Rocco Servedio and Li-Yang Tan)
- An Average-Case Depth Hierarchy Theorem for Boolean Circuits (with Johan Håstad, Rocco Servedio and Li-Yang Tan)
- The Polynomial Hierarchy, Random Oracles and Boolean Circuits (with Rocco Servedio and Li-Yang Tan)
- The Query Complexity of Witness Finding (with Akinori Kawachi and Osamu Watanabe)
Combinatorics
- On Sidorenko’s Conjecture for Bipartite Möbius Ladders (preprint)
- Thresholds in the Lattice of Subspaces of Fqn
- A Polynomial Excluded-Minor Approximation of Treedepth (with Ken-ichi Kawarabayashi)
- The Homomorphism Domination Exponent (with Swastik Kopparty)
- Explicit Graphs with Extension Properties (with Andreas Blass)
- An Optimal Decomposition Algorithm for Tree Edit Distance (with Erik Demaine, Shay Mozes and Oren Weimann)
- Coin-Flipping Magic (with Nadia Benbernou, Erik Demaine and Martin Demaine)
Finite model theory
- Equirank Homomorphism Preservation Theorem on Finite Structures
- An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity
- Homomorphism Preservation Theorems
- Choiceless Computation and Symmetry
- Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs (with Anuj Dawar and David Richerby)
- Successor-Invariant First-Order Logic on Finite Structures
- Ehrenfeucht-Fraïssé Games on Random Graphs
- The Number of Variables for Average-Case k-Clique on Ordered Graphs
Abstract state machines
- Interactive Small-Step Algorithms I: Axiomatization (with Andreas Blass, Yuri Gurevich and Dean Rosenzweig)
- Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem (with Andreas Blass, Yuri Gurevich and Dean Rosenzweig)
- Semantic Essence of AsmL (with Yuri Gurevich and Wolfram Schulte)
Notes and slides
- Round-Query Tradeoff for Single Element Recovery on Affine Sets
- Approximate Sunflowers (a.k.a. robust sunflowers, quasi-sunflowers)
- Criticality and Decision Tree Size of AC0 Circuits
- A Switching Lemma Tutorial (slides)
- PARITY ∉ AC0 from DNF Sparsification