Results 331 - 340 of 24699
Deep networks trained with finite step sizes exhibit non-monotonic, oscillatory loss. For full-batch gradient descent this is well charted: the quadratic model puts the stability boundary at twice the inverse step size, and deep neural networks rise to...
This mini course will give an introduction to hyperbolic surfaces. We will start with their basic topology and (hyperbolic) geometry. We will then introduce several random models for surfaces (some of which are directly defined using random graphs). In the end, we will give a taste of the ways in which many results about random surfaces parallel those for random graphs.
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."
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.