We present the first analysis of the Join-the-Shortest-Queue (JSQ) routing policy for Web server farms. Web server farms involve a collection of Processor-Sharing (PS) servers, whereas prior analyses of JSQ have always assumed First-Come-First-Serve (FCFS) servers. This work introduces a new technique: Single-Queue-Approximation (SQA), and uses the technique to prove some interesting insensitivity properties for Web server farms.
Based on joint work with: Varun Gupta, Karl Sigman, and Ward Whitt.

We consider a 2-person perfect information ``liar'' game, often called a R\'enyi-Ulam game. The basic game is that of ``twenty questions'' played between questioner Paul and responder Carole; Paul searches for a distinguished element $x$ in a search space $[n]$ by asking Yes-No questions of the form ``is $x\in A$'', where $A\subseteq [n]$. Carole responds `Yes' or `No', lying in up to $k$ responses. The fully off-line game is equivalent to $k$-error-correcting codes.

We extend this game to a general channel $\mathcal{C}$ which governs the manner in which Carole may lie. Specifically, given the alphabet $[t]:=\{1,\ldots,t\}$, Paul searches for $x\in[n]$ by partitioning $[n]=A_1\cup \cdots \cup A_t$ and asking for $a$ such that $x\in A_a$. A lie is a tuple $(a,b)\in[t]\times [t]$ with $a\neq b$. The channel $C$ specifies an arbitrary set of lie strings of bounded length $\leq k$ from which Carole may choose a string and intersperse its lies, in order, among her responses. For example, when $t=2$, Carole lies with $(1,2)$ when she responds with 2 (``No'') when the correct response is 1 (``Yes''). We further restrict Paul to ask his questions in two off-line batches. We show that the maximum size of the search space $[n]$ for which Paul can guarantee finding the distinguished element is $t^{q+k}/(E_k(C){q \choose k})$ as $q\rightarrow\infty$, where $E_k(C)$ is the number of lie strings in $\mathcal{C}$ of maximum length $k$, generalizing previous work of Dumitriu and Spencer, and of Cicalese, Deppe, and Mundici. We similarly solve the pathological liar variant. This is joint work with Kathryn Nyman (Loyola University-Chicago).

Suppose n pursuers starting at the origin chase a single prey
starting at 1, all doing standard independent Brownian motions on the real line. Bramson and Griffeath (1991) showed that the expected capture time is infinite for three or fewer pursuers and, after simulations, conjectured that it is finite for four or more. Li and Shao (2001) proved it for five or more pursuers. In recent work with Ratzkin, we show that it finite for four, completing the proof. We use the idea of Li and Shao to reduce the problem to an estimate of the first Dirichlet eigenvalue of a domain in the sphere.

I'll discuss eigenvalues, describe the reduction, the eigenvalue estimates, and some related numerics.

We consider the problem of estimating a set S from a random sample of
points of S, which amounts at estimating the support of the
underlying probability density. Set estimation has applications in
various situations, including medical diagnosises, image analysis,
and quality control for example. We focus on the simple set estimator
defined as the union of balls centered at the random points. Using
tools from Riemannian geometry, and under mild analytic conditions on
the underlying density of the data, we derive the exact rate of
convergence of this set estimator.
In closed connection with the problem of set estimation, we study the
estimation of the number of connected components of a level set of a
multivariate probability density. This allows one to assess the
number of clusters of a statistical population, which is an essential
problem of unsupervised learning. We introduce an estimator based on
a graph, and using similar geometrical tools, we establish the
asymptotic consistency of the methodology.