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...
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...
