Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIGN-REPRESENTATION BY POLYNOMIALS:
Reports tagged with sign-representation by polynomials:
TR19-003 | 2nd January 2019
Alexander A. Sherstov, Pei Wu

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

ISSN 1433-8092 | Imprint