| 2025 | CSL | Equi-Rank Homomorphism Preservation Theorem on Finite Structures. | Benjamin Rossman |
| 2025 | LAGOS | Riffle Rank. | Benjamin Rossman |
| 2024 | STOC | Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. | Benjamin Rossman |
| 2020 | FOCS | Tree-depth and the Formula Complexity of Subgraph Isomorphism. | Deepanshu Kush, Benjamin Rossman |
| 2020 | LATIN | Monotone Circuit Lower Bounds from Robust Sunflowers. | Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman |
| 2020 | LATIN | Thresholds in the Lattice of Subspaces of $\mathbb {F}_q^n$. | Benjamin Rossman |
| 2018 | SODA | A Polynomial Excluded-Minor Approximation of Treedepth. | Ken-ichi Kawarabayashi, Benjamin Rossman |
| 2017 | ICALP | Subspace-Invariant AC^0 Formulas. | Benjamin Rossman |
| 2017 | ICALP | Separation of AC^0[oplus] Formulas and Circuits. | Benjamin Rossman, Srikanth Srinivasan |
| 2016 | FOCS | Exponential Lower Bounds for Monotone Span Programs. | Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook |
| 2016 | STOC | Poly-logarithmic Frege depth lower bounds via an expander switching lemma. | Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2015 | FOCS | The Average Sensitivity of Bounded-Depth Formulas. | Benjamin Rossman |
| 2015 | FOCS | An Average-Case Depth Hierarchy Theorem for Boolean Circuits. | Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2014 | CSR | The Query Complexity of Witness Finding. | Akinori Kawachi, Benjamin Rossman, Osamu Watanabe |
| 2014 | FOCS | On the AC0 Complexity of Subgraph Isomorphism. | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
| 2014 | STOC | Formulas vs. circuits for small distance connectivity. | Benjamin Rossman |
| 2012 | WoLLIC | A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs. | Benjamin Rossman |
| 2010 | FOCS | The Monotone Complexity of k-clique on Random Graphs. | Benjamin Rossman |
| 2009 | LICS | Combining Ehrenfeucht-Frass Games. | Benjamin Rossman |
| 2009 | WoLLIC | Ehrenfeucht-Frass Games on Random Structures. | Benjamin Rossman |
| 2008 | STOC | On the constant-depth complexity of k-clique. | Benjamin Rossman |
| 2007 | ICALP | An Optimal Decomposition Algorithm for Tree Edit Distance. | Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann |
| 2005 | LICS | Existential Positive Types and Preservation under Homomorphisisms. | Benjamin Rossman |
| 2003 | LICS | Successor-Invariance in the Finite. | Benjamin Rossman |