# School of Mathematics

## Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for $m\geq n$, the rank of any $(q,k,t)$-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least $n - (qtn/2k)^2$ .

Using this result we derive the following applications:

## Invariants of Graphs, Their Associated Clique Complexes and Right-Angled Coxeter Groups

Associated to any simplicial graph there is a right-angled Coxeter group. Invariants of the Coxeter group such as its growth series or its weighted L^2 Betti numbers can be computed from the graph's clique complex (i.e., its flag complex).

## A Unified Framework for Testing Linear-Invariant Properties

In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties.

## Some aspects of the p-ADIC local Langlands correspondence for $GL(2,Q_p)$

## 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.

## 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$.

## 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.