ECCC-Report TR15-067https://eccc.weizmann.ac.il/report/2015/067Comments and Revisions published for TR15-067en-usTue, 21 Apr 2015 14:16:14 +0300
Paper TR15-067
| On hardness of multilinearization, and VNP completeness in characteristics two |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2015/067For a boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$, let $\hat{f}$ be the unique multilinear polynomial such that $f(x)=\hat{f}(x)$ holds for every $x\in \{0,1\}^n$. We show that, assuming $\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable $f$ such that $\hat{f}$ requires super-polynomial arithmetic circuits. In fact, this $f$ can be taken as a monotone 2-CNF, or a product of affine functions.
This holds over any field. In order to prove the results in characteristics two, we design new VNP-complete families in this characteristics. This includes the polynomial $\hbox{EC}_n$ counting edge covers in a graph, and the polynomial $\hbox{mclique}_n$ counting cliques in a graph with deleted perfect matching. They both correspond to polynomial-time decidable problems, a phenomenon previously encountered only in characteristics $\not=2$. Tue, 21 Apr 2015 14:16:14 +0300https://eccc.weizmann.ac.il/report/2015/067