A k-modal probability distribution over the domain {1,...,N} is
one whose histogram has at most k "peaks" and "valleys". Such
distributions are a natural generalization of the well-studied
class of monotone increasing (or monotone decreasing)...
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...
