The complexity of simple stochastic games (SSGs) has been open
since they were defined by Condon in 1992. Such a game is played by
two players, Min and Max, on a graph consisting of max nodes, min
nodes, and average nodes. The goal of Max is to...
Recently there has been much interest in polynomial threshold
functions in the context of learning theory, structural results and
pseudorandomness. A crucial ingredient in these works is the
understanding of the distribution of low-degree...
We develop the droplet scaling theory for the low temperature
critical behavior of two-dimensional Ising spin glasses. The models
with integer bond energies vs. continuously-distributed bond
energies are in the...
To a regular algebraic cuspidal representation of GL(2) over a
quadratic imaginary field, whose central character is conjugation
invariant, Taylor et al. associated a two dimensional Galois
representation which is unramified at l different from p...
Iwasawa developed his theory for class groups in towers of
cyclotomic fields partly in analogy with Weil's theory of curves
over finite fields. In this talk, we present another such
conjectural analogy. It seems intertwined with Leopoldt's...
Erdos conjectured that N points in the plane determine at least
c N (log N)^{-1/2} different distances. Building on work of
Elekes-Sharir, Nets Katz and I showed that the number of distances
is at least c N (log N)^{-1} . (Previous estimates had...
We prove that the Cauchy problem for the Benjamin-Ono-Burgers
equation is uniformly globally well-posed in H^1 for all
"\epsilon\in [0,1]". Moreover, we show that for any T>0 the
solution converges in C([0,T]:H^1) to that of Benjamin-Ono equation
as...
A ``tournament'' is a digraph obtained from a complete graph by
directing its edges, and ``colouring'' a tournament means
partitioning its vertex set into acyclic subsets (``acyclic'' means
the subdigraph induced on the subset has no directed cycles...
we will describe various models of sparse and planar graphs and
the associated distributions of eigenvalues (and eigenvalue
spacings) which come up. The talk will be light on theorems, and
heavy on experimental data.
