Rahul Jain (University of Southern California)

"Transitory" queueing systems, namely those that exist only for finite time are all around us. And yet, current queueing theory provides with very few models and even fewer tools to understand them. In this talk, I'll introduce a model that may be more appropriate in "transitory" queueing situations. I'll start by first talking about the ``concert arrival game" that we introduced. This model captures the tradeoff in decision-making when users must decide whether to arrive early and wait in a queue, or arrive late but miss out on opportunities (e.g., best seats at a concert). With such decision-making by the users, it is a folly to assume that the arrival process is exogenous, and a well-behaved renewal process. Thus, under the fluid model, we characterize the equilibrium arrival profile and characterize the ``price of anarchy" (PoA). We also give some simple mechanisms to reduce it. We then present various extensions including to general feedforward networks when routing itself is strategic. The concert queueing game led us to the Delta(i)/GI/1 queue - a new model for transitory queueing systems, in which a each user picks their time of arrival from a common distribution. We derive the fluid and diffusion process limits for such a model. We find that the limiting queue length process is a reflection of a combination of a Brownian motion and a Brownian bridge. The convergence is established in the M1 topology, and we also show that it is not possible to obtain it in the stronger J1 topology. Such models allow us to study transitory queueing systems which are not very amenable to extant techniques in queueing theory.

Yashodhan Kanoria (MSR New England and Columbia University)

We analyze large random two-sided matching markets with different numbers of men and women. We show that being on the short side of the market confers a large advantage, in a sense that the short side roughly chooses the matching while the long side roughly gets chosen. In addition, the matching is roughly the same under all stable matchings. Consider a market with n men and n+k women, for arbitrary 1 <= k<= n/2. We show that, with high probability, the men's average rank of wives is less than 5log(n/k) in any stable match. Further, men's average rank of wives in the women-optimal stable match (WOSM) is within a factor 1+\epsilon of that in the men-optimal stable match (MOSM). On the other hand, the women's average rank of husbands is at least n/(5 log(n/k)) in all stable matches, and is again very nearly the same in the WOSM and MOSM. Thus, our results imply that the core is likely to be "small". Simulations show that our the same features arise even in small markets. Joint work with Itai Ashlagi and Jacob D. Leshno

Rahul Jain (University of Southern California)

Multi-Armed bandits are an elegant model of learning in an unknown and uncertain environment. Such models are relevant in many scenarios, and of late have received increased attention recently due to various problems of distributed control that have arisen in wireless networks, pricing models on the internet, etc. We consider a non-Bayesian multi-armed bandit setting proposed by Lai and Robbins in mid-80s. There are multiple arms each of which generates an i.i.d. reward from an unknown distribution. There are multiple players, each of whom is choosing which arm to play. If two or more players choose the same arm, they all get zero rewards. The problem is to design a learning algorithm to be used by the players that results in an orthogonal matching of players to arms (e.g., users to channels in wireless networks), and moreover minimizes the expected regret. We first consider this as an online bipartite matching problem. We model this combinatorial problem as a classical multi-armed bandit problem but with dependent arms, and propose an index-based learning algorithm that achieves logarithmic regret. From prior results, it is known that this is order-optimal. We then consider the distributed problem where players do not communicate or coordinate in any way. We propose an index-based algorithm that uses Bertsekas' auction mechanism to determine the bipartite matching. We show that the algorithm has expected regret at most near-log-squared. This is the first distributed multi-armed bandit learning algorithm in a general setting.

Rahul Mazumder (MIT)

Low-rank matrix regularization is an important area of research in statistics and machine learning with a wide range of applications. For example, in the context of Missing data imputation arising in recommender systems (e.g. the Netflix Prize), DNA microarray and audio signal processing, among others, the object of interest is a matrix (X) for which the training data comprises of a few noisy linear measurements. The task is to estimate X, under a low rank constraint and possibly additional affine constraints on X. In practice, the matrix dimensions frequently range from hundreds of thousands to even a million --- leading to severe computational challenges. In this talk, I will describe computationally tractable models and scalable (convex) optimization based algorithms for a class of low-rank regularized problems. Exploiting problem-specific statistical insights, problem structure and using novel tools for large scale SVD computations play important roles in this task. This is joint work with Trevor Hastie, Rob Tibshirani and Dennis Sun (Stanford Statistics).

Philippe Rigollet (Princeton University)

Sparse Principal Component Analysis (SPCA) is a remarkably useful tool for practitioners who had been relying on ad-hoc thresholding methods. Our analysis aims at providing a a framework to test whether the data at hand indeed contains a sparse principal component. More precisely we propose an optimal test procedure to detect the presence of a sparse principal component in a high-dimensional covariance matrix. Our minimax optimal test is based on a sparse eigenvalue statistic. Alas, computing this test is known to be NP-complete in general and we describe a computationally efficient alternative test using convex relaxations. Our relaxation is also proved to detect sparse principal components at near optimal detection levels and performs very well on simulated datasets. Moreover, we exhibit some evidence from average case complexity that this slight deterioration may be unavoidable.

Alexei Borodin (Massachusetts Institute of Technology)

The goal of the talk is to describe a class of solvable random growth models of one and two-dimensional interfaces. The growth is local (distant parts of the interface grow independently), it has a smoothing mechanism (fractal boundaries do not appear), and the speed of growth depends on the local slope of the interface.

Semen Shlosman (CNRS, France and Institute for Information Transmission Problems, Russia)

We study particle systems corresponding to highly connected queueing networks. We examine the validity of the so-called Poisson Hypothesis (PH), which predicts that the Markov process, describing the evolution of such particle system, started from a reasonable initial state, approaches the equilibrium in time independent of the size of the network.

Alexander Rybko (Institute for Information Transmission Problems, Russia)

We study the sequences of Markov processes defining the evolution of a general symmetric queueng network with the number of nodes tending to infinity. These sequences have limits which are nonlinear Markov processes. Time evolution of these nonlinear Markov processes are sometimes simpler and easier to analyze than the evolution of corresponding prelimit Markov processes on finite graphs. This fact give the possibility to find good approximation for the behavior of symmetric queueing networks on large graphs. Examples will be discussed.

Guy Bresler (University of California, Berkeley)

DNA sequencing is the basic workhorse of modern biology and medicine. Shotgun sequencing is the dominant technique used: many randomly located short fragments called reads are extracted from the DNA sequence, and these reads are assembled to reconstruct the original DNA sequence. Despite major effort by the research community, the DNA sequencing problem remains unresolved from a practical perspective: it is currently not known how to produce a good assembly of most read data-sets.

Andrei Raigorodksii (Yandex and Moscow Institute of Physics and Technology)

In my talk I will present our research groups in Yandex which is the main search engine in Russia, and Moscow Institute of Physics and Technology which is a kind of Russian MIT.

Andrei Raigorodksii (Yandex and Moscow Institute of Physics and Technology)

In the past 20 years, there has been a lot of work concerning modeling real networks such as Internet, WWW, social networks, biological networks, etc. In our talk, we will mainly concentrate on models devoted to incorporating properties of the web graph. We will give a survey of different such models including those of Bollob\'as--Riordan, Buckley--Osthus, Cooper--Frieze, etc. We will also present some new related mathematical results obtained by our group in Yandex, Moscow Institute of Physics and Technology, Moscow State University. Finally, we will discuss some applications of these results to ranking as well as some future research directions.

Daniil Musatov (Yandex and Moscow Institute of Physics and Technology)

Consider the following situation. Alice knows string x and Bob knows string y. There is a limited capacity information channel from Alice to Bob. Alice wants to transmit a message that is sufficient for Bob to recover x. What is a minimum capacity that allows her to do it? Obviously, there is a theoretical minimum: the amount of information in x that is not contained in y. Astonishing enough, this is a precise estimate: Alice can produce an optimal code even though she does not know what information Bob already possesses. In Shannon entropy framework this fact is stated as Slepian-Wolf theorem. In Kolmogorov complexity framework (where both Alice and Bob use computable functions and logarithmic advice) it was proven by Muchnik. In the talk we will give another proof of Muchnik's result and extend it to space-bounded case, where Alice and Bob use space-bounded computations and advice is still logarithmic.

Liudmila Ostroumova (Yandex and Moscow Institute of Physics and Technology)

We consider the random graph model $H_{a,m}^n$. An explicit construction of this model was suggested by Buckley and Osthus. For any fixed positive integer $m$ and positive real $a$ we define a random graph $H_{a,m}^n$ in the following way. The graph $H_{a,1}^1$ consists of one vertex and one loop. Given a graph $H_{a,1}^{t-1}$ we transform it into $H_{a,1}^{t}$ by adding one new vertex and one new random edge $(t,i)$, where $i \in \{1, \dots, t \}$ and $\Prob(i=t) = \frac{a}{(a+1)t-1}$, $\Prob(i=s) = \frac{d_{H_{a,1}^{t-1}}(s) - 1 + a}{(a+1)t-1}$ if $1 \le s \le t-1$. To construct $H_{a,m}^n$ with $m>1$ we start from $H_{a,1}^{mn}$. Then we identify the vertices $1, \dots, m$ to form the first vertex; we identify the vertices $m+1, \dots, 2m$ to form the second vertex, etc.

Dmitry Shabanov (Yandex and Moscow Institute of Physics and Technology)

WThe talk is devoted to the classical problem of estimating the Van der Waerden number $W(n,r)$. The famous Van der Waerden theorem states that, for any integers $n\ge 3$, $r\ge 2$, there exists the smallest integer $W(n,r)$ such that, for every $N\ge W(n,r)$, in any $r$-coloring of the set $\{1,2,\ldots,N\}$ there exists a monochromatic arithmetic progression of length $n$. The best upper bound for $W(n,r)$ in the general case was obtained by W.T. Gowers in 2001 who proved that $$ W(n,r)\le 2^{2^{r^{2^{2^{n+9}}}}}.$$ Our talk is concentrated on the lower bounds for the Van der Waerden number. We shall show that lower estimates for $W(n,r)$ are closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. Our main result is a new lower bound for $W(n,r)$: $$W(n,r)\ge c\,\frac {r^{n-1}}{\ln n},$$ where $c>0$ is an absolute constant. The proof is based on a continuous-time random recoloring process.

Yuan Zhong (MIT ORC)

We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture about optimal queue-size scaling for input-queued switches.

Eitan Bachmat (Ben-Gurion University)

Given N I/O requests to a disk drive, how long will it take the disk drive to service them? How long does it take to board an airplane? We will show that such questions are modeled by the same math that models the universe in relativity theory, namely, space-time (Lorentzian) geometry.As a result of this connection we will try to understand what is the best way to service I/O, what is the best airplane boarding policy and what makes free falling bodies take the trajectories that they do. On the way we may also encounter a silly card game and random matrices. The talk is self contained, experience with boarding an airplane is helpful.

Erol Peköz (Boston University)

Preferential attachment random graphs evolve in time by sequentially adding vertices and edges randomly so that connections to vertices having high degree are favored. There has been an explosion of research on these models since Barabasi and Albert popularized them in 1999 to explain the so-called power law behavior observed in real networks such as the graph of the Internet where Web pages correspond to vertices and hyperlinks between them correspond to edges. In this talk we will show how to derive rates of convergence for the distribution of the degree of a fixed vertex to its distributional limit using a new variation of Stein's method that relies on finding couplings to motivate distributional transformations for which limit distributions are fixed points. Surprisingly little is known about these limit distributions despite the large literature on such graphs.
top of page

Vivek Goyal (MIT EECS)

Resolution of a data acquisition system is usually thought to be determined completely by sensing properties, such as density and accuracy of measurements. This talk advocates the view that resolution is, in addition, dependent on signal modeling and the complexity of computations allowed. This view is developed concretely for the acquisition of sparse signals, where the asymptotic relationship between resolution and the number of measurements is studied for algorithms with various complexities. The sparse signal recovery problem corresponds perfectly to a model of random multiple access communication in which the task of the receiver is to determine only the subset of the users that transmitted. This connection gives insight on the performance of single- and multi-user detection algorithms. Specifically, all known practical multiuser detection techniques become interference limited at high SNR. However, power control is natural in the multiple access setting, and we are able to prove that a simple detection algorithm based on orthogonal matching pursuit is not interference limited under optimal power control. The talk is based on joint work with Alyson Fletcher and Sundeep Rangan.
top of page

Vivek F. Farias (MIT Sloan)

We present a novel linear program for the approximation of the dynamic programming value function in high-dimensional stochastic control problems. LP approaches to approximate DP naturally restrict attention to approximations that, depending on the context, are upper or lower bounds to the optimal value function. Our program -- the `smoothed LP' -- relaxes this restriction in an appropriate fashion while remaining computationally tractable. Doing so appears to have several advantages: o We demonstrate superior bounds on the quality of approximation to the optimal value function afforded by our approach. o Experiments with our approach on a challenging problem (the game of Tetris) show that the approach outperforms a variety of approximate DP algorithms (including the LP approach, TD-learning and policy gradient methods) by a significant margin. Joint work with Vijay Desai and Ciamac Moallemi (Columbia).
top of page

Scott Sheffield (MIT Math)

Fractional Brownian motions are the most natural generalizations of ordinary (one-dimensional) Brownian motions that allow for some amount of long range dependence (a.k.a. "momentum effects"). They are sometimes used in mathematical finance as models for logarithmic asset prices. We describe some natural random simple walks on the integers that have fractional Brownian motion as a scaling limit. In a sense, these walks are the most natural discrete analogs of fractional Brownian motion.
top of page

Mokshay Madiman (Yale University)

We develop an information-theoretic foundation for compound Poisson approximation and limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation). First, su?cient conditions are given under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. In particular, it is shown that a maximum entropy property is valid if the measures under consideration are log-concave, but that it fails in general. Second, approximation bounds in the (strong) relative entropy sense are given for distributional approximation of sums of independent nonnegative integer valued random variables by compound Poisson distributions. The proof techniques involve the use of a notion of local information quantities that generalize the classical Fisher information used for normal approximation, as well as the use of ingredients from Stein's method for compound Poisson approximation. This work is joint with Andrew Barbour (Zurich), Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).
top of page

Mohsen Bayati (Microsoft Research New England)

Large-scale complex networks have been the objects of study for the past two decades, and one central problem have been constructing or designing realistic models for such networks. This problem appears in a variety of applications including coding theory and systems biology. Unfortunately, the existing algorithms for this problem have large running times, making them impractical to use for networks with millions of links. We will present a technique to design an almost linear time algorithm for generating random graphs with given degree sequences for a range of degrees. Next, we extend the analysis to design an algorithm for efficiently generating random graphs without short cycles. These algorithms can be used for constructing high performance low-density parity-check codes (LDPC codes). Based on joint works with Jeong Han Kim, Andrea Montanari, and Amin Saberi.
top of page

Benoît Collins (University of Ottawa)

We introduce the unitary Schwinger-Dyson equation associated to a selfadjoint polynomial potential V. The V=0 case corresponds to the free product state, so the Schwinger-Dyson equation can be considered as a deformation of free probability. We show that the solutions of this equation are unique for small V's and correspond to a large N limit of a multi-matrix model. This technique allows to show that a wide class of unitary and orthogonal multi-matrix models converge asymptotically. We also give a combinatorial and analytic description of the limit, solving a series of open questions raised in theoretical physics in the late 70's. This is joint work with A. Guionnet and E. Maurel-Segala.
top of page

Johan van Leeuwaarden (Eindhoven University of Technology, EURANDOM, NYU Stern)

We consider the Gaussian random walk (one-dimensional random walk with normally distributed increments), and in particular the moments of its maximum M. Explicit expressions for all moments of M are derived in terms of Taylor series with coefficients that involve the Riemann zeta function. We build upon the work of Chang and Peres (1997) on P(M=0) and Bateman's formulas on Lerch's transcendent. Our result for E(M) completes earlier work of Kingman (1965), Siegmund (1985), and Chang and Peres (1997). The maximum M shows up in a range of applications, such as sequentially testing for the drift of a Brownian motion, corrected diffusion approximations, simulation of Brownian motion, option pricing, thermodynamics of a polymer chain, and queueing systems in heavy traffic. Some of these applications are discussed, as well as several issues open for further research. This talk is based on joint work with A.J.E.M. Janssen.
top of page

Ed Farhi (MIT Physics)

The quantum adiabatic algorithm is a general approach to solving combinatorial search problems using a quantum computer. It will succeed if the run time is long enough. I will discuss how this algorithm works and our current understanding of the required run time.
top of page

Ton Dieker (Georgia Tech I&SE)

Stimulated by applications to internet traffic modeling and insurance mathematics, distributions with heavy tails have been widely studied over the past decades. This talk addresses a fundamental large-deviation problem for random walks with heavy-tailed step-size distributions. We consider so-called subexponential step-size distributions, which constitute the most widely-used class of heavy-tailed distributions. I will present a theory to study sequences {x_n} for which P{S_n>x_n} behaves asymptotically like n P {S_1>x_n} for large n. (joint work with D. Denisov and V. Shneer)
top of page

Peter Glynn (Stanford MS&E)

Many performance engineering and operations research modeling formulations lead to Markov models in which the key performance measure is an expectation defined in terms of the stationary distribution of the process. In models of realistic complexity, it is often difficult to compute such expectations in closed form. In this talk, we will discuss a simple class of bounds for such stationary expectations, and describe some of the mathematical subtleties that arise in making rigorous such bounds. We will also discuss how such bounds can be used algorithmically. This work is joint with Denis Saure and Assaf Zeevi.
top of page

Daron Acemoglu (MIT Econ)

Under the assumption that individuals know the conditional distributions of signals given the payoff-relevant parameters, existing results conclude that, as individuals observe infinitely many signals, their beliefs about the parameters will eventually merge. We first show that these results are fragile when individuals are uncertain about the signal distributions: given any such model, a vanishingly small individual uncertainty about the signal distributions can lead to a substantial (non-vanishing) amount of differences between the asymptotic beliefs. We then characterize the conditions under which a small amount of uncertainty leads only to a small amount of asymptotic disagreement. According to our characterization, this is the case if the uncertainty about the signal distributions is generated by a family with "rapidly-varying tails" (such as the normal or the exponential distributions). However, when this family has "regularly-varying tails" (such as the Pareto, the log-normal, and the t-distributions), a small amount of uncertainty leads to a substantial amount of asymptotic disagreement.
top of page

Victor Chernozhukov (MIT Econ)

The most common approach to estimating conditional quantile curves is to fit a curve, typically linear, pointwise for each quantile. Linear functional forms, coupled with pointwise fitting, are used for a number of reasons including parsimony of the resulting approximations and good computational properties. The resulting fits, however, may not respect a logical monotonicity requirement -- that the quantile curve be increasing as a function of probability. This paper studies the natural monotonization of these empirical curves induced by sampling from the estimated non-monotone model, and then taking the resulting conditional quantile curves that by construction are monotone in the probability. This construction of monotone quantile curves may be seen as a bootstrap and also as a monotonic rearrangement of the original non-monotone function. It is shown that the monotonized curves are closer to the true curves in finite samples, for any sample size. Under correct specification, the rearranged conditional quantile curves have the same asymptotic distribution as the original non-monotone curves. Under misspecification, however, the asymptotics of the rearranged curves may partially differ from the asymptotics of the original non-monotone curves. An analogous procedure is developed to monotonize the estimates of conditional distribution functions. The results are derived by establishing the compact (Hadamard) differentiability of the monotonized quantile and probability curves with respect to the original curves in discontinuous directions, tangentially to a set of continuous functions. In doing so, the compact differentiability of the rearrangement-related operators is established.
top of page

David Forney (MIT LIDS)

One of Shannon's earliest results was his determination of the capacity of the binary symmetric channel (BSC). Shannon went on to show that, with randomly chosen codes and optimal decoding, the probability of decoding error decreases exponentially for any transmission rate less than capacity. Much of the important early work of Shannon, Elias, Fano and Gallager was devoted to determining bounds on the corresponding "error exponent." A later approach to this problem, pioneered by Csiszar and Korner, and now adopted in many modern information theory courses such as 6.441, determines error exponents using large-deviation theory. This approach has several advantages: (a) It can be remarkably simple and intuitive; (b) It gives correct error exponents, not just bounds; (c) It gives insight into how decoding errors typically occur. We illustrate this approach by developing the correct error exponents at all rates for both random codes and random linear codes on the BSC, assuming optimal decoding. We discuss how decoding errors typically occur. In particular, we show why the classical algebraic coding approach never had any hope of approaching channel capacity, even on the BSC. This talk is intended to be pitched at an elementary and tutorial level.
top of page