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...
A "sparsifier" of a graph is a weighted subgraph for which every
cut has approximately the same value as the original graph, up to a
factor of (1 +/- eps). Sparsifiers were first studied by Benczur
and Karger (1996). They have wide-ranging...
