Next

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

__
TR19-139
| 8th October 2019
__

Irit Dinur, Konstantin Golubev#### Direct sum testing - the general case

__
TR19-138
| 6th October 2019
__

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### On the Probabilistic Degrees of Symmetric Boolean functions

Next

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 >>>Irit Dinur, Konstantin Golubev

A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are ...
more >>>

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

Next