Successor-Invariance in the Finite. - Benjamin Rossman (LICS, 2003)

Existential Positive Types and Preservation under Homomorphisisms. - Benjamin Rossman (LICS, 2005)

Explicit Graphs with Extension Properties. - Andreas Blass; Benjamin Rossman (Bull. EATCS, 2005)

Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract). - Anuj Dawar; David Richerby; Benjamin Rossman (WoLLIC, 2005)

Semantic essence of AsmL. - Yuri Gurevich; Benjamin Rossman; Wolfram Schulte (Theor. Comput. Sci., 2005)

An O(n^3)-Time Algorithm for Tree Edit Distance - Erik D. Demaine; Shay Mozes; Benjamin Rossman; Oren Weimann (CoRR, 2006)

Successor-invariant first-order logic on finite structures. - Benjamin Rossman (J. Symb. Log., 2007)

Interactive Small-Step Algorithms I: Axiomatization. - Andreas Blass; Yuri Gurevich; Dean Rosenzweig; Benjamin Rossman (Log. Methods Comput. Sci., 2007)

Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem. - Andreas Blass; Yuri Gurevich; Dean Rosenzweig; Benjamin Rossman (Log. Methods Comput. Sci., 2007)

On the constant-depth complexity of k-clique. - Benjamin Rossman (STOC, 2008)

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. - Anuj Dawar; David Richerby; Benjamin Rossman (Ann. Pure Appl. Log., 2008)

Homomorphism preservation theorems. - Benjamin Rossman (J. ACM, 2008)

Combining Ehrenfeucht-Fraïssé Games. - Benjamin Rossman (LICS, 2009)

Ehrenfeucht-Fraïssé Games on Random Structures. - Benjamin Rossman (WoLLIC, 2009)

An optimal decomposition algorithm for tree edit distance. - Erik D. Demaine; Shay Mozes; Benjamin Rossman; Oren Weimann (ACM Trans. Algorithms, 2009)

Choiceless Computation and Symmetry. - Benjamin Rossman (Fields of Logic and Computation, 2010)

10061 Abstracts Collection - Circuits, Logic, and Games. - Benjamin Rossman; Thomas Schwentick; Denis Thérien; Heribert Vollmer (Circuits, Logic, and Games, 2010)

10061 Executive Summary - Circuits, Logic, and Games. - Benjamin Rossman; Thomas Schwentick; Denis Thérien; Heribert Vollmer (Circuits, Logic, and Games, 2010)

Average-case complexity of detecting cliques. - Benjamin Rossman (2010)

The homomorphism domination exponent. - Swastik Kopparty; Benjamin Rossman (Eur. J. Comb., 2011)

A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs. - Benjamin Rossman (WoLLIC, 2012)

Query Complexity and Error Tolerance of Witness Finding Algorithms. - Akinori Kawachi; Benjamin Rossman; Osamu Watanabe 001 (Electron. Colloquium Comput. Complex., 2012)

Formulas vs. Circuits for Small Distance Connectivity. - Benjamin Rossman (Electron. Colloquium Comput. Complex., 2013)

On the AC0 Complexity of Subgraph Isomorphism. - Yuan Li; Alexander A. Razborov; Benjamin Rossman (FOCS, 2014)

The Monotone Complexity of k-Clique on Random Graphs. - Benjamin Rossman (SIAM J. Comput., 2014)

Correlation Bounds Against Monotone NC^1. - Benjamin Rossman (CCC, 2015)

An average-case depth hierarchy theorem for Boolean circuits. - Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (Electron. Colloquium Comput. Complex., 2015)

Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. - Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (SIGACT News, 2015)

Poly-logarithmic Frege depth lower bounds via an expander switching lemma. - Toniann Pitassi; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

Exponential Lower Bounds for Monotone Span Programs. - Stephen A. Cook; Toniann Pitassi; Robert Robere; Benjamin Rossman (Electron. Colloquium Comput. Complex., 2016)

An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. - Benjamin Rossman (Electron. Colloquium Comput. Complex., 2016)

Subspace-Invariant AC^0 Formulas. - Benjamin Rossman (ICALP, 2017)

Separation of AC^0[oplus] Formulas and Circuits. - Benjamin Rossman; Srikanth Srinivasan 001 (ICALP, 2017)

Separation of AC0[⊕] Formulas and Circuits. - Benjamin Rossman; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2017)

An Average-Case Depth Hierarchy Theorem for Boolean Circuits. - Johan Håstad; Benjamin Rossman; Rocco A. Servedio; Li-Yang Tan (J. ACM, 2017)

The Query Complexity of Witness Finding. - Akinori Kawachi; Benjamin Rossman; Osamu Watanabe 001 (Theory Comput. Syst., 2017)

On the AC0 Complexity of Subgraph Isomorphism. - Yuan Li; Alexander A. Razborov; Benjamin Rossman (SIAM J. Comput., 2017)

A Polynomial Excluded-Minor Approximation of Treedepth. - Ken-ichi Kawarabayashi; Benjamin Rossman (SODA, 2018)

The Average Sensitivity of Bounded-Depth Formulas. - Benjamin Rossman (Comput. Complex., 2018)

Subspace-Invariant AC0 Formulas. - Benjamin Rossman (CoRR, 2018)

Formulas versus Circuits for Small Distance Connectivity. - Benjamin Rossman (SIAM J. Comput., 2018)

Criticality of Regular Formulas. - Benjamin Rossman (CCC, 2019)

Thresholds in the Lattice of Subspaces of (Fq)n. - Benjamin Rossman (CoRR, 2019)

Subspace-Invariant AC00^0 Formulas. - Benjamin Rossman (Log. Methods Comput. Sci., 2019)

Thresholds in the Lattice of Subspaces of $ mathbb {F}_q^n$. - Benjamin Rossman (LATIN, 2020)

Monotone Circuit Lower Bounds from Robust Sunflowers. - Bruno Pasqualotto Cavalar; Mrinal Kumar 001; Benjamin Rossman (Electron. Colloquium Comput. Complex., 2020)

Shrinkage of Decision Lists and DNF Formulas. - Benjamin Rossman (Electron. Colloquium Comput. Complex., 2020)

Symmetric Formulas for Products of Permutations. - William He; Benjamin Rossman (ITCS, 2023)

Tree-Depth and the Formula Complexity of Subgraph Isomorphism. - Deepanshu Kush; Benjamin Rossman (SIAM J. Comput., 2023)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. - Benjamin Rossman (Electron. Colloquium Comput. Complex., 2024)

Equi-Rank Homomorphism Preservation Theorem on Finite Structures. - Benjamin Rossman (CSL, 2025)