Anthony Ostuni

collaborators

4 papers

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

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)$ …

cs.CC2024

Locally Sampleable Uniform Symmetric Distributions

Daniel M. Kane, Anthony Ostuni, Kewen Wu

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f : {0, 1}^{m} \to {0, 1}^{n}$ be a Boolean function where each outp…

math.CO2024

Corners in Quasirandom Groups via Sparse Mixing

Michael Jaber, Shachar Lovett, Anthony Ostuni

We improve the best known upper bounds on the density of corner-free sets over quasirandom groups from inverse poly-logarithmic to quasi-polynomial. We make similarly substantial i…