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...
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...
The Coulomb Gas is a model of Statistical Mechanics with a
special type of phase transition. In the first part of the talk I
will review the expected features conjectured by physicists and the
few mathematical results so far obtained. The second...
In a joint work with Tsuyoshi Ito we have constructed a
fingerprinting scheme (i.e., hashing) that leaks significantly less
than log(1/epsilon) bits about the preimage, where epsilon is the
error ("collision") probability. It is easy to see...
The Bernstein center plays a role in the representation theory
of locally profinite groups analogous to that played by the center
of the group ring in the representation theory of finite groups.
When F is a finite extension of Q_p, we discuss...
