English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study correlation bounds and pseudorandom generators for depth-twocircuits that consist of a $\mathsf{SYM}$-gate (computing an arbitrarysymmetric function) or $\mathsf{THR}$-gate (computing an arbitrary linearthreshold function) that is fed by $S$ $\mathsf{AND}$ gates. Such circuits wereconsidered in early influential work on unconditional derandomization of Luby,Veli\v{c}kovi\'c, and Wigderson [LVW93], who gave the first non-trivial PRGwith seed length $2^{O(\sqrt{\log(S/\varepsilon)})}$ that $\varepsilon$-foolsthese circuits.  In this work we obtain the first strict improvement of [LVW93]'s seed length:we construct a PRG that $\varepsilon$-fools size-$S$$\{\mathsf{SYM},\mathsf{THR}\} \circ\mathsf{AND}$ circuits over $\{0,1\}^n$with seed length \[ 2^{O(\sqrt{\log S })} + \mathrm{polylog}(1/\varepsilon), \]an exponential (and near-optimal) improvement of the $\varepsilon$-dependenceof [LVW93]. The above PRG is actually a special case of a more general PRGwhich we establish for constant-depth circuits containing multiple$\mathsf{SYM}$ or $\mathsf{THR}$ gates, including as a special case$\{\mathsf{SYM},\mathsf{THR}\} \circ \mathsf{AC^0}$ circuits. These moregeneral results strengthen previous results of Viola [Vio06] and essentiallystrengthen more recent results of Lovett and Srinivasan [LS11].  Our improved PRGs follow from improved correlation bounds, which aretransformed into PRGs via the Nisan--Wigderson "hardness versus randomness"paradigm [NW94]. The key to our improved correlation bounds is the use of arecent powerful \emph{multi-switching} lemma due to H{\aa}stad [H{\aa}s14].

Luby--Veli\v{c}kovi\'c--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits