Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Anthony Ostuni:

TR24-031 | 22nd February 2024
Daniel Kane, Anthony Ostuni, Kewen Wu

Locality Bounds for Sampling Hamming Slices

Revisions: 1

Spurred by the influential work of Viola (Journal of Computing 2012), the past decade has witnessed an active line of research into the complexity of (approximately) sampling distributions, in contrast to the traditional focus on the complexity of computing functions.

We build upon and make explicit earlier implicit results of ... more >>>

TR23-203 | 15th December 2023
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

Refuting approaches to the log-rank conjecture for XOR functions

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of ... more >>>

ISSN 1433-8092 | Imprint