| Maximizing queueing network utility
subject to stability
(ps/pdf)
|
 |
|
Sasha Stolyar (Bell Labs)
We study a model which accommodates a wide range of seemingly
very different resource allocation problems in communication networks.
Some examples: utility based congestion control of complex time-varying
(wireless) networks, minimizing average power consumption
in wireless networks, scheduling in wireless systems
subject to power consumption and/or traffic rate constraints.
The model is a controlled queueing network, where controls have dual
effect. In addition to determining exogenous customer arrival rates,
service rates at the nodes, and (possibly random) routing
of customers among the nodes, each control decision produces a certain
vector of "commodities." The set of available control choices depends
on the underlying random network mode. Network "utility" is a concave
function of the vector of long-term average rates at which commodities
are produced. The goal is maximize utility while keeping network
queues stable. We introduce a very parsimonious dynamic control policy,
called Greedy Primal-Dual algorithm, and prove its asymptotic
optimality. Although the model is formulated in terms
of a queueing network, the algorithm can be viewed as a dynamic
mechanism for solving rather general convex optimization problems.
top of page
|
| Generating random graphs with given degrees
(ps/pdf)
|
|
|
Joe Blitzstein (Stanford)
Random graphs with a given degree sequence are a
useful model capturing several features absent in
the classical model, such as dependent edges and
non-binomial degrees. We use a characterization
due to Erdos and Gallai to develop a sequential
algorithm for generating a random labeled graph
with a given degree sequence. The algorithm
is easy to implement and use with sequential
importance sampling. Applications such as studying
a real-world food web and estimating the number
of graphs with a given degree sequence are
discussed. Joint work with Persi Diaconis.
top of
page
|
| Performance and scaling in complex networks: A spectral approach
(ps/pdf)
|
|
|
Milena Mihail (Georgia Tech)
The issue of performance scalability is of
fundamental importance in complex communications
networks. How does congestion scale on the
Internet? At what rate do crawlers discover new
web pages? Spectral graph theory is a powerful
mathematical tool that helps characterize the
performance of many algorithms when run on a
particular graph. We use spectral graph theory to
answer the above questions in several families of
random graphs that model the Internet and the WWW.
top of
page
|
| Random matrices and infinitesimal rotations
(ps/pdf)
|
|
|
Elizabeth Meckes (Stanford)
A theme in studying random matrices from the classical groups is that
Haar-distributed matrices are close to Gaussian matrices in many ways; one
way is that linear functions of random orthogonal matrices are
asymptotically normally distributed (as the dimension approaches
infinity). I will discuss an infinitesimal version of Stein's method,
introduced by Stein in 1995, which can be used to obtain a rate of
convergence in this and related theorems.
top of
page
|
| Estimating mixing times via
the spectral profile
(ps/pdf)
|
|
|
Sharad Goel (Stanford)
Given 52 playing cards, how many shuffles does it take to
approximately randomize the deck? More generally, how long does it
take a finite Markov chain to get close to its stationary
distribution? In this talk, I'll introduce the spectral profile as a
tool for proving upper and lower bounds on convergence rates. This
approach extends the commonly used spectral gap method, and allows us
to recover and refine previous conductance-based estimates of mixing
time. I will illustrate how the spectral profile technique is applied
in several models, including groups with moderate growth, the
fractal-like Viscek graphs, and the torus. This work is joint with
Ravi Montenegro and Prasad Tetali.
top of
page
|
| The universality classes in the parabolic Anderson model
(ps/pdf)
|
|
|
Peter Mörters (Univ. of Bath)
We discuss the Cauchy problem for the
spatially discrete heat equation in a random
i.i.d. potential with localised initial datum. The
emphasis is on the question, which features of the
potential distribution influence the qualitative
behaviour of the solution of the problem. The
talk is based on joint work with Wolfgang Koenig
(Leipzig) and Remco van der Hofstad (Eindhoven).
top of
page
|
| Importance sampling and differential games
(ps/pdf)
|
|
|
Paul Dupuis (Brown)
Importance sampling is a variance reduction
technique used to improve the efficiency of
Monte Carlo approximation of probabilities and
expected values. Under certain law of large
numbers scalings, the optimal performance of
importance sampling schemes can be characterized
by a differential game, or equivalently, in terms
of the solution to the related Isaacs equation
(a nonlinear PDE).
In this talk, we will describe how subsolutions to the Isaacs equation
can be used very effectively in the design and analysis of asymptotically
optimal importance sampling schemes. The main ideas are first described
for a multi-dimensional version of the level crossing problem studied
by Siegmund. We then discuss other classes of problems to which the
approach has been applied, including stochastic networks and sums of
heavy-tailed random variables.
top of
page
|
| A reversible growth model on the homogeneous tree:
some results and open questions
(ps/pdf)
|
|
|
Amber Puha (CSU San Marcos)
A modified contact process on the homogeneous
tree is considered.
The modification is to the death rate: an occupied site becomes
vacant at rate one if the number of occupied neighbors is at most one.
This modification leads to a growth model that is reversible, off the
empty set, provided that the initial set of occupied sites is connected.
Reversibility admits tools for studying the survival properties of the
system not available in a nonreversible situation. The main result is
that there is exactly one phase transition and the value of the birth
parameter at which the phase transition occurs is explicitly computed.
In this talk, we demonstrate how reversibility is exploited to identify
the exact location of the phase transition and discuss some directions
for further investigation.
top of
page
|
| Large deviations for analytic functions
with diffusing coefficients
(ps/pdf)
|
|
|
Ben Hough (UC Berkeley)
We consider a random analytic function f whose
zero set is translationally invariant in the
plane. This zero set is amazingly "lattice-like".
A recent work of Sodin and Tsirelson shows that
it can be matched to a perturbed lattice with
Gaussian tails. Moreover, the "hole probability"
that a disk of radius R contains no zeros of f
decays exponentially in the square of the area
of the disk. This asymptotic behavior is also
observed in the perturbed lattice model in which
lattice points are perturbed by independent
complex normal random variables.
Allowing the coefficients of f to evolve as
independent Ornstein-Uhlenbeck processes, the zero
set evolves as a time homogenous Markov process
in the plane. We show that the probability of
observing a hole of radius R for time T in the
random zero model is exponentially worse than
the corresponding probability for the perturbed
lattice model in which lattice points evolve as
independent Ornstein-Uhlenbeck processes.
top of
page
|
