All reports by Author Suhail Sherif:

__
TR20-132
| 7th September 2020
__

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

__
TR18-176
| 26th October 2018
__

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif#### The Log-Approximate-Rank Conjecture is False

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>