Results 441 - 450 of 24735

We will explore the pseudorandomness toolkit: the basic objects and techniques used to construct pseudorandom generators and prove various other derandomization results. Topics will include bounded independence, small-bias spaces, randomness extractors, expander graphs, and random restrictions. We will present some of the key constructions and their applications, and see how these ingredients fit together in the main challenges in pseudorandomness. Time permitting, we will also give some ideas being more advanced results, and discuss some open problems.

Expanding graphs are ubiquitous throughout mathematics and computer science and have cemented themselves a fundamental objects of interest. This minicourse joint with Sidhanth Mohanty will give a powerful framework from group theory (Kazhdan's property (T)) and operator algebras to construct explicit expanders in a wide variety of settings.

This talk will present Ozawa's remarkable sum of squares certificate for property (T), which subsumes Żuk's criterion presented previously. We then prove Ozawa's theorem showing that property (T) is in fact equivalent to possessing a sum of squares certificate. This gives a semidefinite programming approach towards establishing property (T), yielding computer based proofs of expansion. Time permitting, we will discuss (T) for automophism groups of free groups.

This talk will cover the fundamentals of spectral expander graphs, and the sum-of-squares approach to proving spectral expansion in algebraic constructions. I will attempt to give a mostly self-contained proof of expansion for a simple algebraic construction.