Anthony Ostuni

collaborators

8 papers

cs.CC2026

On the Advantage of Adaptivity for Sampling with Cell Probes

Farzan Byramji, Daniel M. Kane, Jackson Morris +1

We construct an explicit distribution $D$ over ${0, 1}^{N}$ that exhibits an essentially optimal separation between adaptive and non-adaptive cell-probe sampling. The distr…

cs.CC2026

Hard-to-Sample Distributions from Robust Extractors

Farzan Byramji, Daniel M. Kane, Jackson Morris +1

We provide a unified method for constructing explicit distributions which are difficult for restricted models of computation to generate. Our constructions are based on a new notio…

cs.CC2025

Symmetric Distributions from Shallow Circuits

Daniel M. Kane, Anthony Ostuni, Kewen Wu

We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f : {0, 1}^{m} \to {0, 1}^{n}$ be a Boolean fu…

cs.CC2025

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

Daniel Grier, Daniel M. Kane, Jackson Morris +2

We construct a family of distributions ${D_{n}}_{n}$ with $D_{n}$ over ${0, 1}^{n}$ and a family of depth- $7$ quantum circuits ${C_{n}}_{n}$ such that $D_{n}$ …

math.CO2025

Strong Bounds for Skew-Corner-Free Sets

Michael Jaber, Shachar Lovett, Anthony Ostuni

Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of $[n] \times [n]$ could be without containing a skew-corner: three points…

math.CO2025

Quasipolynomial bounds for the corners theorem

Michael Jaber, Yang P. Liu, Shachar Lovett +2

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G ∖ {0}$ such that $(x, y)$ …