Next

__
TR20-041
| 29th March 2020
__

Mrinal Kumar, Ben Lee Volk#### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 1

__
TR20-040
| 25th March 2020
__

Andrei Krokhin, Jakub OprÅ¡al, Marcin Wrochna, Stanislav Zivny#### Topology and adjunction in promise constraint satisfaction

__
TR20-039
| 25th March 2020
__

Pranjal Dutta, Nitin Saxena, Thomas Thierauf#### Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT

Next

Mrinal Kumar, Ben Lee Volk

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>

Andrei Krokhin, Jakub OprÅ¡al, Marcin Wrochna, Stanislav Zivny

The approximate graph colouring problem concerns colouring a $k$-colourable

graph with $c$ colours, where $c\geq k$. This problem naturally generalises

to promise graph homomorphism and further to promise constraint satisfaction

problems. Complexity analysis of all these problems is notoriously difficult.

In this paper, we introduce ...
more >>>

Pranjal Dutta, Nitin Saxena, Thomas Thierauf

We consider the univariate polynomial $f_d:=(x+1)^d$ when represented as a sum of constant-powers of univariate polynomials. We define a natural measure for the model, the support-union, and conjecture that it is $\Omega(d)$ for $f_d$.

We show a stunning connection of the conjecture to the two main problems in algebraic ... more >>>

Next