1. Harald Helfgott
I like solvable groups, in particular the following one, which models the general solvable case,
where is a prime field.
Proposition 1 (special case of Gill, Helfgott 2010) Let . Then either
with some absolute , or is contained in a maximal torus, or is covered by right cosets of , or
Problem:
- Let generate , with . Show that
- How do we navigate. I.e., how does one find a short path from e-any element to identity ?
We have the diameter bound for , but we do not know how to navigate deterministically. There is a randomized algorithm.
[Bukh, Helfgott, Kassabov] have some partial result, but we are close to give up now.
2. James Lee
Dvoretzky theorem. Revived in Szarek’s ICM address.
Theorem 2 Let be an -dimensional Banach space. There is -dimensional linear subspace on which the induced norm is nearly Euclidean, with tending to infinity with .
Vitaly Milman gave a randomized proof, he was later imitated a lot in Banach space geometry.
Definition 3
More or less simultaneously,
- Figiel, Lindenstrauss, Milman achieved if .
- Kasin achieved if .
This has applications to compressed sensing, quantum computing.
Definition 4 Say that is -spread if for all ,
for all sets of coordinates of size .
Analogy with linear codes.
Proposition 5 Every subspace is -spread.
To get good subspaces , consider kernel a random matrix.
Question: Derandomize ?
Known: [Guruswami, Lee, Wigderson 2008]: random bits. [Guruswami, Lee, Razborov 2008]: .
Let be a random -regular graph, a random subspace of dimension . Define
(compare Lubotzky’s talk).
Question: Is bounded ?
In many cases (compressed sensing, dimension reduction,…), the search for deterministic algorithms has led to better algorithms.
3. Anup Rao
The tree code, invented by Schulman.
Start with binary tree of depth . Label edges with a constant size alphabet . We want that for every vertices and , Hamming distance of the words read along the two legs of the shortest path between and on tree is . This gives a code of distance .
Such a code is more powerful than error-correcting codes. It is useful in communication. Indeed,
We want an explicit construction of such a code. One approach is to use polynomials. Let be a degree polynomial on . We want that for every polynomial of degree on , , the product has nonzero coefficients in terms of degree . The labelling is reconstructed from the coefficient of for various polynomials .
Question: Can one find such a polynomial ? And an algorithm that computes it in polynomial time ?
4. Parikshit Gopalan
Construction of pseudorandom generators for half spaces.
[Meka-Zuckerman] use seed size .
Question: Improve this.
Panigrahy proposed the following approach. Instead on the hypercube, work on the sphere. Put repelling point charges on the -sphere. Compute a stable equilibrium. Is this -uniformly distributed ? Want number of points be .
5. Zeev Dvir
Explicit construction of unbalanced bipartite expanders. Fix . Vertex sets and , with left degree , such that for every subset , , and edge expansion .
There exists a (sum-product) construction, but is does not reduce right vertex size that much.
6. Alex Lubotzky
Gromov: is every hyperbolic group residually finite ?
I explain a strategy that relies on expansion for finite simple groups.
Useful facts about hyperbolic groups:
- Adding long relations do not kill the group: it stays infinite and hyperbolic.
- There exist hyperbolic groups which have Kazhdan’s property (T) and whose finite simple quotients must have ranks tending to infinity.
Given a family of finite simple groups with generators , and ranks tending to infinity. Assume that it is a family of expanders.
Question: Prove that there exist finitely many very large words such that for every , there exists such .
This would solve Gromov’s question. Indeed, adding relators to a group having property (2) kills every finite simple non abelian quotient. Abelian quotients are easy to handle.
Comment by Breuillard: There is a similar problem for alternating group .