Seminars Sorted by Series

Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems...

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive nonuniform circuit lower bounds. In this talk, I will show in depth how the nonexistence of nontrivial circuit-analysis algorithms can also imply...

We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within...

Two vector spaces of the same finite dimension are related by a linear isomorphism; that’s how the dimension is defined. Similarly, two simple subalgebras over complex numbers that are closed under conjugate transpose are related by a unitary...

Over the past 50 years, cryptographers have constructed a number of surprising and important primitives like public-key encryption, which allows strangers to communicate privately even if eavesdroppers hear everything they say. However, there are...

In the theory of error-correcting codes, list decoding allows a decoder to output a list of candidates when attempting to remove noise from a corrupted input. The constructions and algorithms for such list decodable codes has had numerous...

The regularity lemma says that every discrete object can be partitioned into a small number of random-like subobjects. But how small is small? And can we make small smaller if we assume that our given object is simple? And what does it mean for a...

Why is it so hard to prove P != NP, or even to prove super-linear circuit lower bounds? While we often blame a lack of combinatorial ingenuity, the bottleneck might be more fundamental: the logical strength of our mathematical tools.

This series of...

Why is it so hard to prove P != NP, or even to prove super-linear circuit lower bounds? While we often blame a lack of combinatorial ingenuity, the bottleneck might be more fundamental: the logical strength of our mathematical tools.

This series of...

I plan to survey the many ways we have today of constructing expanding Cayley graphs of finite groups, and the ideas behind their analysis (some useful beyond that purpose). I want to highlight that despite a comprehensive understanding of achieving...