All reports by Author Ran Tao:

__
TR22-079
| 25th May 2022
__

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao#### Lower Bound Methods for Sign-rank and their Limitations

__
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

__
TR22-018
| 15th February 2022
__

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao#### Further Collapses in TFNP

__
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

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

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 >>>

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

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 >>>

Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao

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 >>>

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

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

more >>>