Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Chattopadhyay, Eshan"'
We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model for which extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ bl
Externí odkaz:
http://arxiv.org/abs/2411.04115
We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our work, all known explicit constructions in the unbalanced set
Externí odkaz:
http://arxiv.org/abs/2409.04549
We prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources [AORSV, EUROCRYPT'20], and adversarial Chor-Goldreich (aCG) source [DMOZ,
Externí odkaz:
http://arxiv.org/abs/2312.15087
We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \tilde{\Omega}(\sqrt{\log n})$. Previously, no constructions were known, even for min
Externí odkaz:
http://arxiv.org/abs/2309.11019
Autor:
Chattopadhyay, Eshan, Liao, Jyun-Jie
In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian pe
Externí odkaz:
http://arxiv.org/abs/2309.04551
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random inp
Externí odkaz:
http://arxiv.org/abs/2205.13725
Autor:
Chattopadhyay, Eshan, Liao, Jyun-Jie
We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mat
Externí odkaz:
http://arxiv.org/abs/2110.12652
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We
Externí odkaz:
http://arxiv.org/abs/2008.01316
Autor:
Chattopadhyay, Eshan, Goodman, Jesse
We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao, Vadhan and Zuckerman (STOC'06), and falls into a line of research init
Externí odkaz:
http://arxiv.org/abs/2007.07772
Autor:
Chattopadhyay, Eshan, Liao, Jyun-Jie
In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a
Externí odkaz:
http://arxiv.org/abs/2002.07208