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 research interests lie in computational complexity and logic, specifically 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). My work is supported by NSERC Discovery and Accelerator Grants, the Ontario Early Researcher Award, and a Sloan Research Fellowship.

Teaching

• Duke, COMPSCI 230: Discrete Mathematics for Computer Science (Spring 2020)
  
• Duke, COMPSCI 590/MATH 590: Circuit Complexity (Fall 2020)
  
• University of Toronto, MAT 309: Introduction to Mathematical Logic (Fall 2019)
  
• University of Toronto, CSC 463: Computational Complexity and Computability (Winter 2019)
  
• University of Toronto, CSC 2429 / MAT 1304: Topics in the Theory of Computation - Circuit Complexity (Winter 2019)
  
  

Publications

• Shrinkage of Decision Lists and DNF Formulas
  ITCS 2021
  
• Tree-depth and the Formula Complexity of Subgraph Isomorphism (with Deepanshu Kush)
  FOCS 2020
  
• Thresholds in the Lattice of Subspaces of (F_q)ⁿ
  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⁰[⊕] Formulas and Circuits (with Srikanth Srinivasan)
  Theory of Computing, Volume 15, Article 1054: 1-18, 2019
  
• Subspace-Invariant AC⁰ 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¹
  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⁰ 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

• Approximate Sunflowers (a.k.a. quasi-sunflowers, robust sunflowers)
  Short note on a generalization of sunflowers that played a role in the recent breakthrough of Alweiss, Lovett, Wu and Zhang
• 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
  
• 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