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

A central question in derandomization is whether randomized logspace (RL)equals deterministic logspace (L). To show that RL=L, it suffices to constructexplicit pseudorandom generators (PRGs) that fool polynomial-size read-once(oblivious) branching programs (roBPs). Starting with the work of Nisan,pseudorandom generators with seed-length $O(\log^2 n)$ were constructed.Unfortunately, improving on this seed-length in general has proven challengingand seems to require new ideas.  A recent line of inquiry has suggested focusing on a particular limitation ofthe existing PRGs, which is that they only fool roBPs when the variables areread in a particular known order, such as $x_1<\cdots<x_n$. In comparison,existentially one can obtain logarithmic seed-length for fooling the set ofpolynomial-size roBPs that read the variables under any fixed unknownpermutation $x_{\pi(1)}<\cdots<x_{\pi(n)}$. While recent works have establishednovel PRGs in this setting for subclasses of roBPs, there were no known$n^{o(1)}$ seed-length explicit PRGs for general polynomial-size roBPs in thissetting.  In this work, we follow the "bounded independence plus noise" paradigm ofHaramaty, Lee and Viola, and give an improved analysis in the general roBPunknown-order setting. With this analysis we obtain an explicit PRG withseed-length $O(\log^3 n)$ for polynomial-size roBPs reading their bits in anunknown order. Plugging in a recent Fourier tail bound of Chattopadhyay,Hatami, Reingold, and Tal, we can obtain a $\widetilde{O}(\log^2 n)$seed-length when the roBP is of constant width.

Pseudorandom Generators for Read-Once Branching Programs, in any Order