Benjamin Rossman

activity

20152022

collaborators

Showing cs.CCShow all

5 papers · 1 filter

cs.CC2022

Symmetric Formulas for Products of Permutations

William He, Benjamin Rossman

We study the formula complexity of the word problem $Word_{S_{n}, k} : {0, 1}^{k n^{2}} \to {0, 1}$ : given $n$ -by- $n$ permutation matrices $M_{1}, \dots, M_{k}$ , compute the $(1, 1)$ …

cs.CC2020

Shrinkage of Decision Lists and DNF Formulas

Benjamin Rossman

We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the $p$ -random restriction $R_{p}$ for all values of $p \in [0, 1]$ . For a…

cs.CC2020

Tree-depth and the Formula Complexity of Subgraph Isomorphism

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$ , the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted $SUB (G)$ ) asks, given an $n$ -vertex graph $H$ and a coloring $V(H) \to V(…

cs.CC2017

Separation of AC $^{0} [\oplus]$ Formulas and Circuits

Benjamin Rossman, Srikanth Srinivasan

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $AC^{0} [\oplus]$ basis (unbounded fan-in AND, OR, NOT and…

cs.CC2015

An average-case depth hierarchy theorem for Boolean circuits

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

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of $AND$ , $OR$ , and $NOT$ gates. Our hierarchy theorem says…

Symmetric Formulas for Products of Permutations

Shrinkage of Decision Lists and DNF Formulas

Tree-depth and the Formula Complexity of Subgraph Isomorphism

Separation of AC0[⊕] Formulas and Circuits

An average-case depth hierarchy theorem for Boolean circuits

Separation of AC $^{0} [\oplus]$ Formulas and Circuits