School of Mathematics
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.
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.
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).
I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms.
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.