Benjamin Rossman

According to our database, Benjamin Rossman authored at least 50 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of two.

2024

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication.

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2024

2023

Tree-Depth and the Formula Complexity of Subgraph Isomorphism.

Deepanshu Kush, Benjamin Rossman

SIAM J. Comput., February, 2023

Symmetric Formulas for Products of Permutations.

William He, Benjamin Rossman

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2020

Shrinkage of Decision Lists and DNF Formulas.

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2020

Monotone Circuit Lower Bounds from Robust Sunflowers.

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Electron. Colloquium Comput. Complex., 2020

Thresholds in the Lattice of Subspaces of $\mathbb {F}_q^n$.

Benjamin Rossman

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

2019

Subspace-Invariant AC00^0 Formulas.

Benjamin Rossman

Log. Methods Comput. Sci., 2019

Thresholds in the Lattice of Subspaces of (F_q)ⁿ.

Benjamin Rossman

CoRR, 2019

Criticality of Regular Formulas.

Benjamin Rossman

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Formulas versus Circuits for Small Distance Connectivity.

Benjamin Rossman

SIAM J. Comput., 2018

Subspace-Invariant AC⁰ Formulas.

Benjamin Rossman

CoRR, 2018

The Average Sensitivity of Bounded-Depth Formulas.

Benjamin Rossman

Comput. Complex., 2018

A Polynomial Excluded-Minor Approximation of Treedepth.

Ken-ichi Kawarabayashi, Benjamin Rossman

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

On the AC⁰ Complexity of Subgraph Isomorphism.

Yuan Li, Alexander A. Razborov, Benjamin Rossman

SIAM J. Comput., 2017

The Query Complexity of Witness Finding.

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Theory Comput. Syst., 2017

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.

Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

J. ACM, 2017

Separation of AC⁰[⊕] Formulas and Circuits.

Benjamin Rossman, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2017

Separation of AC^0[oplus] Formulas and Circuits.

Benjamin Rossman, Srikanth Srinivasan

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Subspace-Invariant AC^0 Formulas.

Benjamin Rossman

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity.

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2016

Exponential Lower Bounds for Monotone Span Programs.

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Electron. Colloquium Comput. Complex., 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.

Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

SIGACT News, 2015

An average-case depth hierarchy theorem for Boolean circuits.

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2015

Correlation Bounds Against Monotone NC^1.

Benjamin Rossman

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

The Monotone Complexity of k-Clique on Random Graphs.

Benjamin Rossman

SIAM J. Comput., 2014

On the AC0 Complexity of Subgraph Isomorphism.

Yuan Li, Alexander A. Razborov, Benjamin Rossman

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Formulas vs. Circuits for Small Distance Connectivity.

Benjamin Rossman

Electron. Colloquium Comput. Complex., 2013

2012

Query Complexity and Error Tolerance of Witness Finding Algorithms.

Akinori Kawachi, Benjamin Rossman, Osamu Watanabe

Electron. Colloquium Comput. Complex., 2012

A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs.

Benjamin Rossman

Proceedings of the Logic, Language, Information and Computation, 2012

2011

The homomorphism domination exponent.

Swastik Kopparty, Benjamin Rossman

Eur. J. Comb., 2011

2010

Average-case complexity of detecting cliques.

Benjamin Rossman

PhD thesis, 2010

10061 Executive Summary - Circuits, Logic, and Games.

Benjamin Rossman, Thomas Schwentick, Denis Thérien, Heribert Vollmer

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

10061 Abstracts Collection - Circuits, Logic, and Games.

Benjamin Rossman, Thomas Schwentick, Denis Thérien, Heribert Vollmer

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

Choiceless Computation and Symmetry.

Benjamin Rossman

Proceedings of the Fields of Logic and Computation, 2010

2009

An optimal decomposition algorithm for tree edit distance.

Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann

ACM Trans. Algorithms, 2009

Ehrenfeucht-Fraïssé Games on Random Structures.

Benjamin Rossman

Proceedings of the Logic, 2009

Combining Ehrenfeucht-Fraïssé Games.

Benjamin Rossman

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

2008

Homomorphism preservation theorems.

Benjamin Rossman

J. ACM, 2008

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.

Anuj Dawar, David Richerby, Benjamin Rossman

Ann. Pure Appl. Log., 2008

On the constant-depth complexity of k-clique.

Benjamin Rossman

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

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

Interactive Small-Step Algorithms I: Axiomatization.

Andreas Blass, Yuri Gurevich, Dean Rosenzweig, Benjamin Rossman

Log. Methods Comput. Sci., 2007

Successor-invariant first-order logic on finite structures.

Benjamin Rossman

J. Symb. Log., 2007

2006

An O(n^3)-Time Algorithm for Tree Edit Distance

Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann

CoRR, 2006

2005

Semantic essence of AsmL.

Yuri Gurevich, Benjamin Rossman, Wolfram Schulte

Theor. Comput. Sci., 2005

Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract).

Anuj Dawar, David Richerby, Benjamin Rossman

Proceedings of the 12th Workshop on Logic, Language, Information and Computation, 2005

Explicit Graphs with Extension Properties.

Andreas Blass, Benjamin Rossman

Bull. EATCS, 2005

Existential Positive Types and Preservation under Homomorphisisms.

Benjamin Rossman

Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

2003

Successor-Invariance in the Finite.

Benjamin Rossman

Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003