# Recently Added

## Pseudorandom Generators for $CCO[p]$ and the Fourier Spectrum of Low-Degree Polynomials Over Finite Fields

## Super-uniformity of the typical billiard path (proof included)

I will describe the proof of the following surprising result: the typical billiard paths form the family of the most uniformly distributed curves in the unit square. I will justify this vague claim with a precise statement. As a byproduct, we obtain the counter-intuitive fact that the complexity of the test set is almost irrelevant. The error term is shockingly small, and it does not matter that we test uniformity with a nice set (like a circle or a square), or with an arbitrarily ugly Lebesgue measurable subset of the unit square.

## The Complexity of the Non-commutative Determinant

I will talk about the computational complexity of computing the noncommutative determinant. In contrast to the case of commutative algebras, we know of (virtually) no efficient algorithms to compute the determinant over non-commutative domains. Our results show that the determinant in noncommutative settings can be as hard as the permanent.

## Approximating the Longest Increasing Subsequence in Polylogarithmic Time

Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple $O(n log n)$ algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length $n$.

## Voting Paradoxes and Combinatorics

The early work of Condorcet in the eighteenth century, and that of Arrow and others in the twentieth century, revealed the complex and interesting mathematical problems that arise in the theory of social choice. In this lecture, Noga Alon, Visiting Professor in the School of Mathematics, explains how the simple process of voting leads to strikingly counter-intuitive paradoxes, focusing on several recent intriguing examples.

## STPM - L^p Concentration of Semiclassical Quasimodes

## STPM - Torsion-Freeness of Certain Cohomology Groups of PEL-Type Shimura Varieties

## STPM - Sparce Approximation of PSD Matrices

I will discuss the problem of approximating a given positive semidefinite matrix A , written as a sum of outer products $vv^T$ , by a much shorter weighted sum in the same outer products. I will then mention an application to sparsification of finite undirected graphs.