All reports by Author Visu Makam:

__
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

__
TR19-114
| 2nd September 2019
__

Visu Makam, Avi Wigderson#### Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)

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 >>>Visu Makam, Avi Wigderson

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: ${\rm SING}_{n,m}$, consisting of all $m$-tuples of $n\times n$ complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in ${\rm SING}_{n,m}$ will imply super-polynomial circuit lower bounds, ... more >>>