Eigenvalues of a real supersymmetric tensor

In this paper, we define the symmetric hyperdeterminant, eigenvalues and E-eigenvalues of a real supersymmetric tensor. We show that eigenvalues are roots of a one-dimensional polynomial, and when the order of the tensor is even, E-eigenvalues are roots of another one-dimensional polynomial. These two one-dimensional polynomials are associated with the symmetric hyperdeterminant. We call them the characteristic polynomial and the E-characteristic polynomial of that supersymmetric tensor. Real eigenvalues (E-eigenvalues) with real eigenvectors (E-eigenvectors) are called H-eigenvalues (Z-eigenvalues). When the order of the supersymmetric tensor is even, H-eigenvalues (Z-eigenvalues) exist and the supersymmetric tensor is positive definite if and only if all of its H-eigenvalues (Z-eigenvalues) are positive. An $m\mathrm{th}$-order $n$-dimensional supersymmetric tensor where $m$ is even has exactly $n{(m-1)}^{n-1}$ eigenvalues, and the number of its E-eigenvalues is strictly less than $n{(m-1)}^{n-1}$ when $m\ge 4$. We show that the product of all the eigenvalues is equal to the value of the symmetric hyperdeterminant, while the sum of all the eigenvalues is equal to the sum of the diagonal elements of that supersymmetric tensor, multiplied by ${(m-1)}^{n-1}$. The $n{(m-1)}^{n-1}$ eigenvalues are distributed in $n$ disks in $C$. The centers and radii of these $n$ disks are the diagonal elements, and the sums of the absolute values of the corresponding off-diagonal elements, of that supersymmetric tensor. On the other hand, E-eigenvalues are invariant under orthogonal transformations.     

Symmetric polynomials over Zm and simultaneous communication protocols

We study the problem of representing symmetric Boolean functions as symmetric polynomials over ${\mathbb{Z}}_m$. We prove an equivalence between representations of Boolean functions by symmetric polynomials and simultaneous communication protocols. We show that computing a function $f$ on 0–1 inputs with a polynomial of degree $d$ modulo $\mathit{pq}$ is equivalent to a two player simultaneous protocol for computing $f$ where one player is given the first $\lceil {\log }_{p}d\rceil$ digits of the weight in base $p$ and the other is given the first $\lceil {\log }_{q}d\rceil$ digits of the weight in base $q$.This equivalence allows us to show degree lower bounds by using techniques from communication complexity. For example, we show lower bounds of $\mathrm{\Omega }(n)$ on symmetric polynomials weakly representing classes of ${\mathrm{Mod}}_r$ and Threshold functions. Previously the best known lower bound for such representations of any function modulo $\mathit{pq}$ was $\mathrm{\Omega }(n^{\frac{1}{2}})$ [D.A. Barrington, R. Beigel, S. Rudich, Representing Boolean functions as polynomials modulo composite numbers, Comput. Complexity 4 (1994) 367–382]. The equivalence also allows us to use results from number theory to prove upper bounds for Threshold-$k$ functions. We show that proving bounds on the degree of symmetric polynomials strongly representing the Threshold-$k$ function is equivalent to counting the number of solutions to certain Diophantine equations. We use this to show an upper bound of $O(\mathit{nk}{)}^{\frac{1}{2}+\varepsilon }$ for Threshold-$k$ assuming the abc-conjecture. We show the same bound unconditionally for $k$ constant. Prior to this, non-trivial upper bounds were known only for the OR function [D.A. Barrington, R. Beigel, S. Rudich, Representing Boolean functions as polynomials modulo composite numbers, Comput. Complexity 4 (1994) 367–382]. We show an almost tight lower bound of $\mathrm{\Omega }(\mathit{nk}{)}^{\frac{1}{2}}$, improving the previously known bound of $\mathrm{\Omega }(\max (k,\sqrt{n}))$ [S.-C. Tsai, Lower bounds on representing Boolean functions as polynomials in ${\mathbb{Z}}_m$, SIAM J. Discrete Math. 9 (1996) 55–62].     

Infeasibility of instance compression and succinct PCPs for NP

The OR-SAT problem asks, given Boolean formulae ${?}_1,\dots ,{?}_m$ each of size at most n, whether at least one of the ${?}_i$'s is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et al. (2008) [6] and Harnik and Naor (2006) [20] and has a number of implications. (i) A number of parametric $\mathsf{NP}$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (ii) Satisfiability does not have PCPs of size polynomial in the number of variables unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (iii) An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (iv) (Buhrman–Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.