All reports by Author Ankit Garg:

__
TR20-132
| 7th September 2020
__

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

__
TR19-140
| 7th October 2019
__

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson#### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Revisions: 1

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

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>