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 construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot\log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs(ROBPs) of width $3$ and length $n$. For unordered ROBPs, we constructpseudorandom generators with seed length $\tilde{O}(\log(n) \cdot\mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandomgenerators fooling width $3$ ROBPs since the work of Nisan [Combinatorica,1992].  Our constructions are based on the `iterated milder restrictions' approach ofGopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigdersonframework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at thelast step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unorderedcase, we combine iterated milder restrictions with the generator ofChattopadhyay et al. [CCC, 2018].  Two conceptual ideas that play an important role in our analysis are: (1) Arelabeling technique allowing us to analyze a relabeled version of the givenbranching program, which turns out to be much easier. (2) Treating the numberof colliding layers in a branching program as a progress measure and showingthat it reduces significantly under pseudorandom restrictions.  In addition, we achieve nearly optimal seed-length$\tilde{O}(\log(n/\epsilon))$ for the classes of: (1) read-once polynomials on$n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$(generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length$n$ having a layer of width $2$ in every consecutive $\mathrm{poly}\log(n)$layers.

Pseudorandom Generators for Width-3 Branching Programs