Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INVARIANT THEORY:
Reports tagged with Invariant theory:
TR18-151 | 29th August 2018
Ankit Garg, Rafael Oliveira

#### Recent progress on scaling algorithms and applications

Scaling problems have a rich and diverse history, and thereby have found numerous
applications in several fields of science and engineering. For instance, the matrix scaling problem
has had applications ranging from theoretical computer science to telephone forecasting,
economics, statistics, optimization, among many other fields. Recently, a generalization of matrix
more >>>

TR19-114 | 2nd September 2019
Visu Makam, Avi Wigderson

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

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

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

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

ISSN 1433-8092 | Imprint