Benjamin Rossman
Associate Professor of Computer Science
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 Computer Science and Mathematics and member of the Theory Group at Duke University .
Previously I held faculty positions at the University of Toronto and the National Institute of Informatics in Tokyo, Japan.
I completed my Ph.D. at MIT under Madhu Sudan .
My interests lie in computational complexity and logic.
I primarily work in the areas of circuit complexity (the quest for lower bounds in combinatorial models of computation) and finite model theory (the study of logical definability on finite structures).
A major focus on my work has been the average-case circuit complexity of subgraph isomorphism problems; see this survey for an overview.
My research has been supported by NSERC Discovery and Accelerator Grants, the Ontario Early Researcher Award, and a Sloan Research Fellowship.
Teaching
Publications
Tree-depth and the Formula Complexity of Subgraph Isomorphism
(with Deepanshu Kush )
Preprint
Thresholds in the Lattice of Subspaces of (F_{q} )^{n}
14th Latin American Theoretical Informatics Symposium (LATIN 2020)
Monotone Circuit Lower Bounds from Robust Sunflowers
(with
Bruno Pasqualotto Cavalar
and Mrinal Kumar )
14th Latin American Theoretical Informatics Symposium (LATIN 2020)
Criticality of Regular Formulas
Proceedings 34th Computational Complexity Conference (CCC), LIPIcs, Volume 137, Article No. 1: 1-28, 2019
Lower Bounds for Subgraph Isomorphism
Proceedings of the International Congress
of Mathematicians, Rio de Janeiro, Volume 3, 3409-3430, 2018
A Polynomial Excluded-Minor Approximation of Treedepth
(with
Ken-ichi Kawarabayashi )
Proceedings 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), 234-246, 2018
Separation of AC^{0} [⊕] Formulas and Circuits
(with
Srikanth Srinivasan )
Theory of Computing, Volume 15, Article 1054: 1-18, 2019
Subspace-Invariant AC^{0} Formulas
Logical Methods in Computer Science, Volume 15, Issue 3: 1-12, 2019
An Improved Homomorphism Preservation Theorem from Lower Bounds in Circuit Complexity
Proceedings 8th Innovations in Theoretical Computer Science (ITCS), LIPIcs, Volume 67, Article No. 27: 1-17, 2017
Formulas vs. Circuits for Small Distance Connectivity
SIAM Journal on Computing, Volume 47, Number 5:
1986-2028, 2018
Correlation Bounds Against Monotone NC^{1}
Proceedings 30th Computational Complexity Conference (CCC), LIPIcs, Volume 33: 392-411, 2015
The Average Sensitivity of Bounded-Depth Formulas
Computational Complexity, Volume 27, Issue 2: 209-223, 2018
Exponential Lower Bounds for Monotone Span Programs
(with
Robert Robere ,
Toni Pitassi and
Steve Cook )
Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 406-416, 2016
Poly-Logarithmic Frege Depth Lower Bounds Via an Expander Switching Lemma
(with
Toni Pitassi ,
Rocco Servedio
and
Li-Yang Tan )
Proceedings 48th ACM Symposium on Theory of Computing (STOC), 644-657, 2016
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
(with
Johan Håstad ,
Rocco Servedio and Li-Yang Tan )
Journal of the ACM, Volume 64, Issue 5: 1-27, 2017
The Polynomial Hierarchy, Random Oracles and Boolean Circuits
(with Rocco Servedio and Li-Yang Tan)
SIGACT News, Complexity Theory Column 89, Volume 46, Issue 4: 50-68, 2015
On the AC^{0} Complexity of Subgraph Isomorphism
(with Yuan Li and Alexander Razborov )
SIAM Journal on Computing, Volume 46, Number 3: 936-931, 2017
The Query Complexity of Witness Finding
(with Akinori Kawachi and Osamu Watanabe )
Theory of Computing Systems, Volume 61, Issue 2: 305-321, 2017
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
Proceedings 19th Workshop on Logic, Language, Information and Computation (WoLLIC), 282-290, 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", Springer LNCS, Volume 6300: 565-580, 2010
Ehrenfeucht-Fraïssé Games on Random Graphs
Proceedings 16th Workshop on Logic, Language, Information and Computation (WoLLIC), 350-364, 2009
On the Constant-Depth Complexity of k -Clique
Proceedings 40th Annual ACM Symposium on the Theory of Computing (STOC), 721-730, 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
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
Notes and slides