Next 
The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has ... more >>>
Weighted pseudorandom generators (wPRGs) were suggested by Braverman, Cohen, and Garg (STOC, 2018) as a relaxation of pseudorandom generator (PRG) used for derandomization.
We present proofs of several observations regarding wPRGs, where some of these observations are well known.
In this paper, we give a one-pass quantum streaming algorithm for Max-$k$SAT that uses $\operatorname{polylog}(n)$ space and achieves a $0.7172$-approximation on instances with $n$ variables. In contrast, prior work by Chou, Golovnev, and Velusamy (FOCS 2020) implies that achieving an approximation ratio better than $\sqrt{2}/2 \approx 0.7071$ for Max-$k$SAT requires ... more >>>
