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 present an explicit pseudorandom generator for oblivious, read-once,permutation branching programs of constant width that can read their input bitsin any order. The seed length is $O(\log^2 n)$, where $n$ is the length of thebranching program. The previous best seed length known for this model was$n^{1/2+o(1)}$, which follows as a special case of a generator due toImpagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length of$s^{1/2+o(1)}$ for arbitrary branching programs of size $s$). Our techniquesalso give seed length $n^{1/2+o(1)}$ for general oblivious, read-once branchingprograms of width $2^{n^{o(1)}}$, which is incomparable to the results ofImpagliazzo et al.Our pseudorandom generator is similar to the one used byGopalan et al. (FOCS 2012) for read-once CNFs, but the analysis is quitedifferent; ours is based on Fourier analysis of branching programs. Inparticular, we show that an oblivious, read-once, regular branching program ofwidth $w$ has Fourier mass at most $(2w^2)^k$ at level $k$, independent of thelength of the program.

Pseudorandomness for Regular Branching Programs via Fourier Analysis