School of Mathematics
2013 Marston Morse Lectures
Sensitivity Versus Block Sensitivity, I
There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this conjecture, and its connection with various combinatorial problems.
Random Matrices, Dimensionality Reduction, and Faster Numerical Linear Algebra Algorithms
fundamental theorem in linear algebra is that any real n x d matrix has a singular value decomposition (SVD). Several important numerical linear algebra problems can be solved efficiently once the SVD of an input matrix is computed: e.g.
Intractability in Algorithmic Game Theory
We discuss three areas of algorithmic game theory that have grappled with intractability. The first is the complexity of computing game-theoretic equilibria, like Nash equilibria. There is an urgent need for new ideas on this topic, to enable meaningful research in the face of computational hardness results. The other domains concern the design and analysis of mechanisms (such as auctions).
"Setoids, e-Categories, and Exact Completions"
Workshop on Topology: Identifying Order in Complex Systems
Cohomology in Homotopy Type Theory
Derandomization of Probabilistic Logspace (The Nisan Variations)
I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms.
Quasirandom Hypergraphs
Since the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs over 20 years ago, there has been a lot of effort by many researchers to extend the theory to hypergraphs. I will present some of this history, and then describe our recent results that provide such a generalization and unify much of the previous work. One key new aspect in the theory is a systematic study of hypergraph eigenvalues.