Benjamin Rossman

86 papers A* 17A 6B 3C 4Misc 1Journal 49Unranked 4

Year	Rank	Type	Title / 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