Benjamin Rossman
where else to find them
no profile links on file
what they talk about
where they keep going back
- ITCS2 editions2021–2023
on a stage with
- William Heonce
who talks about the same things
- Mark Braverman5 talks
- Runzhou Tao6 talks
- Shay Moran6 talks
- Robert Krauthgamer3 talks
- Yuval Filmus9 talks
- Dor Minzer8 talks
| title | conference | date |
|---|---|---|
| Symmetric Formulas for Products of Permutations | ITCS 2023 | 2023-01-10 |
Proves that the permutation-matrix product decision problem PMM_{k,n} requires size n^{Ω(log k)} for formulas invariant under the shifted-diagonal Sn^{k-1}… | ||
| Shrinkage of Decision Lists and DNF Formulas | ITCS 2021 | 2021-01-06 |
Result gives a concrete shrinkage bound: the expected decision list size under a p‑random restriction is at most M^{α(p)} where α(p) is an explicit function of… | ||
| Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic | Symmetry, Logic, Computation 2016 | 2016-11-07 |
States that colored Subgraph Isomorphism has nearly tight AC0 circuit lower bounds — circuits need n^{Ω(treewidth / log treewidth)} — and AC0 formulas require… | ||
| nothing matches | ||