Pseudorandomness in Mathematics and Computer Science Mini-Workshop
In math, one often studies random aspects of deterministic systems and structures. In CS, one often tries to efficiently create structures and systems with specific random-like properties. Recent work has shown many connections between these two approaches through the concept of "pseudorandomness". This workshop highlights these connections, aimed at a joint audience of mathematicians and computer scientists.
Workshop Homepage: http://www.math.ias.edu/pseudo-workshop/2011
Agenda & Abstracts: http://www.math.ias.edu/files/seminars/PseudorandomnessMiniWkshp.pdf
Related Content
Random Walks in Linear Groups
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) are almost uniformly distributed among congruence classes modulo q. Unlike in previous results, q is arbitrary and not restricted to any special subset of the integers.
![[file]](http://video.ias.edu/sites/all/modules/webfm/image/icon/f.gif "Download Hi-Res"){kind=icon} Hi-Res | 370.88 MB |
| Lo-Res | 213.12 MB |
Watch OnlineThe Correlation of Multiplicative Characters with Polynomials over Finite Fields
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) can correctly compute the cubic-residue character for more than 1/3 + o(1) fraction of the elements of GF(2^n). The key ingredient in the proof is an adaptation of the Razborov-Smolensky method for circuit lower bounds to setting of univariate polynomials over GF(2^n) .
| Hi-Res | 358 MB |
| Lo-Res | 184.74 MB |
The Polynomial Method and Applications From Finite Field Kakeya to Distinct Distances
| Hi-Res | 357.49 MB |
| Lo-Res | 189.05 MB |
Monotone Expanders -- Constructions and Applications
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' --> v < v'. It is not clear a priori if monotone expanders exist or not. This is partially due to the fact that the natural application of the probabilistic method does not work in this special case.
| Hi-Res | 329.68 MB |
| Lo-Res | 184.92 MB |
On Zaremba's Conjecture
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. We will present recent progress on this problem, joint with Jean Bourgain.
| Hi-Res | 359.69 MB |
| Lo-Res | 194.59 MB |