Pseudorandomness in Mathematics and Computer Science Mini-Workshop

Inspired by the theory of good lattice points in numerical integration, Zaremba conjectured in 1972 that for every denominator q, there is some coprime numerator p, such that the continued fraction expansion of p/q has uniformly bounded quotients...

A Monotone Expander is an expander graph which can be decomposed into a union of a constant number of monotone matchings, under some fixed ordering of the vertices. A matching is monotone if every two edges (u,v) and (u',v') in it satisfy u u' -->...

This talk will focus on the complexity of the cubic-residue (and higher-residue) characters over GF(2^n), in the context of both arithmetic circuits and polynomials.

We show that no subexponential-size, constant-depth arithmetic circuit over GF(2)...

I will talk about a joint work with Jean Bourgain that establishes spectral gaps for random walks on SL_n(Z/qZ). Let S be a fixed finite and symmetric subset of SL_n(Z) which generates a Zariski dense subgroup. We show that words of length C log(q)...