Benjamin Rossman

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