Benjamin Rossman

Orcid: 0009-0001-0247-5208

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

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023
Symmetric Formulas for Products of Permutations.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022
Monotone Circuit Lower Bounds from Robust Sunflowers.
Algorithmica, 2022

2020
Shrinkage of Decision Lists and DNF Formulas.
Electron. Colloquium Comput. Complex., 2020

Tree-depth and the Formula Complexity of Subgraph Isomorphism.
Electron. Colloquium Comput. Complex., 2020

Thresholds in the Lattice of Subspaces of $\mathbb {F}_q^n$.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

2019
Separation of AC<sup>0</sup>[⊕] Formulas and Circuits.
Theory Comput., 2019

Subspace-Invariant AC00^0 Formulas.
Log. Methods Comput. Sci., 2019

Thresholds in the Lattice of Subspaces of (F<sub>q</sub>)<sup>n</sup>.
CoRR, 2019

Criticality of Regular Formulas.
Proceedings of the 34th Computational Complexity Conference, 2019

2018
Formulas versus Circuits for Small Distance Connectivity.
SIAM J. Comput., 2018

Subspace-Invariant AC<sup>0</sup> Formulas.
CoRR, 2018

The Average Sensitivity of Bounded-Depth Formulas.
Comput. Complex., 2018

A Polynomial Excluded-Minor Approximation of Treedepth.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
The Query Complexity of Witness Finding.
Theory Comput. Syst., 2017

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
J. ACM, 2017

Separation of AC^0[oplus] Formulas and Circuits.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Subspace-Invariant AC^0 Formulas.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
An improved homomorphism preservation theorem from lower bounds in circuit complexity.
ACM SIGLOG News, 2016

Exponential Lower Bounds for Monotone Span Programs.
Electron. Colloquium Comput. Complex., 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
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.
SIGACT News, 2015

An average-case depth hierarchy theorem for Boolean circuits.
Electron. Colloquium Comput. Complex., 2015

Correlation Bounds Against Monotone NC^1.
Proceedings of the 30th Conference on Computational Complexity, 2015

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

On the AC<sup>0</sup> Complexity of Subgraph Isomorphism.
Electron. Colloquium Comput. Complex., 2014

On the AC0 Complexity of Subgraph Isomorphism.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Formulas vs. Circuits for Small Distance Connectivity.
Electron. Colloquium Comput. Complex., 2013

2012
Query Complexity and Error Tolerance of Witness Finding Algorithms.
Electron. Colloquium Comput. Complex., 2012

A Tight Upper Bound on the Number of Variables for Average-Case k-Clique on Ordered Graphs.
Proceedings of the Logic, Language, Information and Computation, 2012

2011
The homomorphism domination exponent.
Eur. J. Comb., 2011

2010
Average-case complexity of detecting cliques.
PhD thesis, 2010

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

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

Choiceless Computation and Symmetry.
Proceedings of the Fields of Logic and Computation, 2010

2009
An optimal decomposition algorithm for tree edit distance.
ACM Trans. Algorithms, 2009

Ehrenfeucht-Fraïssé Games on Random Structures.
Proceedings of the Logic, 2009

Combining Ehrenfeucht-Fraïssé Games.
Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

2008
Homomorphism preservation theorems.
J. ACM, 2008

Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.
Ann. Pure Appl. Log., 2008

On the constant-depth complexity of k-clique.
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.
Log. Methods Comput. Sci., 2007

Interactive Small-Step Algorithms I: Axiomatization.
Log. Methods Comput. Sci., 2007

Successor-invariant first-order logic on finite structures.
J. Symb. Log., 2007

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

2005
Semantic essence of AsmL.
Theor. Comput. Sci., 2005

Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract).
Proceedings of the 12th Workshop on Logic, Language, Information and Computation, 2005

Explicit Graphs with Extension Properties.
Bull. EATCS, 2005

Existential Positive Types and Preservation under Homomorphisisms.
Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

2003
Successor-Invariance in the Finite.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003


  Loading...