Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multilinear polynomial:
TR15-067 | 21st April 2015
Pavel Hrubes

On hardness of multilinearization, and VNP completeness in characteristics two

For 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, ... more >>>

TR18-081 | 20th April 2018
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

ISSN 1433-8092 | Imprint