We analyze principal component regression (PCR) in a high-dimensional error-in-variables setting with fixed design. Under suitable conditions, we show that PCR consistently identifies the unique model with minimum $\ell_2$-norm. These results enable us to establish non-asymptotic out-of-sample prediction guarantees that improve upon the best known rates. In the course of our analysis, we introduce a natural linear algebraic condition between the in- and out-of-sample covariates, which allows us to avoid distributional assumptions for out-of-sample predictions. Our simulations illustrate the importance of this condition for generalization, even under covariate shifts. Accordingly, we construct a hypothesis test to check when this condition holds in practice. As a byproduct, our results also lead to novel results for the synthetic controls literature, a leading approach for policy evaluation. To the best of our knowledge, our prediction guarantees for the fixed design setting have been elusive in both the high-dimensional error-in-variables and synthetic controls literatures.

We are interested in developing a data-driven method to evaluate race-induced biases in law enforcement systems. While recent works have addressed this question in the context of police-civilian interactions using police stop data, they have two key limitations. First, bias can only be properly quantified if true criminality is accounted for in addition to race, but it is absent in prior works. Second, law enforcement systems are multi-stage and hence it is important to isolate the true source of bias within the "causal chain of interactions" rather than simply focusing on the end outcome; this can help guide reforms. In this work, we address these challenges by presenting a multi-stage causal framework incorporating criminality. We provide a theoretical characterization and an associated data-driven method to evaluate (a) the presence of any form of racial bias, and (b) if so, the primary source of such a bias in terms of race and criminality. Our framework identifies three canonical scenarios with distinct characteristics: in settings like (1) airport security, the primary source of observed bias against a race is likely to be bias in law enforcement against innocents of that race; (2) AI-empowered policing, the primary source of observed bias against a race is likely to be bias in law enforcement against criminals of that race; and (3) police-civilian interaction, the primary source of observed bias against a race could be bias in law enforcement against that race or bias from the general public in reporting (e.g. via 911 calls) against the other race. Through an extensive empirical study using police-civilian interaction (stop) data and 911 call data, we And an instance of such a counter-intuitive phenomenon: in New Orleans, the observed bias is against the majority race and the likely reason for it is the over-reporting (via 911 calls) of incidents involving the minority race by the general public.

We introduce a novel framework for incorporating human expertise into algorithmic predictions. Our approach leverages human judgment to distinguish inputs which are *algorithmically indistinguishable*, or "look the same" to predictive algorithms. We argue that this framing clarifies the problem of human-AI collaboration in prediction tasks, as experts often form judgments by drawing on information which is not encoded in an algorithm's training data. Algorithmic indistinguishability yields a natural test for assessing whether experts incorporate this kind of "side information", and further provides a simple but principled method for selectively incorporating human feedback into algorithmic predictions. We show that this method provably improves the performance of any feasible algorithmic predictor and precisely quantify this improvement. We find empirically that although algorithms often outperform their human counterparts *on average*, human judgment can improve algorithmic predictions on *specific* instances (which can be identified ex-ante). In an X-ray classification task, we find that this subset constitutes nearly 30% of the patient population. Our approach provides a natural way of uncovering this heterogeneity and thus enabling effective human-AI collaboration.

In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played amongnrandomly drawn agents from the population. The agents in our model can be individuals, sports teams, or even Wall Street fund managers. Formally, we postulate that the likelihoods of outcomes of games are governed by the parametric Bradley-Terry-Luce (or multinomial logit) model, where the probability of an agent beating another is the ratio between its skill level and the pairwise sum of skill levels, and the skill parameters are drawn from an unknown, non-parametric skill density of interest. The above problem is, in essence, to learn a distribution from noisy and quantized observations. We propose a surprisingly simple and tractable algorithm that learns the skill density with near-optimal minimax mean squared error scaling as$n^{-1+\varepsilon }$, for any$\varepsilon \gt 0$, so long as the density is smooth. Our approach brings together prior work on learning skill parameters from pairwise comparisons with kernel density estimation from non-parametric statistics. We then prove information theoretic lower bounds which establish minimax near-optimality of the skill parameter estimation technique used in our algorithm. These bounds utilize a continuum version of Fano’s method along with a careful covering argument. Furthermore, we show that estimation error bounds for the skill density translate to theoretical guarantees on estimating the differential entropy and other bounded statistics of the skill density. Finally, we apply our algorithm to data from soccer world cups and leagues, cricket world cups, and even mutual funds. We find that the differential entropy of a learnt distribution provides a quantitative measure of overall skill in a tournament, which in turn can provide explanations for popular beliefs about perceived qualities of sporting and other tournaments.

Matrix completion is the study of recovering an underlying matrix from a sparse subset of noisy observations. Traditionally, it is assumed that the entries of the matrix are “missing completely at random” (MCAR), i.e., each entry is revealed at random, independent of everything else, with uniform probability. This is likely unrealistic due to the presence of “latent confounders”, i.e., unobserved factors that determine both the entries of the underlying matrix and the missingness pattern in the observed matrix. For example, in the context of movie recommender systems—a canonical application for matrix completion—a user who vehemently dislikes horror films is unlikely to ever watch horror films. In general, these confounders yield “missing not at random” (MNAR) data, which can severely impact any inference procedure that does not correct for this bias. We develop a formal causal model for matrix completion through the language of potential outcomes, and provide novel identification arguments for a variety of causal estimands of interest. We design a procedure, which we call “synthetic nearest neighbors” (SNN), to estimate these causal estimands. We prove finite-sample consistency and asymptotic normality of our estimator. Our analysis also leads to new theoretical results for the matrix completion literature. In particular, we establish entry-wise, i.e., max-norm, finite-sample consistency and asymptotic normality results for matrix completion with MNAR data. As a special case, this also provides entry-wise bounds for matrix completion with MCAR data. Across simulated and real data, we demonstrate the efficacy of our proposed estimator.

We study counterfactual identifiability in causal models with bijective generation mechanisms (BGM), a class that generalizes several widely-used causal models in the literature. We establish their counterfactual identifiability for three common causal structures with unobserved confounding, and propose a practical learning method that casts learning a BGM as structured generative modeling. Learned BGMs enable efficient counterfactual estimation and can be obtained using a variety of deep conditional generative models. We evaluate our techniques in a visual task and demonstrate its application in a real-world video streaming simulation task.

In recent years, multiple notions of algorithmic fairness have arisen. One such notion is individual fairness (IF), which requires that individuals who are similar receive similar treatment. In parallel, matrix estimation (ME) has emerged as a natural paradigm for handling noisy data with missing values. In this work, we connect the two concepts. We show that pre-processing data using ME can improve an algorithm's IF without sacrificing performance. Specifically, we show that using a popular ME method known as singular value thresholding (SVT) to pre-process the data provides a strong IF guarantee under appropriate conditions. We then show that, under analogous conditions, SVT pre-processing also yields estimates that are consistent and approximately minimax optimal. As such, the ME pre-processing step does not, under the stated conditions, increase the prediction error of the base algorithm, i.e., does not impose a fairness-performance trade-off. We verify these results on synthetic and real data.

The well-established practice of time series analysis involves estimating deterministic, non-stationary trend and seasonality components followed by learning the residual stochastic, stationary components. Recently, it has been shown that one can learn the deterministic non-stationary components accurately using multivariate Singular Spectrum Analysis (mSSA) in the absence of a correlated stationary component; meanwhile, in the absence of deterministic non-stationary components, the Autoregressive (AR) stationary component can also be learnt readily, e.g. via Ordinary Least Squares (OLS). However, a theoretical underpinning of multi-stage learning algorithms involving both deterministic and stationary components has been absent in the literature despite its pervasiveness. We resolve this open question by establishing desirable theoretical guarantees for a natural two-stage algorithm, where mSSA is first applied to estimate the non-stationary components despite the presence of a correlated stationary AR component, which is subsequently learned from the residual time series. We provide a finite-sample forecasting consistency bound for the proposed algorithm, SAMoSSA, which is data-driven and thus requires minimal parameter tuning. To establish theoretical guarantees, we overcome three hurdles: (i) we characterize the spectra of Page matrices of stable AR processes, thus extending the analysis of mSSA; (ii) we extend the analysis of AR process identification in the presence of arbitrary bounded perturbations; (iii) we characterize the out-of-sample or forecasting error, as opposed to solely considering model identification. Through representative empirical studies, we validate the superior performance of SAMoSSA compared to existing baselines. Notably, SAMoSSA's ability to account for AR noise structure yields improvements ranging from 5% to 37% across various benchmark datasets.

High-stakes prediction tasks (e.g., patient diagnosis) are often handled by trained human experts. A common source of concern about automation in these settings is that experts may exercise intuition that is difficult to model and/or have access to information (e.g., conversations with a patient) that is simply unavailable to a would-be algorithm. This raises a natural question whether human experts add value which could not be captured by an algorithmic predictor. We develop a statistical framework under which we can pose this question as a natural hypothesis test. Indeed, as our framework highlights, detecting human expertise is more subtle than simply comparing the accuracy of expert predictions to those made by a particular learning algorithm. Instead, we propose a simple procedure which tests whether expert predictions are statistically independent from the outcomes of interest after conditioning on the available inputs (‘features’). A rejection of our test thus suggests that human experts may add value to any algorithm trained on the available data, and has direct implications for whether human-AI ‘complementarity’ is achievable in a given prediction task. We highlight the utility of our procedure using admissions data collected from the emergency department of a large academic hospital system, where we show that physicians’ admit/discharge decisions for patients with acute gastrointestinal bleeding (AGIB) appear to be incorporating information that is not available to a standard algorithmic screening tool. This is despite the fact that the screening tool is arguably more accurate than physicians’ discretionary decisions, highlighting that – even absent normative concerns about accountability or interpretability – accuracy is insufficient to justify algorithmic automation.

In this work, we study empirical risk minimization (ERM) within a federated learning framework, where a central server seeks to minimize an ERM objective function using$n$samples of training data that is stored across$m$clients and the server. The recent flurry of research in this area has identified the Federated Averaging ($\mathtt{FedAve} $) algorithm as the staple for determining$\epsilon $-approximate solutions to the ERM problem. Similar to standard optimization algorithms, e.g., stochastic gradient descent, the convergence analysis of$\mathtt{FedAve} $and its variants only relies on smoothness of the loss function in the optimization parameter. However, loss functions are often very smooth in the training data too. To exploit this additional smoothness in data in a federated learning context, we propose the Federated Low Rank Gradient Descent (FedLRGD) algorithm. Since smoothness in data induces an approximate low rank structure on the gradient of the loss function, our algorithm first performs a few rounds of communication between the server and clients to learn weights that the server can use to approximate clients’ gradients using its own gradients. Then, our algorithm solves the ERM problem at the server using an inexact gradient descent method. To theoretically demonstrate that FedLRGD can have superior performance to$\mathtt{FedAve} $, we present a notion of federated oracle complexity as a counterpart to canonical oracle complexity in the optimization literature. Under some assumptions on the loss function, e.g., strong convexity and smoothness in the parameter,$\eta $-Hölder class smoothness in the data, etc., we prove that the federated oracle complexity of$LRGD $scales like$\phi m (p/\epsilon)^{\Theta (d/\eta)}$and that of$\mathtt{FedAve} $scales like$\phi m (p / \epsilon)^{3/4}$(neglecting typically sub-dominant factors), where$\phi \gg 1$is the ratio of client-to-server communication time to gradient computation time,$p$is the parameter dimension, and$d$is the data dimension. Then, we show that when$d$is small compared to$n$and the loss function is sufficiently smooth in the data, i.e.,$\eta = \Theta (d)$, FedLRGD beats$\mathtt{FedAve} $in federated oracle complexity. Finally, in the course of analyzing FedLRGD, we also establish a general result on low rank approximation of smooth latent variable models.

Consider the task of estimating a 3-order$n \times n \times n$tensor from noisy observations of randomly chosen entries in the sparse regime. We introduce a similarity based collaborative filtering algorithm for estimating a tensor from sparse observations and argue that it achieves sample complexity that nearly matches the conjectured computationally efficient lower bound on the sample complexity for the setting of low-rank tensors. Our algorithm uses the matrix obtained from the flattened tensor to compute similarity, and estimates the tensor entries using a nearest neighbor estimator. We prove that the algorithm recovers a finite rank tensor with maximum entry-wise error (MEE) and mean-squared-error (MSE) decaying to 0 as long as each entry is observed independently with probability$p = \Omega (n^{-3/2 + \kappa })$for any arbitrarily small$ \kappa > 0$. More generally, we establish robustness of the estimator, showing that when arbitrary noise bounded by$ \boldsymbol { \varepsilon }\geq 0$is added to each observation, the estimation error with respect to MEE and MSE degrades by${\sf poly}(\boldsymbol { \varepsilon })$. Consequently, even if the tensor may not have finite rank but can be approximated within$ \boldsymbol { \varepsilon }\geq 0$by a finite rank tensor, then the estimation error converges to${\sf poly}(\boldsymbol { \varepsilon })$. Our analysis sheds insight into the conjectured sample complexity lower bound, showing that it matches the connectivity threshold of the graph used by our algorithm for estimating similarity between coordinates.

Making an informed decision—for example, when choosing a career or housing—requires knowledge about the available options. Such knowledge is generally acquired through costly trial and error, but this learning process can be disrupted by competition. In this work, we study how competition affects the long-term outcomes of individuals as they learn. We build on a line of work that models this setting as a two-sided matching market with bandit learners. A recent result in this area states that it is impossible to simultaneously guarantee two natural desiderata: stability and low optimal regret for all agents. Resource-allocating platforms can point to this result as a justification for assigning good long-term outcomes to some agents and poor ones to others. We show that this impossibility need not hold true. In particular, by modeling two additional components of competition—namely, costs and transfers—we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.

We consider learning a sparse pairwise Markov Random Field (MRF) with continuous-valued variables from i.i.d samples. We adapt the algorithm of Vuffray et al. (2019) to this setting and provide finite-sample analysis revealing sample complexity scaling logarithmically with the number of variables, as in the discrete and Gaussian settings. Our approach is applicable to a large class of pairwise MRFs with continuous variables and also has desirable asymptotic properties, including consistency and normality under mild conditions. Further, we establish that the population version of the optimization criterion employed in Vuffray et al. (2019) can be interpreted as local maximum likelihood estimation (MLE). As part of our analysis, we introduce a robust variation of sparse linear regression a‘ la Lasso, which may be of interest in its own right.

Variational methods, such as mean-field (MF) and tree-reweighted (TRW), provide computationally efficient approximations of the log-partition function for generic graphical models but their approximation ratio is generally not quantified. As the primary contribution of this work, we provide an approach to quantify their approximation ratio for any discrete pairwise graphical model with non-negative potentials through a property of the underlying graph structure $G$. Specifically, we argue that (a variant of) TRW produces an estimate within factor $1/\sqrt{\kappa(G)}$ where $\kappa(G) \in (0,1]$ captures how far $G$ is from tree structure. As a consequence, the approximation ratio is $1$ for trees, $\sqrt{(d+1)/2}$ for graphs with maximum average degree $d$ and $1+1/(2\beta)+o_{\beta\to \infty}(1/\beta)$ for graphs with girth at least $\beta \log N$. The quantity $\kappa(G)$ is the solution of a min-max problem associated with the spanning tree polytope of $G$ that can be evaluated in polynomial time for any graph. We provide a near linear-time variant that achieves an approximation ratio depending on the minimal (across edges) effective resistance of the graph. We connect our results to the graph partition approximation method and thus provide a unified perspective.

We consider offline reinforcement learning (RL) with heterogeneous agents under severe data scarcity, i.e., we only observe a single historical trajectory for every agent under an unknown, potentially sub-optimal policy. We find that the performance of state-of-the-art offline and model-based RL methods degrade significantly given such limited data availability, even for commonly perceived "solved" benchmark settings such as "MountainCar" and "CartPole". To address this challenge, we propose PerSim, a model-based offline RL approach which first learns a personalized simulator for each agent by collectively using the historical trajectories across all agents, prior to learning a policy. We do so by positing that the transition dynamics across agents can be represented as a latent function of latent factors associated with agents, states, and actions; subsequently, we theoretically establish that this function is well-approximated by a "low-rank" decomposition of separable agent, state, and action latent functions. This representation suggests a simple, regularized neural network architecture to effectively learn the transition dynamics per agent, even with scarce, offline data. We perform extensive experiments across several benchmark environments and RL methods. The consistent improvement of our approach, measured in terms of both state dynamics prediction and eventual reward, confirms the efficacy of our framework in leveraging limited historical data to simultaneously learn personalized policies across agents.

The objective of change point detection (CPD) is to detect significant and abrupt changes in the dynamics of the underlying system of interest through multivariate time series observations. In this work, we develop and analyze an algorithm for CPD that is inspired by a variant of the classical singular spectrum analysis (SSA) approach for time series by combining it with the classical cumulative sum (CUSUM) statistic from sequential hypothesis testing. In particular, we model the underlying dynamics of multivariate time series observations through the spatio-temporal model introduced recently in the multivariate SSA (mSSA) literature. The change point in such a setting corresponds to a change in the underlying spatio-temporal model. As the primary contributions of this work, we develop an algorithm based on CUSUM-statistic to detect such change points in an online fashion. We extend the analysis of CUSUM statistics, traditionally done for the setting of independent observations, to the dependent setting of (multivariate) time series under the spatio-temporal model. Specifically, for a given parameter $h > 0$, our method achieves the following desirable trade-off: when a change happens, it detects it within $O(h)$ time delay on average, while in the absence of change, it does not declare false detection for at least $\exp(\Omega(h))$ time length on average. We conduct empirical experiments using benchmark and synthetic datasets. We find that the proposed method performs competitively or outperforms the state-of-the-art change point detection methods across datasets.

By filtering the content that users see, social media platforms have the ability to influence users' perceptions and decisions, from their dining choices to their voting preferences. This influence has drawn scrutiny, with many calling for regulations on filtering algorithms, but designing and enforcing regulations remains challenging. In this work, we examine three questions. First, given a regulation, how would one design an audit to enforce it? Second, does the audit impose a performance cost on the platform? Third, how does the audit affect the content that the platform is incentivized to filter? In response to these questions, we propose a method such that, given a regulation, an auditor can test whether that regulation is met with only black-box access to the filtering algorithm. We then turn to the platform's perspective. The platform's goal is to maximize an objective function while meeting regulation. We find that there are conditions under which the regulation does not place a high performance cost on the platform and, notably, that content diversity can play a key role in aligning the interests of the platform and regulators.

We consider the question of learning the natural parameters of a $k$ parameter \textit{minimal} exponential family from i.i.d. samples in a computationally and statistically efficient manner. We focus on the setting where the support as well as the natural parameters are appropriately bounded. While the traditional maximum likelihood estimator for this class of exponential family is consistent, asymptotically normal, and asymptotically efficient, evaluating it is computationally hard. In this work, we propose a computationally efficient estimator that is consistent as well as asymptotically normal under mild conditions. We provide finite sample guarantees to achieve an ($\ell_2$) error of $\alpha$ in the parameter estimation with sample complexity $O(\mathrm{poly}(k/\alpha))$ and computational complexity ${O}(\mathrm{poly}(k/\alpha))$. To establish these results, we show that, at the population level, our method can be viewed as the maximum likelihood estimation of a re-parameterized distribution belonging to the same class of exponential family.

In this paper, we study the problem of learning the skill distribution of a population of agents from observations of pairwise games in a tournament. These games are played among randomly drawn agents from the population. The agents in our model can be individuals, sports teams, or Wall Street fund managers. Formally, we postulate that the likelihoods of outcomes of games are governed by the parametric Bradley-Terry-Luce (or multinomial logit) model, where the probability of an agent beating another is the ratio between its skill level and the pairwise sum of skill levels, and the skill parameters are drawn from an unknown, non-parametric skill density of interest. The problem is, in essence, to learn a distribution from noisy, quantized observations. We propose a surprisingly simple and tractable algorithm that learns the skill density with near-optimal minimax mean squared error scaling as $n^{-1+\varepsilon}$, for any $\varepsilon>0$, so long as the density is smooth. Our approach brings together prior work on learning skill parameters from pairwise comparisons with kernel density estimation from non-parametric statistics. Furthermore, we prove information theoretic lower bounds which establish minimax optimality of the skill parameter estimation technique used in our algorithm. These bounds utilize a continuum version of Fano's method along with a careful covering argument. We apply our algorithm to various soccer leagues and world cups, cricket world cups, and mutual funds. We find that the entropy of a learnt distribution provides a quantitative measure of skill, which in turn provides rigorous explanations for popular beliefs about perceived qualities of sporting events, e.g., soccer league rankings. Finally, we apply our method to assess the skill distributions of mutual funds. Our results shed light on the abundance of low quality funds prior to the Great Recession of 2008, and the domination of the industry by more skilled funds after the financial crisis.

We consider the question of learning $Q$-function in a sample efficient manner for reinforcement learning with continuous state and action spaces under a generative model. If $Q$-function is Lipschitz continuous, then the minimal sample complexity for estimating $\epsilon$-optimal $Q$-function is known to scale as $\Omega(\frac{1}{\epsilon^{d_1+d_2+2}})$ per classical non-parametric learning theory, where $d_1$ and $d_2$ denote the dimensions of the state and action spaces respectively. The $Q$-function, when viewed as a kernel, induces a Hilbert-Schmidt operator and hence possesses square-summable spectrum. This motivates us to consider a parametric class of $Q$-functions parameterized by its "rank" $r$, which contains all Lipschitz $Q$-functions as $r\to\infty$. As our key contribution, we develop a simple, iterative learning algorithm that finds $\epsilon$-optimal $Q$-function with sample complexity of $\widetilde{O}(\frac{1}{\epsilon^{\max(d_1, d_2)+2}})$ when the optimal $Q$-function has low rank $r$ and the discounting factor $\gamma$ is below a certain threshold. Thus, this provides an exponential improvement in sample complexity. To enable our result, we develop a novel Matrix Estimation algorithm that faithfully estimates an unknown low-rank matrix in the $\ell_\infty$ sense even in the presence of arbitrary bounded noise, which might be of interest in its own right. Empirical results on several stochastic control tasks confirm the efficacy of our "low-rank" algorithms.

We consider the setup of nonparametric blind regression for estimating the entries of a large m × n matrix, when provided with a small, random fraction of noisy measurements. We assume that all rows u ∈ [m] and columns i ∈ [n] of the matrix are associated to latent features xrow(u) and xcol(i) respectively, and the (u, i)-th entry of the matrix, A(u, i) is equal to f(xrow(u), xcol(i)) for a latent functionf. Given noisy observations of a small, random subset of the matrix entries, our goal is to estimate the unobserved entries of the matrix as well as to “denoise” the observed entries. As the main result of this work, we introduce a nearest-neighbor-based estimation algorithm, and establish its consistency when the underlying latent function f is Lipschitz, the underlying latent space is a bounded diameter Polish space, and the random fraction of observed entries in the matrix is at least max (m-1+δ, n-1/2+δ), for any δ > 0. As an important byproduct, our analysis sheds light into the performance of the classical collaborative filtering algorithm for matrix completion, which has been widely utilized in practice. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides a principled improvement over basic collaborative filtering and is competitive with matrix factorization methods. Our algorithm has a natural extension to the setting of tensor completion via flattening the tensor to matrix. When applied to the setting of image in-painting, which is a 3-order tensor, we find that our approach is competitive with respect to state-of-art tensor completion algorithms across benchmark images.

We consider recommendation systems that need to operate under wireless bandwidth constraints, which is measured as the number of broadcast transmissions. We demonstrate a (tight for some instances) tradeoff between regret and bandwidth for wireless recommendations formulated in a contextual multiarmed bandit framework.

Consider the setting of Linear Regression where the observed response variables, in expectation, are linear functions of the p-dimensional covariates. Then to achieve vanishing prediction error, the number of required samples scales faster than pσ2, where σ2 is a bound on the noise variance. In a high-dimensional setting where p is large but the covariates admit a low-dimensional representation (say r ≪ p), then Principal Component Regression (PCR), cf. [36], is an effective approach; here, the response variables are regressed with respect to the principal components of the covariates. The resulting number of required samples to achieve vanishing prediction error now scales faster than rσ2(≪ pσ2). Despite the tremendous utility of PCR, its ability to handle settings with noisy, missing, and mixed (discrete and continuous) valued covariates is not understood and remains an important open challenge, cf. [24]. As the main contribution of this work, we address this challenge by rigorously establishing that PCR is robust to noisy, sparse, and possibly mixed valued covariates. Specifically, under PCR, vanishing prediction error is achieved with the number of samples scaling as r max(σ2, ρ−4 log5(p)), where ρ denotes the fraction of observed (noisy) covariates. We establish generalization error bounds on the performance of PCR, which provides a systematic approach in selecting the correct number of components r in a data-driven manner. The key to our result is a simple, but powerful equivalence between (i) PCR and (ii) Linear Regression with covariate pre-processing via Hard Singular Value Thresholding (HSVT). From a technical standpoint, this work advances the state-of-the-art analysis for HSVT by establishing stronger guarantees with respect to the ∥·∥2,∞-error for the estimated matrix rather than the Frobenius norm/mean-squared error (MSE) as is commonly done in the matrix estimation / completion literature.

Inferring the correct answers to binary tasks based on multiple noisy answers in an unsupervised manner has emerged as the canonical question for micro-task crowdsourcing or more generally aggregating opinions. In graphon estimation, one is interested in estimating edge intensities or probabilities between nodes using a single snapshot of a graph realization. In the recent literature, there has been exciting development within both of these topics. In the context of crowdsourcing, the key intellectual challenge is to understand whether a given task can be more accurately denoised by aggregating answers collected from other different tasks. In the context of graphon estimation, precise information limits and estimation algorithms remain of interest. In this paper, we utilize a statistical reduction from crowdsourcing to graphon estimation to advance the state-of-art for both of these challenges. We use concepts from graphon estimation to design an algorithm that achieves better performance than the majority voting scheme for a setup that goes beyond the rank one models considered in the literature. We use known lower bounds for crowdsourcing to derive lower bounds for graphon estimation.

We consider wireless recommender systems that need to learn the user preferences (explore) and use them to accordingly decide what are the most profitable recommendations to make (exploit), under bandwidth constraints. We propose a graph-based scheme that leverages user side information and coding to efficiently exploit and explore over wireless, and evaluate its performance.

We consider model-free reinforcement learning for infinite-horizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernel, when only a single sample path under an arbitrary policy of the system is available. We consider the Nearest Neighbor Q-Learning (NNQL) algorithm to learn the optimal Q function using nearest neighbor regression method. As the main contribution, we provide tight finite sample analysis of the convergence rate. In particular, for MDPs with a $d$-dimensional state space and the discounted factor $\gamma \in (0,1)$, given an arbitrary sample path with ``covering time'' $L$, we establish that the algorithm is guaranteed to output an $\varepsilon$-accurate estimate of the optimal Q-function using $\Ot(L/(\varepsilon^3(1-\gamma)^7))$ samples. For instance, for a well-behaved MDP, the covering time of the sample path under the purely random policy scales as $\Ot(1/\varepsilon^d),$ so the sample complexity scales as $\Ot(1/\varepsilon^{d+3}).$ Indeed, we establish a lower bound that argues that the dependence of $ \Omegat(1/\varepsilon^{d+2})$ is necessary.

We present a robust generalization of the synthetic control method for comparative case studies. Like the classical method cf. \cite{abadie3}, we present an algorithm to estimate the unobservable counterfactual of a treatment unit. A distinguishing feature of our algorithm is that of de-noising the data matrix via singular value thresholding, which renders our approach robust in multiple facets: it automatically identifies a good subset of donors for the synthetic control, overcomes the challenges of missing data, and continues to work well in settings where covariate information may not be provided. We posit that the setting can be viewed as an instance of the Latent Variable Model and provide the first finite sample analysis (coupled with asymptotic results) for the estimation of the counterfactual. Our algorithm accurately imputes missing entries and filters corrupted observations in producing a consistent estimator of the underlying signal matrix, provided $p = \Omega( T^{-1 + \zeta})$ for some $\zeta > 0$; here, $p$ is the fraction of observed data and $T$ is the time interval of interest. Under the same proportion of observations, we demonstrate that the mean-squared error in our counterfactual estimation scales as $\mathcal{O}(\sigma^2/p + 1/\sqrt{T})$, where $\sigma^2$ is the variance of the inherent noise. Additionally, we introduce a Bayesian framework to quantify the estimation uncertainty. Our experiments, using both synthetic and real-world datasets, demonstrate that our robust generalization yields an improvement over the classical synthetic control method.

Estimating a matrix based on partial, noisy observations is prevalent in variety of modern applications with recommendation system being a prototypical example. The non-parametric latent variable model provides canonical representation for such matrix data when the underlying distribution satisfies ``exchangeability'' with graphons and stochastic block model being recent examples of interest. Collaborative filtering has been a successfully utilized heuristic in practice since the dawn of e-commerce. In this extended abstract, we will argue that collaborative filtering (and its variants) solve matrix estimation for a generic latent variable model with near optimal sample complexity.

The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering-style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to $0$ at the rate of $O(d^2 (pn)^{-2/5})$ as long as $\omega(d^5 n)$ random entries from a total of $n^2$ entries of $Y$ are observed (uniformly sampled), $\E[Y]$ has rank $d$, and the entries of $Y$ have bounded support. The maximum squared error across all entries converges to $0$ with high probability as long as we observe a little more, $\Omega(d^5 n \ln^5(n))$ entries. Our results are the best known sample complexity results in this generality.

Current approaches to the practical implementation of network coding are batch-based, and often do not use feedback, except possibly to signal completion of a file download. In this paper, the various benefits of using feedback in a network coded system are studied. It is shown that network coding can be performed in a completely online manner, without the need for batches or generations, and that such online operation does not affect the throughput. Although these ideas are presented in a single-hop packet erasure broadcast setting, they naturally extend to more general lossy networks, which employ network coding in the presence of feedback. The impact of feedback on sender-side queue size and receiver-side decoding delay is studied in an asymptotic sense as the traffic load approaches capacity. Different notions of decoding delay are considered, including an order-sensitive notion, which assumes that packets are useful only when delivered in order. Strategies for adaptive coding based on feedback are presented. Our scheme achieves throughput optimality and asymptotically optimal sender queue size and is conjectured to achieve asymptotically optimal in-order delivery delay for any number of receivers. This paper may be viewed as a natural extension of Automatic Repeat reQuest to coded networks.

In this talk, we shall discuss the question of learning distribution over permutations of n choices based on partial observations. This is central to capturing the so called "choice" in a variety of contexts: understanding preferences of consumers over a collection of products based on purchasing and browsing data in the setting of retail and e-commerce, learning public opinion amongst a collection of socio-economic issues based on sparse polling data, and deciding a ranking of teams or players based on outcomes of games. The talk will primarily discuss the relationship between the ability to learn, nature of partial information and number of available observations. Connections to the classical theory of social choice and behavioral psychology, as well as modern literature in Statistics, learning theory and operations research will be discussed.

We introduce the framework of {\em blind regression} motivated by {\em matrix completion} for recommendation systems: given $m$ users, $n$ movies, and a subset of user-movie ratings, the goal is to predict the unobserved user-movie ratings given the data, i.e., to complete the partially observed matrix. Following the framework of non-parametric statistics, we posit that user $u$ and movie $i$ have features $x_1(u)$ and $x_2(i)$ respectively, and their corresponding rating $y(u,i)$ is a noisy measurement of $f(x_1(u), x_2(i))$ for some unknown function $f$. In contrast with classical regression, the features $x = (x_1(u), x_2(i))$ are not observed, making it challenging to apply standard regression methods to predict the unobserved ratings. Inspired by the classical Taylor's expansion for differentiable functions, we provide a prediction algorithm that is consistent for all Lipschitz functions. In fact, the analysis through our framework naturally leads to a variant of collaborative filtering, shedding insight into the widespread success of collaborative filtering in practice. Assuming each entry is sampled independently with probability at least $\max(m^{-1+\delta},n^{-1/2+\delta})$ with $\delta > 0$, we prove that the expected fraction of our estimates with error greater than $\epsilon$ is less than $\gamma^2 / \epsilon^2$ plus a polynomially decaying term, where $\gamma^2$ is the variance of the additive entry-wise noise term. Experiments with the MovieLens and Netflix datasets suggest that our algorithm provides principled improvements over basic collaborative filtering and is competitive with matrix factorization methods.

There is much empirical evidence that item-item collaborative filtering works well in practice. Motivated to understand this, we provide a framework to design and analyze various recommendation algorithms. The setup amounts to online binary matrix completion, where at each time a random user requests a recommendation and the algorithm chooses an entry to reveal in the user's row. The goal is to minimize regret, or equivalently to maximize the number of +1 entries revealed at any time. We analyze an item-item collaborative filtering algorithm that can achieve fundamentally better performance compared to user-user collaborative filtering. The algorithm achieves good "cold-start" performance (appropriately defined) by quickly making good recommendations to new users about whom there is little information.

An ideal datacenter network should provide several properties, including low median and tail latency, high utilization (throughput), fair allocation of network resources between users or applications, deadline-aware scheduling, and congestion (loss) avoidance. Current datacenter networks inherit the principles that went into the design of the Internet, where packet transmission and path selection decisions are distributed among the endpoints and routers. Instead, we propose that each sender should delegate control---to a centralized arbiter---of when each packet should be transmitted and what path it should follow.

Computing a ranking over choices using consumer data gathered from a heterogenous population has become an indispensable module for any modern consumer information system, e.g. Yelp, Netflix, Amazon and app-stores like Google play. In such applications, a ranking or recommendation algorithm needs to extract meaningful information from noisy data accurately and in a scalable manner. A principled approach to resolve this challenge requires a model that connects observations to recommendation decisions and a tractable inference algorithm utilizing this model. To that end, we abstract the preference data generated by consumers as noisy, partial realizations of their innate preferences, i.e. orderings or permutations over choices. Inspired by the seminal works of Samuelson (cf. axiom of revealed preferences) and that of McFadden (cf. discrete choice models for transportation), we model the population's innate preferences as a mixture of the so called Multi-nomial Logit (MMNL) model. Under this model, the recommendation problem boils down to (a) learning the MMNL model from population data, (b) finding am MNL component within the mixture that closely represents the revealed preferences of the consumer at hand, and (c) recommending other choices to her/him that are ranked high according to thus found component. In this work, we address the problem of learning MMNL model from partial preferences. We identify fundamental limitations of any algorithm to learn such a model as well as provide conditions under which, a simple, data-driven (non-parametric) algorithm learns the model effectively. The proposed algorithm has a pleasant similarity to the standard collaborative filtering for scalar (or star) ratings, but in the domain of permutations. This work advances the state-of-art in the domain of learning distribution over permutations (cf. [2]) as well as in the context of learning mixture distributions (cf. [4]).

For classifying time series, a nearest-neighbor approach is widely used in practice with performance often competitive with or better than more elaborate methods such as neural networks, decision trees, and support vector machines. We develop theoretical justification for the effectiveness of nearest-neighbor-like classification of time series. Our guiding hypothesis is that in many applications, such as forecasting which topics will become trends on Twitter, there aren't actually that many prototypical time series to begin with, relative to the number of time series we have access to, e.g., topics become trends on Twitter only in a few distinct manners whereas we can collect massive amounts of Twitter data. To operationalize this hypothesis, we propose a latent source model for time series, which naturally leads to a weighted majority voting" classification rule that can be approximated by a nearest-neighbor classifier. We establish nonasymptotic performance guarantees of both weighted majority voting and nearest-neighbor classification under our model accounting for how much of the time series we observe and the model complexity. Experimental results on synthetic data show weighted majority voting achieving the same misclassification rate as nearest-neighbor classification while observing less of the time series. We then use weighted majority to forecast which news topics on Twitter become trends, where we are able to detect such "trending topics" in advance of Twitter 79% of the time, with a mean early advantage of 1 hour and 26 minutes, a true positive rate of 95%, and a false positive rate of 4%."

Computing the stationary distribution of a large finite or countably infinite state space Markov Chain (MC) has become central in many problems such as statistical inference and network analysis. Standard methods involve large matrix multiplications as in power iteration, or simulations of long random walks to sample states from the stationary distribution, as in Markov Chain Monte Carlo (MCMC). However these methods are computationally costly; either they involve operations at every state or they scale (in computation time) at least linearly in the size of the state space. In this paper, we provide a novel algorithm that answers whether a chosen state in a MC has stationary probability larger than some $\Delta \in (0,1)$. If so, it estimates the stationary probability. Our algorithm uses information from a local neighborhood of the state on the graph induced by the MC, which has constant size relative to the state space. We provide correctness and convergence guarantees that depend on the algorithm parameters and mixing properties of the MC. Simulation results show MCs for which this method gives tight estimates.

Crowdsourcing systems like Amazon's Mechanical Turk have emerged as an effective large-scale human-powered platform for performing tasks in domains such as image classification, data entry, recommendation, and proofreading. Since workers are low-paid (a few cents per task) and tasks performed are monotonous, the answers obtained are noisy and hence unreliable. To obtain reliable estimates, it is essential to utilize appropriate inference algorithms (e.g. Majority voting) coupled with structured redundancy through task assignment. Our goal is to obtain the best possible trade-off between reliability and redundancy. In this paper, we consider a general probabilistic model for noisy observations for crowd-sourcing systems and pose the problem of minimizing the total price (i.e. redundancy) that must be paid to achieve a target overall reliability. Concretely, we show that it is possible to obtain an answer to each task correctly with probability 1-ε as long as the redundancy per task is O((K/q) log (K/ε)), where each task can have any of the $K$ distinct answers equally likely, q is the crowd-quality parameter that is defined through a probabilistic model. Further, effectively this is the best possible redundancy-accuracy trade-off any system design can achieve. Such a single-parameter crisp characterization of the (order-)optimal trade-off between redundancy and reliability has various useful operational consequences. Further, we analyze the robustness of our approach in the presence of adversarial workers and provide a bound on their influence on the redundancy-accuracy trade-off.

This brief presents a technique to evaluate the timing variation of static random access memory (SRAM). Specifically, a method called loop flattening, which reduces the evaluation of the timing statistics in the complex highly structured circuit to that of a single chain of component circuits, is justified. Then, to very quickly evaluate the timing delay of a single chain, a statistical method based on importance sampling augmented with targeted high-dimensional spherical sampling can be employed. The overall methodology has shown 650× or greater speedup over the nominal Monte Carlo approach with 10.5% accuracy in probability. Examples based on both the large-signal and small-signal SRAM read path are discussed, and a detailed comparison with state-of-the-art accelerated statistical simulation techniques is given.

Spinal codes are a recently proposed capacity-achieving rateless code. While hardware encoding of spinal codes is straightforward, the design of an efficient, high-speed hardware decoder poses significant challenges. We present the first such decoder. By relaxing data dependencies inherent in the classic M-algorithm decoder, we obtain area and throughput competitive with 3GPP turbo codes as well as greatly reduced latency and complexity. The enabling architectural feature is a novel alpha-beta incremental approximate selection algorithm. We also present a method for obtaining hints which anticipate successful or failed decoding, permitting early termination and/or feedback-driven adaptation of the decoding parameters.

Recently, rateless codes have introduced a promising approach to obtaining wireless throughput higher than what is achieved by fixed-rate codes, especially over time-varying channels. Rateless codes like Raptor, Strider, and spinal codes naturally process all the information available at the receiver corresponding to a packet, whether from one or many frame transmissions. However, a profitable deployment of rateless codes in a wireless network requires a link-layer protocol to coordinate between sender and receiver. This protocol needs to determine how much coded data should be sent before the sender pauses for feedback from the receiver. Without such feedback, an open-loop sender would not know when the packet has been decoded, but sending this feedback is not free and consumes a significant fraction of the packet transmission time. This paper develops RateMore, a protocol that learns the probability distribution of the number of symbols required to decode a packet (the decoding CDF), and uses the learned distribution in a dynamic programming strategy to produce an optimal transmission schedule. Our experiments show that RateMore reduces overhead by between 2.6x and 3.9x compared to 802.11-style ARQ and between 2.8x and 5.4x compared to 3GPP-style "Try-after-n" HARQ.

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g. MSR’s TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining ranking, finding ‘scores’ for each object (e.g. player’s rating) is of interest to understanding the intensity of the preferences. In this paper, we propose a novel iterative rank aggregation algorithm for discovering scores for objects from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1].

Spinal codes are a new class of rateless codes that enable wireless networks to cope with time-varying channel conditions in a natural way, without requiring any explicit bit rate selection. The key idea in the code is the sequential application of a pseudo-random hash function to the message bits to produce a sequence of coded symbols for transmission. This encoding ensures that two input messages that differ in even one bit lead to very different coded sequences after the point at which they differ, providing good resilience to noise and bit errors. To decode spinal codes, this paper develops an approximate maximum-likelihood decoder, called the bubble decoder, which runs in time polynomial in the message size and achieves the Shannon capacity over both additive white Gaussian noise (AWGN) and binary symmetric channel (BSC) models. Experimental results obtained from a software implementation of a linear-time decoder show that spinal codes achieve higher throughput than fixed-rate LDPC codes, rateless Raptor codes, and the layered rateless coding approach of Strider, across a range of channel conditions and message sizes. An early hardware prototype that can decode at 10 Mbits/s in FPGA demonstrates that spinal codes are a practical construction.

The need to rank items based on user input arises in many practical applications such as elections, group decision making and recommendation systems. The primary challenge in such scenarios is to decide on a global ranking based on partial preferences provided by users. The standard approach to address this challenge is to ask users to provide explicit numerical ratings (cardinal information) of a subset of the items. The main appeal of such an approach is the ease of aggregation. However, the rating scale as well as the individual ratings are often arbitrary and may not be consistent from one user to another. A more natural alternative to numerical ratings requires users to compare pairs of items (ordinal information). On the one hand, such comparisons provide an "absolute" indicator of the user's preference. On the other hand, it is often hard to combine or aggregate these comparisons to obtain a consistent global ranking.

This paper looks at the problem of designing medium access algorithm for wireless networks with the objective of providing high throughput and low delay performance to the users, while requiring only a modest computational effort at the transmitters and receivers. Additive inter-user interference at the receivers is an important physical layer characteristic of wireless networks. Today's Wi-Fi networks are based upon the abstraction of physical layer where inter-user interference is considered as noise leading to the 'collision' model in which users are required to co-ordinate their transmissions through Carrier Sensing Multiple Access (CSMA)-based schemes to avoid interference. This, in turn, leads to an inherent performance trade-off [1]: it is impossible to obtain high throughput and low delay by means of low complexity medium access algorithm (unless P=NP). As the main result, we establish that this trade-off is primarily due to treating interference as noise in the current wireless architecture. Concretely, we develop a simple medium access algorithm that allows for simultaneous transmissions of users to the same receiver by performing joint decoding at receivers, over time. For a receiver to be able to decode multiple transmissions quickly enough, we develop appropriate congestion control where each transmitter maintains a "window" of undecoded transmitted data that is adjusted based upon the "feedback" from the receiver. In summary, this provides an efficient, low complexity "online" code operating at varying rate, and the system as a whole experiences only small amount of delay (including decoding time) while operating at high throughput.

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 of this paper, 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.

We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor centrality as an estimator for detecting the source. They establish it to be the maximum likelihood estimator with respect to the popular Susceptible Infected (SI) model with exponential spreading time for regular trees. They showed that as the size of infected graph increases, for a line (2-regular tree) graph, the probability of source detection goes to 0 while for d-regular trees with d ≥ 3 the probability of detection, say αd, remains bounded away from 0 and is less than 1/2. Their results, however stop short of providing insights for the heterogeneous setting such as irregular trees or the SI model with non-exponential spreading times.

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. The network performance is described by the 2n× n-dimensional caching capacity region of the wireless network. We provide an inner bound on this caching capacity region, and, in the high path-loss regime, a matching (in the scaling sense) outer bound. For large path-loss exponent, this provides an information-theoretic scaling characterization of the entire caching capacity region. The proposed communication scheme achieving the inner bound shows that the problems of cache selection and channel coding can be solved separately without loss of order-optimality. On the other hand, our results show that the common architecture of nearest-neighbor cache selection can be arbitrarily bad, implying that cache selection and load balancing need to be performed jointly.

Consider a wireless network of n nodes represented by a (undirected) graph G where an edge (i,j) models the fact that transmissions of i and j interfere with each other, i.e. simultaneous transmissions of i and j become unsuccessful. Hence it is required that at each time instance a set of non-interfering nodes (corresponding to an independent set in G) access the wireless medium. To utilize wireless resources efficiently, it is required to arbitrate the access of medium among interfering nodes properly. Moreover, to be of practical use, such a mechanism is required to be totally distributed as well as simple. As the main result of this paper, we provide such a medium access algorithm. It is randomized, totally distributed and simple: each node attempts to access medium at each time with probability that is a function of its local information. We establish efficiency of the algorithm by showing that the corresponding network Markov chain is positive recurrent as long as the demand imposed on the network can be supported by the wireless network (using any algorithm). In that sense, the proposed algorithm is optimal in terms of utilizing wireless resources. The algorithm is oblivious to the network graph structure, in contrast with the so-called polynomial back-off algorithm by Hastad-Leighton-Rogoff (STOC '87, SICOMP '96) that is established to be optimal for the complete graph and bipartite graphs (by Goldberg-MacKenzie (SODA '96, JCSS '99)).

A fundamental problem in wireless networks is to develop communication protocols that achieve high throughput in the face of noise, interference, and fading, all of which vary with time. An ideal solution is a rateless wireless system, in which the sender encodes data without any explicit estimation or adaptation, implicitly adapting to the level of noise or interference. In this paper, we present a novel rateless code, the spinal code, which uses a hash function over the message bits to produce pseudo-random bits that in turn can be mapped directly to a dense constellation for transmission. Results from theoretical analysis and simulations show that spinal codes essentially achieve Shannon capacity, and out-perform best-known fixed rate block codes.

We are interested in the following question: given n numbers x1, ..., xn, what sorts of approximation of average xave= 1overn (x1+ ... + xn) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of xavethat is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging.

Crowdsourcing systems, in which tasks are electronically distributed to numerous ``information piece-workers'', have emerged as an effective paradigm for human-powered solving of large scale problems in domains such as image classification, data entry, optical character recognition, recommendation, and proofreading. Because these low-paid workers can be unreliable, nearly all crowdsourcers must devise schemes to increase confidence in their answers, typically by assigning each task multiple times and combining the answers in some way such as majority voting. In this paper, we consider a general model of such rowdsourcing tasks, and pose the problem of minimizing the total price (i.e., number of task assignments) that must be paid to achieve a target overall reliability. We give new algorithms for deciding which tasks to assign to which workers and for inferring correct answers from the workers’ answers. We show that our algorithm significantly outperforms majority voting and, in fact, are asymptotically optimal through comparison to an oracle that knows the reliability of every worker.

The theory of network coding promises significant benefits in network performance, especially in lossy networks and in multicast and multipath scenarios. To realize these benefits in practice, we need to understand how coding across packets interacts with the acknowledgment (ACK)-based flow control mechanism that forms a central part of today's Internet protocols such as transmission control protocol (TCP). Current approaches such as rateless codes and batch-based coding are not compatible with TCP's retransmission and sliding-window mechanisms. In this paper, we propose a new mechanism called TCP/NC that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs-the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Thus, our new TCP ACK rule takes into account the network coding operations in the lower layer and enables a TCP-compatible sliding-window approach to network coding. Coding essentially masks losses from the congestion control algorithm and allows TCP/NC to react smoothly to losses, resulting in a novel and effective approach for congestion control over lossy networks such as wireless networks. An important feature of our solution is that it allows intermediate nodes to perform re-encoding of packets, which is known to provide significant throughput gains in lossy networks and multicast scenarios. Simulations show that our scheme, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We present a real-world implementation of this protocol that addresses the practical aspects of incorporating network coding and decoding with TCP's window management mechanism. We work with TCP-Reno, which is a widespread and practical variant of TCP. Our implementation significantly advances the goal of designing a deployable, general, TCP-compatible protocol that provides the benefits of network coding.

We consider the #P-complete problem of counting the number of independent sets in a given graph. Our interest is in understanding the effectiveness of the popular belief propagation (BP) heuristic. BP is a simple iterative algorithm that is known to have at least one fixed point, where each fixed point corresponds to a stationary point of the Bethe free energy (introduced by Yedidia, Freeman, and Weiss [IEEE Trans. Inform. Theory, 51 (2004), pp. 2282–2312] in recognition of Bethe’s earlier work in 1935). The evaluation of the Bethe free energy at such a stationary point (or BP fixed point) leads to the Bethe approximation for the number of independent sets of the given graph. BP is not known to converge in general, nor is an efficient, convergent procedure for finding stationary points of the Bethe free energy known. Furthermore, the effectiveness of the Bethe approximation is not well understood. As the first result of this paper we propose a BP-like algorithm that always converges to a stationary point of the Bethe free energy for any graph for the independent set problem. This procedure finds an [Formula: see text]-approximate stationary point in [Formula: see text] iterations for a graph of [Formula: see text] nodes with max-degree [Formula: see text]. We study the quality of the resulting Bethe approximation using the recently developed “loop series” framework of Chertkov and Chernyak [J. Stat. Mech. Theory Exp., 6 (2006), P06009]. As this characterization is applicable only for exact stationary points of the Bethe free energy, we provide a slightly modified characterization that holds for [Formula: see text]-approximate stationary points. We establish that for any graph on [Formula: see text] nodes with max-degree [Formula: see text] and girth larger than [Formula: see text], the multiplicative error between the number of independent sets and the Bethe approximation decays as [Formula: see text] for some [Formula: see text]. This provides a deterministic counting algorithm that leads to strictly different results compared to a recent result of Weitz [in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2006, pp. 140–149]. Finally, as a consequence of our analysis we prove that the Bethe approximation is exceedingly good for a random 3-regular graph conditioned on the shortest cycle cover conjecture of Alon and Tarsi [SIAM J. Algebr. Discrete Methods, 6 (1985), pp. 345–350] being true.

Core-to-core variability in future many-core chip multi-processors (CMPs) negatively impacts energy. Under-performing cores necessitate increasing the system voltage to maintain homogeneous core performance, introducing an energy overhead. Multiple supply voltages can be used to mitigate the impact of delay variation in CMPs. In this paper, we carefully analyze the use of a local search algorithm to pick near-optimal supply voltages while meeting a fixed performance target. With two system voltages, we prove our algorithm selects the global optimum and in the more general multiple voltage case we develop quantitative bounds. Using a custom simulation methodology on a real processor core, we show that two system voltages provide the most incremental benefit, reducing the energy overhead relative to a single voltage by 59-75% and total energy by 6-16%. Additionally, the worst 5-15% of cores in such systems necessitate increasingly larger amounts of incremental energy for a constant incremental performance gain. Therefore, turning off or disabling these cores is beneficial to a joint performance-energy metric.

We consider the problem of designing a fair scheduling algorithm for discrete-time constrained queuing networks. Each queue has dedicated exogenous packet arrivals. There are constraints on which queues can be served simultaneously. This model effectively describes important special instances like network switches, interference in wireless networks, bandwidth sharing for congestion control and traffic scheduling in road roundabouts. Fair scheduling is required because it provides isolation to different traffic flows; isolation makes the system more robust and enables providing quality of service. Existing work on fairness for constrained networks concentrates on flow based fairness. As a main result, we describe a notion of packet based fairness by establishing an analogy with the ranked election problem: packets are voters, schedules are candidates, and each packet ranks the schedules based on its priorities. We then obtain a scheduling algorithm that achieves the described notion of fairness by drawing upon the seminal work of Goodman and Markowitz (1952). This yields the familiar Maximum Weight (MW) style algorithm. As another important result, we prove that the algorithm obtained is throughput optimal. There is no reason a priori why this should be true, and the proof requires nontraditional methods.

We consider the problem of recovering a function over the space of permutations (or, the symmetric group) over$n$elements from given partial information; the partial information we consider is related to the group theoretic Fourier Transform of the function. This problem naturally arises in several settings such as ranked elections, multi-object tracking, ranking systems, and recommendation systems. Inspired by the work of Donoho and Stark in the context of discrete-time functions, we focus on non-negative functions with a sparse support (support size$\ll$domain size). Our recovery method is based on finding the sparsest solution (through$\ell_0$optimization) that is consistent with the available information. As the main result, we derive sufficient conditions for functions that can be recovered exactly from partial information through$\ell_0$optimization. Under a natural random model for the generation of functions, we quantify the recoverability conditions by deriving bounds on the sparsity (support size) for which the function satisfies the sufficient conditions with a high probability as$n \to \infty$.$\ell_0$optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation,$\ell_1$optimization, to find the sparsest solution. However, we show that$\ell_1$optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as$n \to \infty$. In order to overcome this problem, we propose a novel iterative algorithm for the recovery of functions that satisfy the sufficient conditions. Finally, using an Information Theoretic framework, we study necessary conditions for exact recovery to be possible.

We consider a communication network and study the problem of designing a high-throughput and low-delay scheduling policy that only requires a polynomial amount of computation at each time step. The well-known maximum weight scheduling policy, proposed by Tassiulas and Ephremides (1992), has favorable performance in terms of throughput and delay but, for general networks, it can be computationally very expensive. A related randomized policy proposed by Tassiulas (1998) provides maximal throughput with only a small amount of computation per step, but seems to induce exponentially large average delay. These considerations raise some natural questions. Is it possible to design a policy with low complexity, high throughput, and low delay for a general network? Does Tassiulas' randomized policy result in low average delay? In this paper, we answer both of these questions negatively. We consider a wireless network operating under two alternative interference models: (a) a combinatorial model involving independent set constraints and (b) the standard SINR (signal to interference noise ratio) model. We show that unlessNP⊆BPP(orP=NPfor the case of determistic arrivals and deterministic policies), and even if the required throughput is a very small fraction of the network's capacity, there does not exist a low-delay policy whose computation per time step scales polynomially with the number of queues. In particular, the average delay of Tassiulas' randomized algorithm must grow super-polynomially. To establish our results, we employ a clever graph transformation introduced by Lund and Yannakakis (1994).

We provide a systematic study of the problem of finding the source of a rumor in a network. We model rumor spreading in a network with the popular susceptible-infected (SI) model and then construct an estimator for the rumor source. This estimator is based upon a novel topological quantity which we term rumor centrality. We establish that this is a maximum likelihood (ML) estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has nontrivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops of the true source across different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding rumor sources in networks which are not tree-like.

The impact of process variation in deep-submicron technologies is especially pronounced for SRAM architectures which must meet demands for higher density and higher performance at increased levels of integration. Due to the complex structure of SRAM, estimating the effect of process variation accurately has become very challenging. In this paper, we address this challenge in the context of estimating SRAM timing variation. Specifically, we introduce a method called loop flattening that demonstrates how the evaluation of the timing statistics in the complex, highly structured circuit can be reduced to that of a single chain of component circuits. To then very quickly evaluate the timing delay of a single chain, we employ a statistical method based on importance sampling augmented with targeted, high-dimensional, spherical sampling. Overall, our methodology provides an accurate estimation with 650X or greater speed-up over the nominal Monte Carlo approach.

In the recent years, message-passing paradigm has emerged as a canonical algorithmic solution to solve networkwide problems by means of minimal local information exchange, across variety of disciplines. The primary purpose of this work is to understand tradeoffs offered between network performance and protocol overhead by a class of message-passing algorithms - belief propagation and its variants. Through an extensive simulation study, for prototypical network topological models, we find that such class can lead to wireless network scheduling algorithms under which each node exchanges exactly one message per time-slot and achieve reasonably high performance. This algorithm utilizes the "continuity" of network state to achieve high performance in presence of minimal information exchange.

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A ∈ {0, 1}m×n. We establish that when A corresponds to the adjacency matrix of a bipartite graph with sufficient expansion, a simple message-passing algorithm produces an estimate x^ of x satisfying ∥x-x^∥1≤ O(n/k) ∥x-x(k)∥1, where x(k)is the best k-sparse approximation of x. The algorithm performs O(n(log(n/k))2log (k)) computation in total, and the number of measurements required is m = O(k log(n/k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n/k) log(k)). Ultimately, this work is a further step in the direction of more formally developing the broader role of message-passing algorithms in solving compressed sensing problems.

The packet is the fundamental unit of transportation in modern communication networks such as the Internet. Physical layer scheduling decisions are made at the level of packets, and packet-level models with exogenous arrival processes have long been employed to study network performance, as well as design scheduling policies that more efficiently utilize network resources. On the other hand, a user of the network is more concerned with end-to-end bandwidth, which is allocated through congestion control policies such as TCP. Utility-based flow-level models have played an important role in understanding congestion control protocols. In summary, these two classes of models have provided separate insights for flow-level and packet-level dynamics of a network. In this paper, we wish to study these two dynamics together. We propose a joint flow-level and packet-level stochastic model for the dynamics of a network, and an associated policy for congestion control and packet scheduling that is based on alpha-weighted policies from the literature. We provide a fluid analysis for the model that establishes the throughput optimality of the proposed policy, thus validating prior insights based on separate packet-level and flow-level models. By analyzing a critically scaled fluid model under the proposed policy, we provide constant factor performance bounds on the delay performance and characterize the invariant states of the system.

Distributed averaging is a well-studied problem, and often a prototype for a class of fundamental questions arising in various disciplines. Previous work has considered the effect of dynamics in the network topology, in terms of changes in which communication links are present. Here, we analyze the other forms of dynamics, namely: changes in the values at the nodes, and nodes joining or leaving the network.

Game theoretic modeling and equilibrium analysis of congestion games have provided insights in the performance of Internet congestion control, road transportation networks, etc. Despite the long history, very little is known about their transient (non equilibrium) performance. In this paper, we are motivated to seek answers to questions such as how long does it take to reach equilibrium, when the system does operate near equilibrium in the presence of dynamics, e.g. nodes join or leave. , or the tradeoff between performance and the rate of dynamics. In this pursuit, we provide three contributions in this paper. First, a novel probabilistic model to capture realistic behaviors of agents allowing for the possibility of arbitrariness in conjunction with rationality. Second, evaluation of (a) time to converge to equilibrium under this behavior model and (b) distance to Nash equilibrium. Finally, determination of tradeoff between the rate of dynamics and quality of performance (distance to equilibrium) which leads to an interesting uncertainty principle. The novel technical ingredients involve analysis of logarithmic Sobolov constant of Markov process with time varying state space and methodically this should be of broader interest in the context of dynamical systems.

In the past year or so, an exciting progress has led to throughput optimal design of CSMA-based algorithms for wireless networks. However, such an algorithm suffers from very poor delay performance. A recent work suggests that it is impossible to design a CSMA-like simple algorithm that is throughput optimal and induces low delay for any wireless network. However, wireless networks arising in practice are formed by nodes placed, possibly arbitrarily, in some geographic area.

We consider a switched network, a fairly general constrained queueing network model that has been used successfully to model the detailed packet-level dynamics in communication networks, such as input-queued switches and wireless networks. The main operational issue in this model is that of deciding which queues to serve, subject to certain constraints.

We provide a systematic study of the problem of finding the source of a computer virus in a network. We model virus spreading in a network with a variant of the popular SIR model and then construct an estimator for the virus source. This estimator is based upon a novel combinatorial quantity which we term rumor centrality. We establish that this is an ML estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has non-trivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops in different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding virus sources in networks which are not tree-like.

We formulate a Belief Propagation (BP) algorithm in the context of the capacitated minimum-cost network flow problem (ℳ ℱ). Unlike most of the instances of BP studied in the past, the messages of BP in the context of this problem are piecewise-linear functions. We prove that BP converges to the optimal solution in pseudo-polynomial time, provided that the optimal solution is unique and the problem input is integral. Moreover, we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS) for ℳ ℱ. This is the first instance where BP is proved to have fully-polynomial running time.

A network of nodes communicate via point-to-point memoryless independent noisy channels. Each node has some real-valued initial measurement or message. The goal of each of the nodes is to acquire an estimate of a given function of all the initial measurements in the network. As the main contribution of this paper, a lower bound on computation time is derived. This bound must be satisfied by any algorithm used by the nodes to communicate and compute, so that the mean-square error in the nodes' estimate is within a given interval around zero. The derivation utilizes information theoretic inequalities reminiscent of those used in rate distortion theory along with a novel “perturbation” technique so as to be broadly applicable. To understand the tightness of the bound, a specific scenario is considered. Nodes are required to learn a linear combination of the initial values in the network while communicating over erasure channels. A distributed quantized algorithm is developed, and it is shown that the computation time essentially scales as is implied by the lower bound. In particular, the computation time depends reciprocally on “conductance”, which is a property of the network that captures the information-flow bottleneck. As a by-product, this leads to a quantized algorithm, for computing separable functions in a network, with minimal computation time.

Motivated by applications to sensor networks and privacy preserving databases, we consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary but fixed deterministic function of those sources can be computed given the compressed data from each source. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder; 2) under a special condition, lossless computation where both sources are separately encoded; and 3) lossy computation where one source is available at the decoder. For all of these instances, we present a layered architecture for distributed coding: first preprocess data at each source using colorings of certain characteristic graphs and then use standard distributed source coding (a laSlepian and Wolfs scheme) to compress them. For the first instance, our results extend the approach developed by Orlitsky and Roche (2001) in the sense that our scheme requires simpler structure of coloring rather than independent sets as in the previous case. As an intermediate step to obtain these results, we obtain an asymptotic characterization of conditional graph coloring for an OR product of graphs generalizing a result of Korner (1973), which should be of interest in its own right.

This paper provides proofs of the rate stability, Harris recurrence, and ε-optimality of carrier sense multiple access (CSMA) algorithms where the random access (or backoff) parameter of each node is adjusted dynamically. These algorithms require only local information and they are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities, in terms of the rates, of the packet flows at different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the ε-optimality in terms of the utilities of the allocated rates. Both algorithms are iterative and we study two versions of each of them. In the first version, both operate with strictly local information but have relatively weaker performance guarantees; under the second version, both provide stronger performance guarantees by utilizing the additional information of the number of nodes in the network.

Motivated by applications of distributed linear estimation, distributed control, and distributed optimization, we consider the question of designing linear iterative algorithms for computing the average of numbers in a network. Specifically, our interest is in designing such an algorithm with the fastest rate of convergence given the topological constraints of the network. As the main result of this paper, we design an algorithm with the fastest possible rate of convergence using a nonreversible Markov chain on the given network graph. We construct such a Markov chain by transforming the standard Markov chain, which is obtained using the Metropolis-Hastings method. We call this novel transformationpseudo-lifting. We apply our method to graphs with geometry, or graphs with doubling dimension. Specifically, the convergence time of our algorithm (equivalently, the mixing time of our Markov chain) is proportional to the diameter of the network graph and hence optimal. As a byproduct, our result provides the fastest mixing Markov chain given the network topological constraints, and should naturally find their applications in the context of distributed optimization, estimation and control.

We consider the question of determining the scaling of then2-dimensional balanced unicast and then2n-dimensional balanced multicast capacity regions of a wireless network withnnodes placed uniformly at random in a square region of areanand communicating over Gaussian fading channels. We identify this scaling of both the balanced unicast and multicast capacity regions in terms of¿(n) , out of2ntotal possible, cuts. These cuts only depend on the geometry of the locations of the source nodes and their destination nodes and the traffic demands between them, and thus can be readily evaluated. Our results are constructive and provide optimal (in the scaling sense) communication schemes.

Unlike the telephone network or the Internet, many of the next generation networks are not engineered for the purpose of providing efficient communication between various networked entities. Examples abound: sensor networks, peer-to-peer networks, mobile networks of vehicles and social networks. Indeed, these emerging networks do require algorithms for communication, computation, or merely spreading information. For example, estimation algorithms in sensor networks, broadcasting news through a peer-to-peer network, or viral advertising in a social network. These networks lack infrastructure; they exhibit unpredictable dynamics and they face stringent resource constraints. Therefore, algorithms operating within them need to be extremely simple, distributed, robust against network dynamics, and efficient in resource utilization. Gossip algorithms, as the name suggests, are built upon a gossip or rumor style unreliable, asynchronous information exchange protocol. Due to their immense simplicity and wide applicability, this class of algorithms has emerged as a canonical architectural solution for the next generation networks. This has led to exciting recent progress to understand the applicability as well as limitations of the gossip algorithms. In this survey, I will discuss some of these recent results on gossip network algorithms. The algorithmic results described here in a natural way bring together tools and techniques from Markov chain theory, optimization, percolation, random graphs, spectral graph theory, and coding.

We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1)factor for general graphs. In this paper, we first show that the whole n2dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

We study the problem of determining the multicast capacity region of a wireless network of n nodes randomly located in an extended area and communicating with each other over Gaussian fading channels. We obtain an explicit information- theoretic characterization of the scaling of the multicast capacity region for n nodes in terms of 2n weighted cuts. These cuts only depend on the geometry of the locations of the source nodes and their destination nodes and the traffic demands between them, and thus can be readily evaluated. The results are constructive and provide a two-layer architecture for achieving nearly the entire multicast capacity region in the scaling sense: The top layer routes traffic from each of the source nodes to its set of destination nodes, and the bottom layer physically distributes/concentrates traffic among appropriate nodes through one of the two cooperative communication schemes - hierarchical relaying and multi-hopping - depending on the wireless-channel characteristics.

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs - the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Such ACKs enable a TCP-compatible sliding-window approach to network coding. Our scheme has the nice property that packet losses are essentially masked from the congestion control algorithm. Our algorithm therefore reacts to packet drops in a smooth manner, resulting in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our scheme also allows intermediate nodes to perform re-encoding of the data packets. Our simulations show that our algorithm, with or without re-encoding inside the network, achieves much higher throughput compared to TCP over lossy wireless links. We also establish the soundness and fairness properties of our algorithm. Finally, we present queuing analysis for the case of intermediate node re-encoding.

Motivated by the recent emergence of large online social networks, we seek to understand the effects the underlying social network (graph) structure and the information dynamics have on the creation of influence of an individual. We examine a natural model for information dynamics under two important temporal scales: a first impression setting and a long- term or equilibrated setting. We obtain a characterization of relevant network structures under these temporal aspects, thereby allowing us to formalize the existence of influential agents. Specifically, we find that the existence of an influential agent corresponds to: (a) strictly positive information theoretic capacity over an infinite-sized noisy broadcast tree network in the first impression case, and (b) positive recurrent property of an appropriate (countable state space) Markov chain in the long-term case. As an application of our results, we evaluate the parameter space of the popular ldquosmall worldrdquo network model to identify when the network structure supports the existence of influential agents.

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. In the most general form, this can be analyzed by considering the 2ntimesn-dimensional caching capacity region of the wireless network. We propose a communication scheme for transmission of messages cached in the network. This provides an inner bound to the caching capacity region.

We visit the following fundamental problem: For a `generic model of consumer choice (namely, distributions over preference lists) and a limited amount of data on how consumers actually make decisions (such as marginal preference information), how may one predict revenues from offering a particular assortment of choices? This problem is central to areas within operations research, marketing and econometrics. We present a framework to answer such questions and design a number of tractable algorithms (from a data and computational standpoint) for the same.

We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.

In recent work, Ozgur, Leveque, and Tse (2007) obtained a complete scaling characterization of throughput scaling for random extended wireless networks (i.e.,nnodes are placed uniformly at random in a square region of arean). They showed that for small path-loss exponentsalphaisin(2,3], cooperative communication is order optimal, and for large path-loss exponentsalpha>3, multihop communication is order optimal. However, their results (both the communication scheme and the proof technique) are strongly dependent on the regularity induced with high probability by the random node placement. In this paper, we consider the problem of characterizing the throughput scaling in extended wireless networks with arbitrary node placement. As a main result, we propose a more general novel cooperative communication scheme that works for arbitrarily placed nodes. For small path-loss exponentsalphaisin(2,3], we show that our scheme is order optimal for all node placements, and achieves exactly the same throughput scaling as in Ozgur. This shows that the regularity of the node placement does not affect the scaling of the achievable rates foralphaisin(2,3]. The situation is, however, markedly different for large path-loss exponentsalpha>3. We show that in this regime the scaling of the achievable per-node rates depends crucially on the regularity of the node placement. We then present a family of schemes that smoothly ldquointerpolaterdquo between multihop and cooperative communication, depending upon the level of regularity in the node placement. We establish order optimality of these schemes under adversarial node placement foralpha>3.

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application in many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm are known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. More precisely, we consider the impact of having a slowly time-varying domain over which the minimization takes place. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps somewhat surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

In this paper, we investigate the use of message-passing algorithms for the problem of finding the max-weight independent set (MWIS) in a graph. First, we study the performance of the classical loopy max-product belief propagation. We show that each fixed-point estimate of max product can be mapped in a natural way to an extreme point of the linear programming (LP) polytope associated with the MWIS problem. However, this extreme point may not be the one that maximizes the value of node weights; the particular extreme point at final convergence depends on the initialization of max product. We then show that if max product is started from the natural initialization of uninformative messages, it always solves the correct LP, if it converges. This result is obtained via a direct analysis of the iterative algorithm, and cannot be obtained by looking only at fixed points. The tightness of the LP relaxation is thus necessary for max-product optimality, but it is not sufficient. Motivated by this observation, we show that a simple modification of max product becomes gradient descent on (a smoothed version of) the dual of the LP, and converges to the dual optimum. We also develop a message-passing algorithm that recovers the primal MWIS solution from the output of the descent algorithm. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of maximuma posteriori(MAP) estimation for probability distributions over finite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation.

With process variation becoming a growing concern in deep submicron technologies, the ability to efficiently obtain an accurate estimate of failure probability of SRAM components is becoming a central issue. In this paper we present a general methodology for a fast and accurate evaluation of the failure probability of memory designs. The proposed statistical method, which we call importance sampling through norm minimization principle, reduces the variance of the estimator to produce quick estimates. It builds upon the importance sampling, while using a novel norm minimization principle inspired by the classical theory of Large Deviations. Our method can be applied for a wide class of problems, and our illustrative examples are the data retention voltage and the read/write failure tradeoff for 6T SRAM in 32 nm technology. The method yields computational savings on the order of 10000x over the standard Monte Carlo approach in the context of failure probability estimation for SRAM considered in this paper.

Rate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms, it has long been known that this is a hard problem with these additional secondary constraints. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - epsi) polynomial-time approximation scheme for checking feasibility (for any epsi > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin,dmax) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section.

In this paper, we consider the problem of designing a scheduling algorithm for input queued switches, that is both fair as well as throughput optimal. Most of the existing literature on input-queued switch fairness criteria concentrates on flow-based fairness. Since a large fraction of network traffic is about "short- flows" there is a need for packet-based fairness criterion. The significant body of literature developed over the past two decades for packet-based scheduling algorithms is primarily concerned with throughput and delay, but not fairness. One of the reasons for such a state of affairs is the lack of a proper definition for packet-based fairness. The difficulty in defining fair stems from the fact that any reasonable notion of fairness must combine the well-known notion of fairness for a single-queue with the scheduling constraint of an input queued switch in an appropriate manner. As one of the main results of this paper, we define a notion of packet-based fair scheduling by identifying it as the selection of a winner in the following ranked election: packets are voters; schedules are candidates and each packet ranks different schedules based on their priorities. Drawing upon the seminal work of Goodman and Markowitz (1952) on ranked elections, we obtain a unique characterization of the fair schedule. Another important contribution of this paper is proving that the thus obtained fair scheduling algorithm is throughput optimal. There is no a priori reason why this should be true, and we introduce some non-standard proof techniques to prove the result. Our results suggest a framework for defining fair scheduling algorithm for a constrained packet network; a nonstandard method to prove throughput stability for algorithms, such as ours, that are not based on queue-sizes.

We consider a network of nodes, each having an initial value or measurement, and seeking to acquire an estimate of a given function of all the nodespsila values in the network. Each node may exchange with its neighbors a finite number of bits every time communication is initiated. In this paper, we present an algorithm for computation of separable functions, under the constraint that communicated messages are quantized, so that with some specified probability, all nodes have an estimate of the function value within a desired interval of accuracy. We derive an upper bound on the computation time needed to achieve this goal, and show that the dependence of the computation time on the network topology, via the ldquoconductancerdquo of the graph representing this topology, matches a lower bound derived from Information Theoretic analysis. Hence, the algorithmpsilas running time is optimal with respect to dependence on the graph structure.

We consider the problem of characterizing per node throughput scaling in arbitrary extended wireless networks. Recently, Özgür, Lévêque, and Tse (2007) obtained a complete characterization of throughput scaling for random extended networks (i.e., nodes are placed in a square region uniformly at random) under a fast fading channel model. They proposed a hierarchical cooperative communication scheme to establish this result. However, their results (both the communication scheme and the proof technique) are strongly dependent on the “regularity” induced with high probability by the random node placement. As a main result of this paper, we propose a more general (and very different) hierarchical cooperative communication scheme that works for arbitrarily placed nodes (with a minimum-separation requirement). Under our scheme, we obtain exactly the same per node throughput scaling as in Özgür et. al., showing that much less regularity is necessary for successful hierarchical cooperation. Our result holds under both fast and slow fading channel model. For small path-loss exponents α ∈ (2, 3], we show that our scheme is order optimal for all node placements with minimum-separation requirement. We also show that for certain node placements, our scheme is order optimal for all α ≫ 3 as well.

A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node ldquoseeingrdquo a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is O[(1)/(1-rho)] as opposed to Omega[(1)/(1-rho)2] for the baseline approach, where rho is the load factor.

We consider the problem of characterizing per node throughput scaling in arbitrary extended wireless networks. For extended networks with random node placement, the following threshold phenomenon exists: for path loss exponent alpha les 3, hierarchical cooperative communication achieves the optimal throughput scaling; for alpha > 3, multi-hop communication achieves the optimal throughput scaling. We establish that for arbitrary node placement, due to the lack of ldquoregularityrdquo, such a threshold phenomenon does not exist. More precisely, while hierarchical cooperative communication is still order optimal for alpha les 3, there are node placements such that multi-hop communication is not order optimal for alpha > 3. We then present a family of schemes that smoothly ldquointerpolatesrdquo between multi-hop and hierarchical cooperative communication, depending upon the ldquolevel of regularityrdquo of the node placement. We establish optimality of these schemes under adversarial node placement for alpha > 3.

Motivated by applications like elections, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings using constrained data. More specifically, we consider the problem of inferring a probability distribution over the group of permutations using its first order marginals. We first prove that it is not possible to recover more than O(n) permutations over n elements with the given information. We then provide a simple and novel algorithm that can recover up to O(n) permutations under a natural stochastic model; in this sense, the algorithm is optimal. In certain applications, the interest is in recovering only the most popular (or mode) ranking. As a second result, we provide an algorithm based on the Fourier Transform over the symmetric group to recover the mode under a natural majority condition; the algorithm turns out to be a maximum weight matching on an appropriately defined weighted bipartite graph. The questions considered are also thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing.

We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of 5dj/(1-ρj), at a factor 5 loss of throughput, where dj is the path length (number of hops) of flow j and ρj is the effective loading along the route of flow j. Clearly, dj is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network.

This paper considers structural and algorithmic problems in stochastic loss networks. The very popular Erlang approximation can be shown to provide relatively poor performance estimates, especially for loss networks in the critically loaded regime. This paper proposes a novel algorithm for estimating the stationary loss probabilities in stochastic loss networks based on structural properties of the exact stationary distribution, which is shown to always converge, exponentially fast, to the asymptotically exact results. Using a variational characterization of the stationary distribution, an alternative proof is provided for an important result due to Kelly, which is simpler and may be of interest in its own right. This paper also determines structural properties of the inverse Erlang function characterizing the region of capacities that ensures offered traffic is served within a set of loss probabilities. Numerical experiments investigate various issues of both theoretical and practical interest.

Max-product "belief propagation" (BP) is an iterative, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding and combinatorial optimization, which involve graphs with many cycles, theoretical results about both the correctness and convergence of the algorithm are known in only a few cases (see section I for references). In this paper, we prove the correctness and convergence of max-product for finding the maximum weight matching (MWM) in bipartite graphs. Even though the underlying graph of the MWM problem has many cycles, somewhat surprisingly we show that the max-product algorithm converges to the correct MWM as long as the MWM is unique. We provide a bound on the number of iterations required and show that for a graph of size n, the computational cost of the algorithm scales as O(n3), which is the same as the computational cost of the best known algorithms for finding the MWM. We also provide an interesting relation between the dynamics of the max-product algorithm and the auction algorithm, which is a well-known distributed algorithm for solving the MWM problem.

We provide a tight approximate characterization of then-dimensional product multicommodity flow (PMF) region for a wireless network ofnnodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information-theoretic sense and for a combinatorial interference model (e.g., protocol model). These provide an inner approximation to then2-dimensional capacity region. Our results hold for general node distributions, traffic models, and channel fading models. We first establish that the random source-destination model assumed in many previous results on capacity scaling laws, is essentially a one-dimensional approximation to the capacity region and a special case of PMF. We then build on the results for a wireline network (graph) that relate PMF to its spectral (or cut) properties. Specifically, for a combinatorial interference model given by a network graph and a conflict graph, we relate the PMF to the spectral properties of the underlying graphs resulting in simple computational upper and lower bounds. These results show that the 1/radicnscaling law obtained by Gupta and Kumar for a geometric random network can be explained in terms of the scaling law of the conductance of a geometric random graph. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs-such a characterization for general wireless networks has not been available before. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.

The problem of computing functions of values at the nodes in a network in a fully distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend, in general, to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the subroutine yields a complete fully distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme.

We consider the distributed computation of a function of random sources with minimal communication. Specifically, given two discrete memoryless sources, X and Y, a receiver wishes to compute f(X, Y) based on (encoded) information sent from X and Y in a distributed manner. A special case, f(X, Y) = (X, Y), is the classical question of distributed source coding considered by Slepian and Wolf (1973). Orlitsky and Roche (2001) considered a somewhat restricted setup when Y is available as side information at the receiver. They characterized the minimal rate at which X needs to transmit data to the receiver as the conditional graph entropy of the characteristic graph of X based on f. In our recent work (2006), we further established that this minimal rate can be achieved by means of graph coloring and distributed source coding (e.g. Slepian-Wolf coding). This characterization allows for the separation between "function coding" and "correlation coding." In this paper, we consider a more general setup where X and Y are both encoded (separately). This is a significantly harder setup for which to give a single-letter characterization for the complete rate region. We find that under a certain condition on the support set of X and Y (called the zigzag condition), it is possible to characterize the rate region based on graph colorings at X and Y separately. That is, any achievable pair of rates can be realized by means of first coloring graphs at X and Y separately (function coding) and then using Slepian-Wolf coding for these colors (correlation coding). We also obtain a single-letter characterization of the minimal joint rate. Finally, we provide simulation results based on graph coloring to establish the rate gains on real sequences

The input-queued switch architecture is widely used in Internet routers due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is the scheduling algorithm that decides which packets to transfer from ingress ports to egress ports in a given timeslot. It is desirable that such algorithms be iterative (so as to be pipelineable), distributed (allowing flexibility in hardware implementation) and are able to deliver high performance (in terms of throughput and delay). In practice, implementable algorithms have so far had limited success in combining all of the above properties. For example, the popular iSLIP algorithm is known to perform suboptimally, but it is commercially deployed mainly because it is iterative and distributed. The main contribution of this paper is the design and systematic analysis of two algorithms which, to the best of our knowledge, are the first high-performance iterative and distributed scheduling algorithms with possibility of efficient implementation. We first present an iterative, distributed and low-delay maximal throughput algorithm based on the celebrated "auction algorithm". This algorithm can be seen as a natural extension of iSLIP when queue-size information is allowed to be exchanged. The standard auction algorithm can take an unbounded number of iterations to converge in the worst case. However we show that under admissible Bernoulli i.i.d. traffic, our algorithm takes O(n2) iterations, where n is the number of ingress/egress ports in the switch. Moreover for a switch with finite buffer-size, the algorithm allows for a graceful trade-off between running time and performance, which we verify by representative simulation results. Next, we propose and analyze a throughput-optimal, iterative and distributed scheduling algorithm influenced by Max-product belief propagation. Recently the problem of efficient transmission over multi-hop wireless networks has been formulated as that of finding an appropriate schedule over the grid-graph abstraction of the network. A key feature of the multi-hop wireless transmission problem is that while the communication subgraph is bipartite, the bi-partition is allowed to change in each scheduling epoch. We show that our algorithm can be used to efficiently schedule traffic in multi-hop wireless networks.

We consider the problem of aggregating data at a mobile fusion center (fusor) (eg. a PDA or a cellular phone) moving within a spatial region over which a wireless sensor network (eg., fixed motes) has been deployed. Each sensor node generates packets destined to the fusor, and our objective is to develop strategies that can route the packets to the mobile fusor. For an arbitrary (possibly random) fusor mobility pattern over any connected subset of the sensor deployment area, we first derive upper bounds on the aggregation data rate (i.e., the uniform rate region from each sensor node to the mobile fusor), where we allow all sensor nodes to have complete knowledge of the mobility pattern of the fusor. We then consider aggregation data rates that can be achieved when the mobility pattern of the fusor is unknown to the sensor nodes. Surprisingly, we show that for a class of mobility patterns (random mobility over connected-compositions of convex sets of the deployment region, e.g. random walks over piece-wise linear sets), we can construct "universal" mobility-oblivious routing strategies that achieve aggregation data rates that are of the same order as the (mobility-aware) upper bound.

We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if network coding were not allowed. Thus, network coding leads to a larger rate region in a multicast crossbar switch. We demonstrate a traffic pattern which requires a switch speedup if coding is not allowed, whereas, with coding the speedup requirement is eliminated completely. In addition to throughput benefits, coding simplifies the characterization of the rate region. We give a graph-theoretic characterization of the rate region with fanout splitting and intra-flow coding, in terms of the stable set polytope of the "enhanced conflict graph" of the traffic pattern. Such a formulation is not known in the case of fanout splitting without coding. We show that computing the offline schedule (i.e. using prior knowledge of the flow arrival rates) can be reduced to certain graph coloring problems. Finally, we propose online algorithms (i.e. using only the current queue occupancy information) for multicast scheduling based on our graph-theoretic formulation. In particular, we show that a maximum weighted stable set algorithm stabilizes the queues for all rates within the rate region.

We consider the following rate distortion problem: given a source X and correlated, decoder side information Y, find the minimum encoding rate for X required to compute f(X,Y) at the decoder within distortion D. This is a generalization of the classical Wyner-Ziv setup and was resolved by Yamamoto (1982). However, this result involved an auxiliary random variable that lacks explicit meaning. To provide a more direct link between this variable and the function f, Orlitsky and Roche (2001) established the minimal rate required in the zero-distortion case as an extension of Korner's graph entropy. Recently, we (with Jaggi) showed that the zero-distortion rate can be achieved by minimum entropy graph coloring of an appropriate product graph. This leads to a modular architecture for functional source coding with a preprocessing "functional coding" scheme operating on top of a classical Slepian-Wolf source coding scheme. In this paper, we give a characterization of Yamamoto's rate distortion function in terms of a reconstruction function. This (non-single-letter) characterization is an extension of our previous results as well as Orlitsky and Roche's results. We obtain a modular scheme operating with Slepian-Wolf's scheme for the problem of functional rate distortion. Further, we give an achievable rate (with single-letter characterization) utilizing this scheme that intuitively extends our previous results.

In a wireless network, a sophisticated algorithm is required to schedule simultaneous wireless transmissions while satisfying interference constraint that two neighboring nodes can not transmit simultaneously. The scheduling algorithm need to be excellent in performance while being simple and distributed so as to be implementable. The result of Tassiulas and Ephremides (1992) imply that the algorithm, scheduling transmissions of nodes in the 'maximum weight independent set' (MWIS) of network graph, is throughput optimal. However, algorithmically the problem of finding MWIS is known to be NP-hard and hard to approximate. This raises the following questions: is it even possible to obtain throughput optimal simple, distributed scheduling algorithm? if yes, is it possible to minimize delay of such an algorithm? Motivated by these questions, we first provide a distributed throughput optimal algorithm for any network topology. However, this algorithm may induce exponentially large delay. To overcome this, we present an order optimal delay algorithm for any non-expanding network topology. Networks deployed in geographic area, like wireless networks, are likely to be of this type. Our algorithm is based on a novel distributed graph partitioning scheme which may be of interest in its own right. Our algorithm for non-expanding graph takes O (n) total message exchanges or O(l) message exchanges per node to compute a schedule.

The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables or equivalently of finding a point in the intersection of two sets. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. Our result is a generalization of the work by Csiszar and Tusnady on alternating minimization procedures. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.

We propose a new queueing mechanism for coded networks with stochastic arrivals and/or lossy links. In this context, earlier work introduced the notion of "virtual queues" which represent the backlog in degrees of freedom. For instance, the work by Ho and Viswanathan defined the achievable rate region for which the virtual queue size is stabilized, using intra-session coding. The queueing scheme that we propose here forms a natural bridge between the virtual queue size and the physical queue size, and thus extends their result to the stability of the physical queues as well. Specifically, we show that the amount of memory used at the transmit buffer in our scheme is upper bounded by the total backlog in the number of linearly independent degrees of freedom. Moreover, our scheme gives an online algorithm for queue update and coding, in the sense that the coding does not happen block by block, but in a streaming manner. The main idea in our scheme is to ensure that the information stored at the sender excludes any knowledge that is common to all receivers. This requires the transmitting node to track the states of knowledge of its receivers. Therefore, if the links are lossy, some form of feedback may be necessary.

We present a new local approximation algorithm for computing MAP and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when $G$ excludes some finite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is $\Theta(n)$ (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantifiable approximation guarantee that depends on the decomposition scheme.

We investigate the use of message-passing algorithms for the problem of finding the max-weight independent set (MWIS) in a graph. First, we study the perfor- mance of loopy max-product belief propagation. We show that, if it converges, the quality of the estimate is closely related to the tightness of an LP relaxation of the MWIS problem. We use this relationship to obtain sufficient conditions for correctness of the estimate. We then develop a modification of max-product – one that converges to an optimal solution of the dual of the MWIS problem. We also develop a simple iterative algorithm for estimating the max-weight independent set from this dual solution. We show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. Finally, we show that any problem of MAP estimation for probability distributions over finite domains can be reduced to an MWIS problem. We believe this reduction will yield new insights and algorithms for MAP estimation.

Grossglauser and Tse (2001) introduced a mobile random network model where each node moves independently on a unit disk according to a stationary uniform distribution and showed that a throughput of Theta(1) is achievable. El Gamal, Mammen, Prabhakar, and Shah (2004) showed that the delay associated with this throughput scales as Theta(nlogn), when each node moves according to an independent random walk. In a later work, Diggavi, Grossglauser, and Tse (2002) considered a random network on a sphere with a restricted mobility model, where each node moves along a randomly chosen great circle on the unit sphere. They showed that even with this one-dimensional restriction on mobility, constant throughput scaling is achievable. Thus, this particular mobility restriction does not affect the throughput scaling. This raises the question whether this mobility restriction affects the delay scaling. This correspondence studies the delay scaling at Theta(1) throughput for a random network with restricted mobility. First, a variant of the scheme presented by Diggavi, Grossglauser, and Tse (2002) is presented and it is shown to achieve Theta(1) throughput using different (and perhaps simpler) techniques. The exact order of delay scaling for this scheme is determined, somewhat surprisingly, to be of Theta(nlogn), which is the same as that without the mobility restriction. Thus, this particular mobility restriction does not affect either the maximal throughput scaling or the corresponding delay scaling of the network. This happens because under this 1-D restriction, each node is in the proximity of every other node in essentially the same manner as without this restriction

Most of the current communication networks, including the Internet, are packet switched networks. One of the main reasons behind the success of packet switched networks is the possibility of performance gain due to multiplexing of network bandwidth. The multiplexing gain crucially depends on the size of the buffers available at the nodes of the network to store packets at the congested links. However, most of the previous work assumes the availability of infinite buffer-size. In this paper, we study the effect of finite buffer-size on the performance of networks of interacting queues. In particular, we study the throughput of flow-controlled loss-less networks with finite buffers. The main result of this paper is the characterization of a dynamic scheduling policy that achieves the maximal throughput with a minimal finite buffer at the internal nodes of the network under memory-less (e.g., Bernoulli IID) exogenous arrival process. However, this ideal performance policy is rather complex and, hence, difficult to implement. This leads us to the design of a simpler and possibly implementable policy. We obtain a natural trade-off between throughput and buffer-size for such implementable policy. Finally, we apply our results to packet switches with buffered crossbar architecture

We consider communication over the Gaussian multiple access channel (MAC) with unknown set of active users. The proposed multiple access strategy is distributed and achieves a maximum sum rate point on the boundary of the capacity region for this channel for any set of active users S simultaneously, as if S were known at the transmitters. The proposed coding scheme splits each user into a set of virtual users, each of which can be decoded using a single-user decoder at the receiver instead of having to decode all users jointly. We also present a generalization of this scheme to the case where the channel gains differ between users and each user only knows its own channel gain.

The input-queued switch architecture is widely used in Internet routers, due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is choosing the scheduling algorithm, i.e. deciding which packets to transfer from ingress ports to egress ports in a given timeslot. Important metrics for evaluating a scheduling algorithm are its throughput and average delay. The well-studied ‘Maximum-Weight’ algorithm has been proved to have maximal throughput [1]; later work [2]–[4] found a wider class of algorithms which also have maximal throughput. The delay performance of these algorithms is less well understood. In this paper, we present a new technique for analysing scheduling algorithms which can explain their delay performance. In particular, we are able to explain the empirical observations in [2] about the average delay in a parameterized class of algorithms akin to Maximum-Weight. We also propose an optimal scheduling algorithm. Our technique is based on critically-balanced fluid model equations.

The max-product "belief propagation" algorithm has received a lot of attention recently due to its spectacular success in many application areas such as iterative decoding, computer vision and combinatorial optimization. There is a lot of ongoing work investigating the theoretical properties of the algorithm. In our previous work (2005) we showed that the max-product algorithm can be used to solve the problem of finding the maximum weight matching (MWM) in a weighted complete bipartite graph. However, for a graph with n nodes the max-product algorithm requires O(n4) operations to find the MWM compared to O(n3) for best known algorithms such as those proposed by Edmonds and Karp (1972) and Bertsekas (1988). In this paper, we simplify the max-product algorithm to reduce the number of operations required to O(n3). The simplified algorithm has very similar dynamics to the well-known auction algorithm of Bertsekas (1988). To make this connection precise, we show that the max-product and auction algorithms, when slightly modified, are equivalent. We study the correctness of this modified algorithm. There is a tantalizing similarity between this connection and a recently observed connection between the max-product and LP-based algorithms for iterative decoding by Vontobel and Koetter

Starting with the seminal work of Gupta and Kumar (2000), there have been many interesting results that give information theoretic outer and inner approximations to the rate region for wireless networks. While these bounds are almost tight for geometric random networks, not much is known about their tightness for arbitrary wireless networks. In contrast, Leighton and Rao (1988) established a powerful result that uniform multi-commodity flow (UMCF) is within a factor of log n of the natural min-cut capacity for any graph (equivalent to a wireline network) of n nodes. Our motivation is to obtain a similar simple and general characterization for UMCF (shown to be equivalent to the characterization for a much wider class of traffic models) for any wireless network. In this paper, we apply and extend known results to obtain such characterization for networks with Gaussian fading channels. For channel state information (CSI) only at the receivers, we establish that UMCF is within a Delta2log n factor of the information theoretic min-cut capacity of a wireless network, where Delta is the max-degree of a sub-graph induced by the underlying wireless network. For deterministic AWGN channels, we show that UMCF is within square root of the min-cut bound for any network

We study distributed algorithms, also known as gossip algorithms, for information dissemination in an arbitrary connected network of nodes. Distributed algorithms have applications to peer-to-peer, sensor, and ad hoc networks, in which nodes operate under limited computational, communication, and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes in which nodes repeatedly communicate with randomly chosen neighbors, thus distributing the computational burden across all the nodes in the network and making the computation robust against node failures. Information dissemination based on network coding was introduced by Deb and Medard. They showed the virtue of coding by analyzing a coding algorithm for a complete graph. Although their scheme generalizes to arbitrary graphs, the analysis does not. We present analysis of this algorithm for arbitrary graphs. Specifically, we find that the information dissemination time is naturally related to the spectral properties of the underlying network graph. Our results provide insight into how the graph topology affects the performance of the coding-based information dissemination algorithm

Distributed computation of average is essential for many tasks such as estimation, eigenvalue computation, scheduling in the context of wireless sensor and ad-hoc networks. The wireless communication imposes the gossip constraint: each node can communicate with at most one other node at a given time. Recent interest in emerging wireless sensor network has led to exciting developments in the context of gossip algorithms for averaging. Most of the known algorithms are iterative and based on certain reversible random walk on the network graph. Subsequently, the running time of algorithm is affected by the diffusive nature of reversible random walk. For example, they take Ω(n2) time to compute average on a simple path or ring graph of n nodes. In contrast, an optimal (simple) centralized algorithm takes [unk](n) time to compute average in a path. This raises the following questions: is it possible for a distributed algorithm to compute average in O(n) time for path graph? is it possible to improve over diffusive behavior of current algorithms in arbitrary graphs? In this paper, we answer the above questions in affirmative. To overcome the diffusive nature of algorithms, we utilize non-reversible random walks. Specifically, we design our algorithms by "projecting down" the "lifted" non-reversible random walks of Diaconis-Holmes-Neal (2000) and Chen-Lovasz-Pak (1999). The running time of our algorithm is square-root of the time taken by corresponding reversible random walk for a large class of graphs including path.

Motivated by applications to sensor, peer-to-peer, and ad-hoc networks, we study the problem of computing functions of values at the nodes in a network in a totally distributed manner. In particular, we consider separable functions, which can be written as linear combinations of functions of individual variables. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend in general to the computation of the actual values of separable functions.The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions based on properties of exponential random variables. We bound the running time of our algorithm in terms of the running time of an information spreading algorithm used as a subroutine by the algorithm. Since we are interested in totally distributed algorithms, we consider a randomized gossip mechanism for information spreading as the subroutine. Combining these algorithms yields a complete and simple distributed algorithm for computing separable functions.The second contribution of this paper is an analysis of the information spreading time of the gossip algorithm. This analysis yields an upper bound on the information spreading time, and therefore a corresponding upper bound on the running time of the algorithm for computing separable functions, in terms of the conductance of an appropriate stochastic matrix. These bounds imply that, for a class of graphs with small spectral gap (such as grid graphs), the time used by our algorithm to compute averages is of a smaller order than the time required for the computation of averages by a known iterative gossip scheme [5].

Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Theta(1/radic(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=Theta(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Theta(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Theta(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of Oscr(1/radic(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=Theta(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Theta(nlogn), which is the delay for throughput of Theta(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.

In Part I of this paper, the optimal throughput-delay tradeoff for static wireless networks was shown to be D(n)=Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this tradeoff captures the essential network dynamics, packets need to scale down with the network size. In this "fluid model, " no buffers are required. Due to this packet scaling, D(n) does not correspond to the average delay per bit. This leads to the question whether the tradeoff remains the same when the packet size is kept constant, which necessitates packet scheduling in the network. In this correspondence, this question is answered in the affirmative by showing that the optimal throughput-delay tradeoff is still D(n)=Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queuing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by devising a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queuing theory for continuous-time networks.

Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.

The advent of packet networks has motivated many researchers to study the performance of networks of queues in the last decade or two. However, most of the previous work assumes the availability of infinite queue-size. Instead, in this paper, we study the maximal achievable throughput in a flow-controlled lossless network with finite-queue size. In such networks, throughput depends on the packet scheduling policy utilized. As the main of this paper, we obtain a dynamic scheduling policy that achieves the maximal throughput (equal to the maximal throughput in the presence of infinite queue-size) with a minimal finite queue-size at the internal nodes of the network. Though the performance of the policy is ideal, it is quite complex and hence difficult to implement. This leads us to a design of simpler and possibly implementable policy. We obtain a natural trade-off between throughput and queue-size for this policy. We apply our results to the packet switches with buffered crossbar architecture. We propose a simple, implementable, distributed scheduling policy which provides high throughput in the presence of minimal internal buffer. We also obtain a natural trade-off between throughput, internal speedup and buffer-size providing a switch designer with a gamut of designs. To the best of authors' knowledge, this is one of the first attempts to study the throughput for general networks with finite queue-size. We believe that our methods are general and can be useful in other contexts.

The max-product "belief propagation" algorithm is an iterative, local, message passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding and computer vision which involve graphs with many cycles, theoretical convergence results are only known for graphs which are tree-like or have a single cycle. In this paper, we consider a weighted complete bipartite graph and define a probability distribution on it whose MAP assignment corresponds to the maximum weight matching (MWM) in that graph. We analyze the fixed points of the max-product algorithm when run on this graph and prove the surprising result that even though the underlying graph has many short cycles, the maxproduct assignment converges to the correct MAP assignment. We also provide a bound on the number of iterations required by the algorithm

In previous work (2004), we characterized the optimal throughput-delay trade-off in static wireless networks as D(n) = Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this trade-off captured the essential network dynamics, packets needed to scale down with the network size. In this "fluid model", no buffers were required. Due to this packet scaling, D(n) did not correspond to the average delay per bit. That led to the question whether the trade-off remains the same when the packet size is kept constant, which necessitates buffers and packet scheduling in the network. In this paper, we answer this question in the affirmative by showing that the optimal throughput-delay trade-off is still D(n) = Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queueing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by looking at a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queueing theory for continuous-time networks

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets-also knowns as cells-for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan et al. They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan et al. are strongly dependent on the arrival distribution. Next, we propose a new class of "waiting" algorithms. We show that the "waiting"-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.

In recent years, several high-throughput low-delay scheduling algorithms have been designed for input-queued (IQ) switches, assuming admissible traffic. In this paper, we focus on queueing systems that violate admissibility criteria. We show that in a single-server system with multiple queues, the longest queue first (LQF) policy disallows a fair allocation of service rates. We also describe the duality shared by LQF's rate allocation and a fair rate allocation. In general, we demonstrate that the rate allocation performed by the maximum weight matching (MWM) scheduling algorithm in overloaded IQ switches is unfair. We attribute this to the lack of coordination between admission control and scheduling, and propose fair scheduling algorithms that minimize delay for nonoverloaded queues.

Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in a wireless network when the nodes are fixed, and showed that the throughput per source-destination pair is /spl otimes/(1//spl radic/nlogn). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant or /spl otimes/(1) throughput scaling per source-destination pair. The focus of this paper is on characterizing the delay and determining the throughput-delay trade-off in such fixed and mobile ad hoc networks. For the Gupta-Kumar fixed network model, we show that the optimal throughput-delay trade-off is given by D(n) = /spl otimes/(nT(n)), where T(n) and D(n) are the throughput and delay respectively. For the Grossglauser-Tse mobile network model, we show that the delay scales as /spl otimes/(n/sup 1/2//v(n)), where v(n) is the velocity of the mobile nodes. We then describe a scheme that achieves the optimal order of delay for any given throughput. The scheme varies (i) the number of hops, (ii) the transmission range and (iii) the degree of node mobility to achieve the optimal throughput-delay trade-off. The scheme produces a range of models that capture the Gupta-Kumar model at one extreme and the Grossglauser-Tse model at the other. In the course of our work, we recover previous results of Gupta and Kumar, and Grossglauser and Tse using simpler techniques, which might be of a separate interest.

The random network model assumed in this paper is a generalization of the model that incorporates transmission energy consumption. The throughput, delay and energy-per-bit for a communication scheme are related through the scheme's average transmission range, i.e., average hop distance is considered. For mobile networks, the same model with additional feature that each node moves with velocity according to an independent Brownian motion is considered.

In this paper, we study the delay scaling for a mobile network with 1-D mobility restriction and show, that the delay scales as /spl Theta/(/spl radic/n/v(n)). Thus, this particular mobility restriction does not affect the throughput or the delay performance of the network.

The essence of an Internet router is an n /spl times/ n switch which routes packets from input to output ports. Such a switch can be viewed as a bipartite graph with the input and output ports as the two vertex sets. Packets arriving at input port i and destined for output port j can be modeled as an edge from i to j. Current switch scheduling algorithms view the routing of packets at each time step as a selection of a bipartite matching. We take the view that the switch scheduling problem across a sequence of time-steps is an instance of the edge coloring problem for a bipartite multigraph. Implementation considerations lead us to seek edge coloring algorithms for bipartite multigraphs that are fast, decentralized, and online. We present a randomized algorithm which has the desired properties, and uses only a near-optimal /spl Delta/ + o(/spl Delta/) colors on dense bipartite graphs arising in the context of switch scheduling. This algorithm extends to non-bipartite graphs as well. It leads to a novel switch scheduling algorithm which, for stochastic online edge arrivals, is stable, i.e. the queue length at each input port is bounded at all times. We note that this is the first decentralized switch scheduling algorithm that is also guaranteed to be stable.

In high-speed switches the input queued (IQ) architecture is very popular due to its low memory-bandwidth requirement compared to the output queued (OQ) switch architecture, which is extremely desirable in terms of performance but requires very high memory-bandwidth. In the past decade researchers and industry people have been trying hard to find good scheduling algorithm for IQ switches. The two main performance criteria for a scheduling algorithm are: (i) throughput, and (ii) delay. There has been a lot of research done to find throughput of scheduling algorithms, but a little has been known about delay performance of algorithms. This paper mainly studies the delay properties of a class of scheduling algorithms known as maximal matching algorithms. It has been known that maximum weight matching (MWM) scheduling algorithm provides the maximum possible throughput, also denoted as 100% throughput [Tassiulas, L., et al., Dec. 1993], [McKneown, N., et al., March 1996], [Dai, J., et al., March 2000]. The delay bounds for MWM algorithm, and a suite of approximations of MWM algorithm, are known under Bernoulli i.i.d. traffic. Unfortunately there are two problems: (i) MWM and its approximations are not implementable, and (ii) delay bounds are very weak compared to the known theoretical lower bounds that can be obtained in terms of performance of an OQ switch. On the other end of spectrum lies simple maximal matching algorithm like iSLIP [McKeown, N., April 1999], which is implemented in commercially available routers. In [Dai, J., et al., March 2000] it was shown that all maximal matching scheduling algorithms are stable at speedup of 2. But nothing is known about their delay performance. In this paper, we obtain bounds on all maximal matching scheduling algorithm running at speedup 2 when traffic is Bernoulli i.i.d. Interestingly, these bounds match the theoretical lower bound very closely and much better than the bounds on MWM. In particular, we show that any CIOQ switch running at speedup 2 with maximal matching schedule as at most 5 times longer queue-sizes on average compared to the OQ switch under Bernolli i.i.d. traffic. This suggests that under assumption of traffic being independent enough, no switch can do better than a simple maximal matching algorithm running at speedup 2. This provides the first theoretical support to "iSLIP can provide QoS". We would like to note that any IQ switch architecture that needs to sup- port OQ switch must have speedup 2 as shown in [Chuang, S.-T., et al., 1999], [Prabhakar, P., et al., 1999]. The algorithms proposed in [Chuang, S.-T., et al., 1999], [Prabhakar, P., et al., 1999] are very complex compared to algorithms like !SLIP.

Input Queued (IQ) switches have been very well studied in the recent past. The main problem in the IQ switches concerns scheduling. The main focus of the research has been the fixed length packet-known as cells-case. The scheduling decision becomes relatively easier for cells compared to the variable length packet case as scheduling needs to be done at a regular interval of fixed cell time. In real traffic dividing the variable packets into cells at the input side of the switch and then reassembling these cells into packets on the output side achieve it. The disadvantages of this cell-based approach are the following: (a) bandwidth is lost as division of a packet may generate incomplete cells, and (b) additional overhead of segmentation and reassembling cells into packets. This motivates the packet scheduling: scheduling is done in units of arriving packet sizes and in nonpreemptive fashion. In M.A. Marsan et al. (2001) the problem of packet scheduling was first considered. They show that under any admissible Bernoulli i.i.d. arrival traffic a simple modification of maximum weight matching (MWM) algorithm is stable, similar to cell-based MWM. In this paper, we study the stability properties of packet based scheduling algorithm for general admissible arrival traffic pattern. We first show that the result of Marsan et al. extends to general regenerative traffic model instead of just admissible traffic, that is, packet based MWM is stable. Next we show that there exists an admissible traffic pattern under which any work-conserving (that is maximal type) scheduling algorithm will be unstable. This suggests that the packet based MWM will be unstable too. To overcome this difficulty we propose a new class of "waiting" algorithms. We show that "waiting"-MWM algorithm is stable for any admissible traffic using fluid limit technique.

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.

A standard load balancing model considers placing n balls into n bins by choosing d possible locations for each ball independently and uniformly at random and sequentially placing each in the least loaded of its chosen bins. It is well known that allowing just a small amount of choice (d = 2) greatly improves performance over random placement (d = 1). In this paper, we show that similar performance gains occur by introducing memory. We focus on the situation where each time a ball is placed, the least loaded of that ball's choices after placement is remembered and used as one of the possible choices for the next ball. For example, we show that when each ball gets just one random choice, but can also choose the best of the last ball's choices, the maximum number of balls in a bin is log log n/2 log /spl phi/ + O(1) with high probability, where /spl phi/ = (1 + /spl radic/5)/2 is the golden ratio. The asymptotic performance is therefore better with one random choice and one choice from memory than with two fresh random choices for each ball; the performance with memory asymptotically matches the asymmetric policy, using two choices introduced by Vocking (1999). More generally, we find that a small amount of memory, like a small amount of choice, can dramatically improve the load balancing performance. We also investigate continuous time variations corresponding to queueing systems, where we find similar results.

The speedup of a switch is the factor by which the switch, and hence the memory used in the switch, runs faster compared to the line rate. In high-speed switches, line rates are already touching the limits at which memory can operate. It is very important for a switch to run at as low a speedup as possible. For an input queued (IQ) switch at speedup 1, 100% throughput can be achieved for any admissible traffic (McKeown, N. et al., 1999; Dai, J. and Prabhakar, B., 2000). This gives finite average delays but does not guarantee control on packet delays. S.T. Chuang et al. (see IEEE J. Selected Areas of Commun., vol.17, no.6, p.1030-9, 1999) show that a combined input output queued (CIOQ) switch can emulate perfectly an output queued (OQ) switch at a speedup of 2 and, thus, control the packet delays. This motivates a study of the possibility of obtaining delay control at speedup less than 2. To guarantee optimal control of delays for a general class of traffic, as shown by Chuang et al., speedup 2 is necessary. Hence, to obtain control of delays at lower speedup, we need to restrict the class of arrival traffic. We study the speedup requirement for a class of admissible traffic, which we denote as (1, nF)-regulated traffic, with parameters n and F. We obtain the necessary speedup for this class of traffic. Further, we present a general class of algorithms working at the necessary speedups and thus providing bounded delays.

High-aggregate bandwidth switches are those whose port count multiplied by the operating line rate is very high; for example, a 30 port switch operating at 40 Gbps or a 1000 port switch operating at 1 Gbps. Designing high-performance schedulers for such switches is challenging for the following reasons: (i) high performance requires finding good matchings; (ii) good matchings take time to find; (iii) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers: (a) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time; (b) observing arriving packets conveys useful information about the state of the switch. These features are exploited using hardware parallelism and randomization to yield three scheduling algorithms for IQ (input-queued) switches - APSARA, LAURA and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite competitive with respect to the maximum weight matching. The stability proof involves a derandomization procedure and uses methods which may have wider applicability.

Input Queued (IQ) switch architecture has been of interest due to its low memory bandwidth requirement. A scheduling algorithm is required to schedule the transfer of packets through cross-bar switch fabric at every time slot. The performance, that is throughput and delay, of a switch depends on the scheduling algorithm. The maximum weight matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. Leonardi et. al. (2001) obtained a nontrivial bound on the delay for the MWM algorithm under admissible Bernoulli i.i.d. traffic. There has been a lot of interesting work done over time to analyze throughput of scheduling algorithms. But apart from the work of Leonardi et al. there has not been any work done to obtain bounds on delay of scheduling algorithms. The MWM algorithm is perceived to be a very good scheduling algorithm in general and simulations have suggested that it performs better than most of the known algorithms in terms of delay. But it is very complex to implement. Hence many simple to implement approximations to MWM have been proposed. In this paper, we study a class of approximation algorithms to MWM, which always obtain a schedule whose weight W differs from the weight of MWM schedule W* by at most f(W*), where f(.) is a sub-linear function. We call this difference in weight as "approximation distance" of algorithm from MWM. We denote this class of algorithms by 1-APRX. We prove that any 1-APRX algorithm is stable, that is, it delivers upto 100% of throughput under any admissible Bernoulli i.i.d. input traffic. Under any admissible Bernoulli i.i.d. traffic, we obtain bounds on the average queue length(equivalently delay) of the 1-APRX algorithms using a Lyapunov function technique, which was motivated in Leonardi et al. The delay bounds obtained for the 1-APRX algorithm are linearly related with the "approximation distance", which matches the intuition that the better the weight of the schedule, the better the algorithm will perform. Interestingly, simulations show a linear relationship between the average queue length (equivalently delay) and the "approximation distance". Thus, the "approximation distance" of a scheduling algorithm can serve as a metric to differentiate between the performance of different stable algorithms, even though throughput may be same for these algorithms. We also obtain a novel heuristic tighter bound on the average queue length (equivalently delay) under uniform Bernoulli i.i.d. traffic for MWM using a very simple argument.

In a vertical representation of a market-basket database, each item is associated with a column of values representing the transactions in which it is present. The association-rule mining algorithms that have been recently proposed for this representation show performance improvements over their classical horizontal counterparts, but are either efficient only for certain database sizes, or assume particular characteristics of the database contents, or are applicable only to specific kinds of database schemas. We present here a new vertical mining algorithm called VIPER, which is general-purpose, making no special requirements of the underlying database. VIPER stores data in compressed bit-vectors called “snakes” and integrates a number of novel optimizations for efficient snake generation, intersection, counting and storage. We analyze the performance of VIPER for a range of synthetic database workloads. Our experimental results indicate significant performance gains, especially for large databases, over previously proposed vertical and horizontal mining algorithms. In fact, there are even workload regions where VIPER outperforms an optimal, but practically infeasible, horizontal mining algorithm.