All reports by Author Xuangui Huang:

__
TR21-137
| 14th September 2021
__

Xuangui Huang, Peter Ivanov, Emanuele Viola#### Affine extractors and AC0-Parity

Revisions: 1

__
TR20-193
| 29th December 2020
__

Xuangui Huang, Emanuele Viola#### Average-case rigidity lower bounds

Revisions: 1

__
TR19-085
| 7th June 2019
__

Xuangui Huang, Emanuele Viola#### Approximate Degree-Weight and Indistinguishability

Revisions: 2

Xuangui Huang, Peter Ivanov, Emanuele Viola

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. ... more >>>

Xuangui Huang, Emanuele Viola

It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently ... more >>>

Xuangui Huang, Emanuele Viola

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 >>>