Benjamin Rossman

ORCID

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 39

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

SIAM J. Comput.

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Benjamin Rossman
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. Electron. Colloquium Comput. Complex. (2024)
Benjamin Rossman
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication. STOC (2024)
Benjamin Rossman
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. CoRR (2024)
William He, Benjamin Rossman
Symmetric Formulas for Products of Permutations. ITCS (2023)
Deepanshu Kush, Benjamin Rossman
Tree-Depth and the Formula Complexity of Subgraph Isomorphism. SIAM J. Comput. 52 (1) (2023)
William He, Benjamin Rossman
Symmetric Formulas for Products of Permutations. CoRR (2022)
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Monotone Circuit Lower Bounds from Robust Sunflowers. Algorithmica 84 (12) (2022)
Benjamin Rossman
Shrinkage of Decision Lists and DNF Formulas. ITCS (2021)
Benjamin Rossman
Shrinkage of Decision Lists and DNF Formulas. CoRR (2020)
Benjamin Rossman
Shrinkage of Decision Lists and DNF Formulas. Electron. Colloquium Comput. Complex. 27 (2020)
Deepanshu Kush, Benjamin Rossman
Tree-depth and the Formula Complexity of Subgraph Isomorphism. Electron. Colloquium Comput. Complex. 27 (2020)
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Monotone Circuit Lower Bounds from Robust Sunflowers. Electron. Colloquium Comput. Complex. 27 (2020)
Benjamin Rossman
Thresholds in the Lattice of Subspaces of $\mathbb {F}_q^n$. LATIN (2020)
Deepanshu Kush, Benjamin Rossman
Tree-depth and the Formula Complexity of Subgraph Isomorphism. CoRR (2020)
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Monotone Circuit Lower Bounds from Robust Sunflowers. CoRR (2020)
Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman
Monotone Circuit Lower Bounds from Robust Sunflowers. LATIN (2020)
Deepanshu Kush, Benjamin Rossman
Tree-depth and the Formula Complexity of Subgraph Isomorphism. FOCS (2020)
Benjamin Rossman
. CoRR (2019)
Benjamin Rossman, Srikanth Srinivasan
[⊕] Formulas and Circuits. Theory Comput. 15 (2019)
Benjamin Rossman
Subspace-Invariant AC00^0 Formulas. Log. Methods Comput. Sci. 15 (3) (2019)
Benjamin Rossman
Criticality of Regular Formulas. Computational Complexity Conference (2019)
Benjamin Rossman
Formulas versus Circuits for Small Distance Connectivity. SIAM J. Comput. 47 (5) (2018)
Ken-ichi Kawarabayashi, Benjamin Rossman
A Polynomial Excluded-Minor Approximation of Treedepth. SODA (2018)
Benjamin Rossman
The Average Sensitivity of Bounded-Depth Formulas. Comput. Complex. 27 (2) (2018)
Benjamin Rossman
Formulas. CoRR (2018)
Benjamin Rossman
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. ITCS (2017)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
The Query Complexity of Witness Finding. Theory Comput. Syst. 61 (2) (2017)
Benjamin Rossman, Srikanth Srinivasan
Separation of AC$^0[\oplus]$ Formulas and Circuits. CoRR (2017)
Benjamin Rossman, Srikanth Srinivasan
Separation of AC^0[oplus] Formulas and Circuits. ICALP (2017)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
Complexity of Subgraph Isomorphism. SIAM J. Comput. 46 (3) (2017)
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64 (5) (2017)
Benjamin Rossman
Subspace-Invariant AC^0 Formulas. ICALP (2017)
Benjamin Rossman, Srikanth Srinivasan
[⊕] Formulas and Circuits. Electron. Colloquium Comput. Complex. 24 (2017)
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman
Exponential Lower Bounds for Monotone Span Programs. Electron. Colloquium Comput. Complex. 23 (2016)
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC (2016)
Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook
Exponential Lower Bounds for Monotone Span Programs. FOCS (2016)
Benjamin Rossman
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. CoRR (2016)
Benjamin Rossman
An improved homomorphism preservation theorem from lower bounds in circuit complexity. ACM SIGLOG News 3 (4) (2016)
Benjamin Rossman
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An average-case depth hierarchy theorem for Boolean circuits. CoRR (2015)
Benjamin Rossman
The Average Sensitivity of Bounded-Depth Formulas. CoRR (2015)
Benjamin Rossman
Correlation Bounds Against Monotone NC^1. Computational Complexity Conference (2015)
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. SIGACT News 46 (4) (2015)
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An average-case depth hierarchy theorem for Boolean circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. FOCS (2015)
Benjamin Rossman
The Average Sensitivity of Bounded-Depth Formulas. Electron. Colloquium Comput. Complex. 22 (2015)
Benjamin Rossman
The Average Sensitivity of Bounded-Depth Formulas. FOCS (2015)
Benjamin Rossman
The Monotone Complexity of k-Clique on Random Graphs. SIAM J. Comput. 43 (1) (2014)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
Complexity of Subgraph Isomorphism. Electron. Colloquium Comput. Complex. 21 (2014)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
The Query Complexity of Witness Finding. CSR (2014)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
On the AC0 Complexity of Subgraph Isomorphism. FOCS (2014)
Benjamin Rossman
Formulas vs. circuits for small distance connectivity. STOC (2014)
Benjamin Rossman
Formulas vs. Circuits for Small Distance Connectivity. CoRR (2013)
Benjamin Rossman
Formulas vs. Circuits for Small Distance Connectivity. Electron. Colloquium Comput. Complex. 20 (2013)
Benjamin Rossman
A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs. WoLLIC (2012)
Akinori Kawachi, Benjamin Rossman, Osamu Watanabe
Query Complexity and Error Tolerance of Witness Finding Algorithms. Electron. Colloquium Comput. Complex. 19 (2012)
Swastik Kopparty, Benjamin Rossman
The homomorphism domination exponent. Eur. J. Comb. 32 (7) (2011)
Benjamin Rossman, Thomas Schwentick, Denis Thérien, Heribert Vollmer
10061 Executive Summary - Circuits, Logic, and Games. Circuits, Logic, and Games (2010)
Benjamin Rossman
Choiceless Computation and Symmetry. Fields of Logic and Computation (2010)
Benjamin Rossman
The Monotone Complexity of k-clique on Random Graphs. FOCS (2010)
Benjamin Rossman, Thomas Schwentick, Denis Thérien, Heribert Vollmer
10061 Abstracts Collection - Circuits, Logic, and Games. Circuits, Logic, and Games (2010)
Benjamin Rossman
Ehrenfeucht-Fraïssé Games on Random Structures. WoLLIC (2009)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms 6 (1) (2009)
Benjamin Rossman
Combining Ehrenfeucht-Fraïssé Games. LICS (2009)
Benjamin Rossman
On the constant-depth complexity of k-clique. STOC (2008)
Benjamin Rossman
Homomorphism preservation theorems. J. ACM 55 (3) (2008)
Anuj Dawar, David Richerby, Benjamin Rossman
Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Ann. Pure Appl. Log. 152 (1-3) (2008)
Andreas Blass, Yuri Gurevich, Dean Rosenzweig, Benjamin Rossman
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem. Log. Methods Comput. Sci. 3 (4) (2007)
Andreas Blass, Yuri Gurevich, Dean Rosenzweig, Benjamin Rossman
Interactive Small-Step Algorithms I: Axiomatization CoRR (2007)
Andreas Blass, Yuri Gurevich, Dean Rosenzweig, Benjamin Rossman
Interactive Small-Step Algorithms I: Axiomatization. Log. Methods Comput. Sci. 3 (4) (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
An Optimal Decomposition Algorithm for Tree Edit Distance. ICALP (2007)
Andreas Blass, Yuri Gurevich, Dean Rosenzweig, Benjamin Rossman
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem CoRR (2007)
Benjamin Rossman
Successor-invariant first-order logic on finite structures. J. Symb. Log. 72 (2) (2007)
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann
An O(n^3)-Time Algorithm for Tree Edit Distance CoRR (2006)
Anuj Dawar, David Richerby, Benjamin Rossman
Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract). Electron. Notes Theor. Comput. Sci. 143 (2006)
Benjamin Rossman
Existential Positive Types and Preservation under Homomorphisisms. LICS (2005)
Yuri Gurevich, Benjamin Rossman, Wolfram Schulte
Semantic essence of AsmL. Theor. Comput. Sci. 343 (3) (2005)
Andreas Blass, Benjamin Rossman
Explicit Graphs with Extension Properties. Bull. EATCS 86 (2005)
Yuri Gurevich, Benjamin Rossman, Wolfram Schulte
Semantic Essence of AsmL. FMCO (2003)
Benjamin Rossman
Successor-Invariance in the Finite. LICS (2003)

Benjamin Rossman.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Benjamin Rossman