Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > XUANGUI HUANG:
All reports by Author Xuangui Huang:

TR19-085 | 7th June 2019
Xuangui Huang, Emanuele Viola

Approximate Degree-Weight and Indistinguishability

Revisions: 1

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps ... more >>>




ISSN 1433-8092 | Imprint