Results 341 - 350 of 24711
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.