Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > WILLIAM PIRES:
All reports by Author William Pires:

TR26-312 | 5th November 2026
Clement Canonne, Xi Chen, William Pires, Toniann Pitassi, Rocco Servedio

The Space Complexity of Property Testing

We initiate the study of the space complexity of property testing. We focus on five properties of Boolean functions that have been intensively studied in the property testing literature: monotonicity, symmetry, linearity, being a junta, and being a linear threshold function.

On the upper bounds side, we show --- ... more >>>


TR22-079 | 25th May 2022
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

Lower Bound Methods for Sign-rank and their Limitations

The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>


TR22-058 | 26th April 2022
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Separations in Proof Complexity and TFNP

Revisions: 3

It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Resolution cannot be efficiently simulated by SA when the coefficients are written in unary. We also show that Reversible Resolution (a variant of MaxSAT ... more >>>


TR22-018 | 15th February 2022
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

Further Collapses in TFNP

We show $\text{EOPL}=\text{PLS}\cap\text{PPAD}$. Here the class $\text{EOPL}$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... more >>>


TR21-123 | 25th August 2021
Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

On public-coin zero-error randomized communication complexity

Revisions: 2

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>



ISSN 1433-8092 | Imprint