Results 291 - 300 of 24656

The hardness versus randomness paradigm (initiated by Blum, Micali, Yao, Nisan and Wigderson) aims to show that randomized complexity classes can be derandomized assuming that certain complexity theoretic hardness assumptions hold. The key concept in this research is that of a pseudorandom generator, which stretches a short seed of random bits into a long string of pseudorandom bits that cannot be distinguished from uniform bits by any efficient algorithm. In the talk I will survey classical constructions of pseudorandom generators based on hardness assumptions, as well as implications of these constructions. I will also try to broadly survey some of the more recent work in this area.

Last week, we saw the basics of local-spectral HDX, the local-to-global method, high order random walks, and constructions. In these two lectures, we focus on a second interpretation of (local-spectral) HDX as a theory of strongly``pseudo-independent’’ distributions that mimic many well-loved properties of independent variables such as concentration of measure (Chernoff bounds), Fourier analysis, and computational hardness amplification.

In the first lecture we will review the basics of local-spectral expansion, introduce partite HDX and the notion of $\lambda$-products, prove the high-dimensional expander-mixing lemma, and see how it implies a basic Chernoff bound for HDX. In the second lecture, we will focus on the theory of (derandomized) agreement testing, one of the first major applications of high dimensional expanders in computer science and a core component in modern PCP constructions.

We present an introduction to the "L vs. BPL" problem, which asks whether randomness is ever necessary for space-efficient computation. We highlight four approaches to the problem: the "INW approach," the "Nisan approach," the "iterated restrictions approach," and the "inverse Laplacian approach."

Minicourse on quantum ergodicity, mostly on graphs, with some extensions and questions on manifolds.