Ravi Kumar 0001

ICLR Conference 2025 Conference Paper

Descent with Misaligned Gradients and Applications to Hidden Convexity

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We consider the problem of minimizing a convex objective given access to an oracle that outputs "misaligned" stochastic gradients, where the expected value of the output is guaranteed to be correlated with, but not necessarily equal to the true gradient of the objective. In the case where the misalignment (or bias) of the oracle changes slowly, we obtain an optimization algorithm that achieves the optimum iteration complexity of $\tilde O(\epsilon^{-2})$; for the more general case where the changes need not be slow, we obtain an algorithm with $\tilde O(\epsilon^{-3})$ iteration complexity. As an application of our framework, we consider optimization problems with a "hidden convexity" property, and obtain an algorithm with $O(\epsilon^{-3})$ iteration complexity.

ICML Conference 2025 Conference Paper

Scaling Laws for Differentially Private Language Models

• Ryan McKenna
• Yangsibo Huang
• Amer Sinha
• Borja Balle
• Zachary Charles
• Christopher A. Choquette-Choo
• Badih Ghazi
• Georgios Kaissis

Scaling laws have emerged as important components of large language model (LLM) training as they can predict performance gains through scale, and provide guidance on important hyper-parameter choices that would otherwise be expensive. LLMs also rely on large, high-quality training datasets, like those sourced from (sometimes sensitive) user data. Training models on this sensitive user data requires careful privacy protections like differential privacy (DP). However, the dynamics of DP training are significantly different, and consequently their scaling laws are not yet fully understood. In this work, we establish scaling laws that accurately model the intricacies of DP LLM training, providing a complete picture of the compute-privacy-utility and the optimal training configurations in many settings.

ICLR Conference 2025 Conference Paper

Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy

• Yangsibo Huang
• Daogao Liu
• Lynn Chua
• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi
• Milad Nasr

Machine unlearning algorithms, designed for selective removal of training data from models, have emerged as a promising approach to growing privacy concerns. In this work, we expose a critical yet underexplored vulnerability in the deployment of unlearning systems: the assumption that the data requested for removal is always part of the original training set. We present a threat model where an attacker can degrade model accuracy by submitting adversarial unlearning requests for data \textit{not} present in the training set. We propose white-box and black-box attack algorithms and evaluate them through a case study on image classification tasks using the CIFAR-10 and ImageNet datasets, targeting a family of widely used unlearning methods. Our results show extremely poor test accuracy following the attack—3.6% on CIFAR-10 and 0.4% on ImageNet for white-box attacks, and 8.5% on CIFAR-10 and 1.3% on ImageNet for black-box attacks. Additionally, we evaluate various verification mechanisms to detect the legitimacy of unlearning requests and reveal the challenges in verification, as most of the mechanisms fail to detect stealthy attacks without severely impairing their ability to process valid requests. These findings underscore the urgent need for research on more robust request verification methods and unlearning protocols, should the deployment of machine unlearning systems become more prevalent in the future.

ICML Conference 2024 Conference Paper

How Private are DP-SGD Implementations?

• Lynn Chua
• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi
• Amer Sinha
• Chiyuan Zhang

We demonstrate a substantial gap between the privacy guarantees of the Adaptive Batch Linear Queries (ABLQ) mechanism under different types of batch sampling: (i) Shuffling, and (ii) Poisson subsampling; the typical analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) follows by interpreting it as a post-processing of ABLQ. While shuffling-based DP-SGD is more commonly used in practical implementations, it has not been amenable to easy privacy analysis, either analytically or even numerically. On the other hand, Poisson subsampling-based DP-SGD is challenging to scalably implement, but has a well-understood privacy analysis, with multiple open-source numerically tight privacy accountants available. This has led to a common practice of using shuffling-based DP-SGD in practice, but using the privacy analysis for the corresponding Poisson subsampling version. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling, and thus advises caution in reporting privacy parameters for DP-SGD.

ICML Conference 2024 Conference Paper

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization

• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi
• Adam Sealfon

In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled variant satisfies two-sided DP. From this, we obtain several improved algorithms for private combinatorial optimization problems, including decomposable submodular maximization and set cover. Our error guarantees are asymptotically tight and our algorithm satisfies pure-DP while previously known algorithms (Gupta et al. , 2010; Chaturvedi et al. , 2021) are approximate-DP. We also show an application of our technique beyond combinatorial optimization by giving a pure-DP algorithm for the shifting heavy hitter problem in a stream; previously, only an approximate-DP algorithm was known (Kaplan et al. , 2021; Cohen & Lyu, 2023).

ICLR Conference 2024 Conference Paper

LabelDP-Pro: Learning with Label Differential Privacy via Projections

• Badih Ghazi
• Yangsibo Huang
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi
• Chiyuan Zhang

Label differentially private (label DP) algorithms seek to preserve the privacy of the labels in a training dataset in settings where the features are known to the adversary. In this work, we study a new family of label DP training algorithms. Unlike most prior label DP algorithms that have been based on label randomization, our algorithm naturally leverages the power of the central model of DP. It interleaves gradient projection operations with private stochastic gradient descent steps in order to improve the utility of the trained model while guaranteeing the privacy of the labels. We show that such projection-based algorithms can be made practical and that they improve on the state-of-the art for label DP training in the high-privacy regime. We complement our empirical evaluation with theoretical results shedding light on the efficacy of our method through the lens of bias-variance trade-offs.

ICML Conference 2023 Conference Paper

Bandit Online Linear Optimization with Hints and Queries

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We study variants of the online linear optimization (OLO) problem with bandit feedback, where the algorithm has access to external information about the unknown cost vector. Our motivation is the recent body of work on using such “hints” towards improving regret bounds for OLO problems in the full-information setting. Unlike in the full-information OLO setting, with bandit feedback, we first show that one cannot improve the standard regret bounds of $\tilde{O}(\sqrt{T})$ by using hints, even if they are always well-correlated with the cost vector. In contrast, if the algorithm is empowered to issue queries and if all the responses are correct, then we show $O(\log T)$ regret is achievable. We then show how to make this result more robust—when some of the query responses can be adversarial—by using a little feedback on the quality of the responses.

SODA Conference 2023 Conference Paper

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

• Justin Y. Chen
• Badih Ghazi
• Ravi Kumar 0001
• Pasin Manurangsi
• Shyam Narayanan
• Jelani Nelson
• Yinzhan Xu

We study the problem of releasing the weights of all-pairs shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ 1 -distance. We give an algorithm with additive error Õ ( n 2/3 /ε) in the ε-DP case and an algorithm with additive error in the (ε, δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o ( n )- error algorithm exists. We also show that an additive error of Ω ( n 1/6 ) is necessary for any sufficiently small ε, δ > 0. Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly in the ε-DP case and roughly in the (ε, δ)-DP case. Previously, it was only known how to obtain Õ ( n 2/3 /ε 1/3 ) additive error in the ε-DP case and additive error in the (ε, δ)-DP case for bounded-weight graphs [Sea16]. Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to Õ( n 1/2+ O (1/ k ) /ε) in the ε-DP case and Õ ( n 1/3+O(1/ k ) /ε) in the (ε, δ)-DP case.

ICML Conference 2023 Conference Paper

On User-Level Private Convex Optimization

• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi
• Raghu Meka
• Chiyuan Zhang

We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those in the prior work of Levy et al. 2021 and Narayanan et al. 2022, but with two important improvements. Our mechanism does not require any smoothness assumptions on the loss. Furthermore, our bounds are also the first where the minimum number of users needed for user-level privacy has no dependence on the dimension and only a logarithmic dependence on the desired excess error. The main idea underlying the new mechanism is to show that the optimizers of strongly convex losses have low local deletion sensitivity, along with a new output perturbation method for functions with low local deletion sensitivity, which could be of independent interest.

ICLR Conference 2023 Conference Paper

Regression with Label Differential Privacy

• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Ethan Leeman
• Pasin Manurangsi
• Avinash V. Varadarajan
• Chiyuan Zhang

We study the task of training regression models with the guarantee of _label_ differential privacy (DP). Based on a global prior distribution of label values, which could be obtained privately, we derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins", and propose an efficient algorithm for finding the optimal bin values. We carry out a thorough experimental evaluation on several datasets demonstrating the efficacy of our algorithm.

FOCS Conference 2023 Conference Paper

Towards Separating Computational and Statistical Differential Privacy

• Badih Ghazi
• Rahul Ilango
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi

Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 2008) and Mironov, Pandey, Reingold, and Vadhan (CRYPTO 2009). In contrast to SDP, CDP only requires privacy guarantees to hold against computationally-bounded adversaries rather than computationally-unbounded statistical adversaries. Despite the question being raised explicitly in several works (e. g. , Bun, Chen, and Vadhan, TCC 2016), it has remained tantalizingly open whether there is any task achievable with the CDP notion but not the SDP notion. Even a candidate such task is unknown. Indeed, it is even unclear what the truth could be! In this work, we give the first construction of a task achievable with the CDP notion but not the SDP notion, under the following strong but plausible cryptographic assumptions: •Non-Interactive Witness Indistinguishable Proofs, •Laconic Collision-Resistant Keyless Hash Functions, •Differing-Inputs Obfuscation for Public-Coin Samplers. In particular, we construct a task for which there exists an $\varepsilon$-CDP mechanism with $\varepsilon=O(1)$ achieving $1-o(1)$ utility, but any $(\varepsilon, \delta)$-SDP mechanism, including computationally-unbounded ones, that achieves a constant utility must use either a super-constant $\varepsilon$ or an inverse-polynomially large $\delta$. To prove this, we introduce a new approach for showing that a mechanism satisfies CDP: first we show that a mechanism is “private” against a certain class of decision tree adversaries, and then we use cryptographic constructions to “lift” this into privacy against computationally bounded adversaries. We believe this approach could be useful to devise further tasks separating CDP from SDP.

ICML Conference 2022 Conference Paper

Faster Privacy Accounting via Evolving Discretization

• Badih Ghazi
• Pritish Kamath
• Ravi Kumar 0001
• Pasin Manurangsi

We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for compositions of mechanisms. Our algorithm achieves a running time and memory usage of $polylog(k)$ for the task of self-composing a mechanism, from a broad class of mechanisms, $k$ times; this class, e. g. , includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent (DP-SGD). By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task. Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon the running time and memory usage in their work from $\widetilde{O}(k^{1. 5})$ to $\wtilde{O}(k)$.

SODA Conference 2022 Conference Paper

Learning-Augmented Weighted Paging

• Nikhil Bansal 0001
• Christian Coester
• Ravi Kumar 0001
• Manish Purohit
• Erik Vee

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging [45, 50, 52] to the weighted setting. For the case of perfect predictions, we provide an ℓ -competitive deterministic and an O (log ℓ )-competitive randomized algorithm, where ℓ is the number of distinct weight classes. Both these bounds are tight, and imply an O (log W )- and O (log log W )-competitive ratio, respectively, when the page weights lie between 1 and W. Previously, it was not known how to use these predictions in the weighted setting and only bounds of k and O (log k ) were known, where k is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from O ( ℓ ) and O (log ℓ ) to O ( k ) and O (log k ), respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.

ICML Conference 2022 Conference Paper

Parsimonious Learning-Augmented Caching

• Sungjin Im
• Ravi Kumar 0001
• Aditya Petety
• Manish Purohit

Learning-augmented algorithms—in which, traditional algorithms are augmented with machine-learned predictions—have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally when the predictions are accurate yet retain certain worst-case guarantees irrespective of the accuracy of the predictions. This framework has been successfully applied to online problems such as caching where the predictions can be used to alleviate uncertainties. In this paper we introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously. We consider the caching problem—which has been extensively studied in the learning-augmented setting—and show that one can achieve quantitatively similar results but only using a sublinear number of predictions.

ICML Conference 2022 Conference Paper

RUMs from Head-to-Head Contests

• Matteo Almanza
• Flavio Chierichetti
• Ravi Kumar 0001
• Alessandro Panconesi
• Andrew Tomkins

Random utility models (RUMs) encode the likelihood that a particular item will be selected from a slate of competing items. RUMs are well-studied objects in both discrete choice theory and, more recently, in the machine learning community, as they encode a fairly broad notion of rational user behavior. In this paper, we focus on slates of size two representing head-to-head contests. Given a tournament matrix $M$ such that $M_{i, j}$ is the probability that item $j$ will be selected from $\{i, j\}$, we consider the problem of finding the RUM that most closely reproduces $M$. For this problem we obtain a polynomial-time algorithm returning a RUM that approximately minimizes the average error over the pairs. Our experiments show that RUMs can perfectly represent many of the tournament matrices that have been considered in the literature; in fact, the maximum average error induced by RUMs on the matrices we considered is negligible ($\approx 0. 001$). We also show that RUMs are competitive, on prediction tasks, with previous approaches.

ICML Conference 2021 Conference Paper

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message

• Badih Ghazi
• Ravi Kumar 0001
• Pasin Manurangsi
• Rasmus Pagh
• Amer Sinha

The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.

ICML Conference 2021 Conference Paper

Light RUMs

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

A Random Utility Model (RUM) is a distribution on permutations over a universe of items. For each subset of the universe, a RUM induces a natural distribution of the winner in the subset: choose a permutation according to the RUM distribution and pick the maximum item in the subset according to the chosen permutation. RUMs are widely used in the theory of discrete choice. In this paper we consider the question of the (lossy) compressibility of RUMs on a universe of size $n$, i. e. , the minimum number of bits required to approximate the winning probabilities of each slate. Our main result is that RUMs can be approximated using $\tilde{O}(n^2)$ bits, an exponential improvement over the standard representation; furthermore, we show that this bound is optimal. En route, we sharpen the classical existential result of McFadden and Train (2000) by showing that the minimum size of a mixture of multinomial logits required to can approximate a general RUM is $\tilde{\Theta}(n)$.

ICML Conference 2021 Conference Paper

Locally Private k-Means in One Round

• Alisa Chang
• Badih Ghazi
• Ravi Kumar 0001
• Pasin Manurangsi

We provide an approximation algorithm for k-means clustering in the \emph{one-round} (aka \emph{non-interactive}) local model of differential privacy (DP). Our algorithm achieves an approximation ratio arbitrarily close to the best \emph{non private} approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, ours is the first constant-factor approximation algorithm for k-means that requires only \emph{one} round of communication in the local DP model, positively resolving an open question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible; we demonstrate this by showing that it also yields a similar near-optimal approximation algorithm in the (one-round) shuffle DP model.

STOC Conference 2021 Conference Paper

Sample-efficient proper PAC learning with approximate differential privacy

• Badih Ghazi
• Noah Golowich
• Ravi Kumar 0001
• Pasin Manurangsi

In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ( d 6 ), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2 O ( d ) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.

SODA Conference 2020 Conference Paper

Interleaved Caching with Access Graphs

• Ravi Kumar 0001
• Manish Purohit
• Zoya Svitkina
• Erik Vee

SODA Conference 2020 Conference Paper

On the Learnability of Random Deep Networks

• Abhimanyu Das
• Sreenivas Gollapudi
• Ravi Kumar 0001
• Rina Panigrahy

In this paper we study the learnability of random deep networks both theoretically and experimentally. On the theoretical front, assuming the statistical query model, we show that the learnability of random deep networks with sign activation drops exponentially with their depths; under plausible conjectures, our results extend to ReLu and sigmoid activations. The core of the arguments is that even for highly correlated inputs, the outputs of deep random networks are near-orthogonal. On the experimental side, we find that the learnability of random networks drops sharply with depth even with the state-of-the-art training methods.

ICML Conference 2020 Conference Paper

Online Learning with Imperfect Hints

• Aditya Bhaskara
• Ashok Cutkosky
• Ravi Kumar 0001
• Manish Purohit

We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a “hint” vector before choosing the action for that round. Rather surprisingly, it was shown that if the hint vector is guaranteed to have a positive correlation with the cost vector, then the online player can achieve a regret of $O(\log T)$, thus significantly improving over the $O(\sqrt{T})$ regret in the general setting. However, the result and analysis require the correlation property at \emph{all} time steps, thus raising the natural question: can we design online learning algorithms that are resilient to bad hints? In this paper we develop algorithms and nearly matching lower bounds for online learning with imperfect hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case. Our results also generalize, simplify, and improve upon previous results on optimistic regret bounds, which can be viewed as an additive version of hints.

ICML Conference 2020 Conference Paper

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead

• Badih Ghazi
• Ravi Kumar 0001
• Pasin Manurangsi
• Rasmus Pagh

Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trust assumptions whereas those in the local DP model make the weakest trust assumptions but incur substantial accuracy loss. The shuffled DP model [Bittau et al 2017, Erlingsson et al 2019, Cheu et al 19] has recently emerged as a feasible middle ground between the central and local models, providing stronger trust assumptions than the former while promising higher accuracies than the latter. In this paper, we obtain practical communication-efficient algorithms in the shuffled DP model for two basic aggregation primitives used in machine learning: 1) binary summation, and 2) histograms over a moderate number of buckets. Our algorithms achieve accuracy that is arbitrarily close to that of central DP algorithms with an expected communication per user essentially matching what is needed without any privacy constraints! We demonstrate the practicality of our algorithms by experimentally evaluating them and comparing their performance to several widely-used protocols such as Randomized Response [Warner 1965] and RAPPOR [Erlingsson et al. 2014].

ICML Conference 2019 Conference Paper

Faster Algorithms for Binary Matrix Factorization

• Ravi Kumar 0001
• Rina Panigrahy
• Ali Rahimi
• David P. Woodruff

We give faster approximation algorithms for well-studied variants of Binary Matrix Factorization (BMF), where we are given a binary $m \times n$ matrix $A$ and would like to find binary rank-$k$ matrices $U, V$ to minimize the Frobenius norm of $U \cdot V - A$. In the first setting, $U \cdot V$ denotes multiplication over $\mathbb{Z}$, and we give a constant-factor approximation algorithm that runs in $2^{O(k^2 \log k)} \textrm{poly}(mn)$ time, improving upon the previous $\min(2^{2^k}, 2^n) \textrm{poly}(mn)$ time. Our techniques generalize to minimizing $\|U \cdot V - A\|_p$ for $p \geq 1$, in $2^{O(k^{\lceil p/2 \rceil + 1}\log k)} \textrm{poly}(mn)$ time. For $p = 1$, this has a graph-theoretic consequence, namely, a $2^{O(k^2)} \poly(mn)$-time algorithm to approximate a graph as a union of disjoint bicliques. In the second setting, $U \cdot V$ is over $\GF(2)$, and we give a bicriteria constant-factor approximation algorithm that runs in $2^{O(k^3)} \poly(mn)$ time to find binary rank-$O(k \log m)$ matrices $U$, $V$ whose cost is as good as the best rank-$k$ approximation, improving upon $\min(2^{2^k}mn, \min(m, n)^{k^{O(1)}} \textrm{poly}(mn))$ time.

SODA Conference 2018 Conference Paper

Discrete Choice, Permutations, and Reconstruction

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

In this paper we study the well-known family of Random Utility Models, developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i. i. d. from some distribution a utility function mapping each item in the universe to a real-valued utility. The user is then offered a subset of the items, and selects the one of maximum utility. A M ax -D ist oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a M ax -D ist oracle, must return a function that approximates the oracle. We show three primary results. First, we show that any algorithm exactly reproducing the oracle must make exponentially many queries. Second, we show an equivalent representation of the distribution over utility functions, based on permutations, and show that if this distribution has support size k, then it is possible to approximate the oracle using O ( nk ) queries. Finally, we consider settings in which the subset of items is always small. We give an algorithm that makes less than n (1– ∊/ 2) K queries, each to sets of size at most (1– ∊/ 2) K, in order to approximate the M ax -D ist oracle on every set of size | T | ≤ K with statistical error at most ∊. In contrast, we show that any algorithm that queries for subsets of size must make maximal statistical error on some large sets.

ICML Conference 2018 Conference Paper

Learning a Mixture of Two Multinomial Logits

• Flavio Chierichetti
• Ravi Kumar 0001
• Andrew Tomkins

The classical Multinomial Logit (MNL) is a behavioral model for user choice. In this model, a user is offered a slate of choices (a subset of a finite universe of $n$ items), and selects exactly one item from the slate, each with probability proportional to its (positive) weight. Given a set of observed slates and choices, the likelihood-maximizing item weights are easy to learn at scale, and easy to interpret. However, the model fails to represent common real-world behavior. As a result, researchers in user choice often turn to mixtures of MNLs, which are known to approximate a large class of models of rational user behavior. Unfortunately, the only known algorithms for this problem have been heuristic in nature. In this paper we give the first polynomial-time algorithms for exact learning of uniform mixtures of two MNLs. Interestingly, the parameters of the model can be learned for any $n$ by sampling the behavior of random users only on slates of sizes 2 and 3; in contrast, we show that slates of size 2 are insufficient by themselves.

ICML Conference 2017 Conference Paper

Algorithms for $\ell_p$ Low-Rank Approximation

• Flavio Chierichetti
• Sreenivas Gollapudi
• Ravi Kumar 0001
• Silvio Lattanzi
• Rina Panigrahy
• David P. Woodruff

We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entrywise $\ell_p$-approximation error, for any $p \geq 1$; the case $p = 2$ is the classical SVD problem. We obtain the first provably good approximation algorithms for this robust version of low-rank approximation that work for every value of $p$. Our algorithms are simple, easy to implement, work well in practice, and illustrate interesting tradeoffs between the approximation quality, the running time, and the rank of the approximating matrix.

FOCS Conference 2015 Conference Paper

Approximate Modularity

• Flavio Chierichetti
• Abhimanyu Das
• Anirban Dasgupta 0001
• Ravi Kumar 0001

A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error, approximate modularity is the set analog of approximate linearity. In this paper we study how close, in additive error, can approximately modular functions be to truly modular functions. We first obtain a polynomial time algorithm that makes O(n 2 log n) queries to any approximately modular function to reconstruct a modular function that is O(√n)-close. We also show an almost matching lower bound: any algorithm world need super polynomially many queries to construct a modular function that is o(√(n/log n))-close. In a striking contrast to these near-tight computational reconstruction bounds, we then show that for any approximately modular function, there exists a modular function that is O(log n)-close.

SODA Conference 2014 Conference Paper

Learning Entangled Single-Sample Gaussians

• Flavio Chierichetti
• Anirban Dasgupta 0001
• Ravi Kumar 0001
• Silvio Lattanzi

We introduce a new model of Gaussian mixtures, motivated by the setting where the data points correspond to ratings on a set of items provided by users who have widely varying expertise, and each user can rate an item at most once. In this mixture model, each item i has a true quality μ i, each user has a variance (lack of expertise), and the rating of a user j on an item i consists of a single sample independently drawn from the Normal distribution. The aim is to learn the unknown item qualities μ i 's as precisely as possible. We study the single item case and obtain efficient algorithms for the problem, complemented by near-matching lower bounds; we also obtain preliminary results for the multiple items case. !TEX root = paper. tex

ICML Conference 2013 Conference Paper

Near-Optimal Bounds for Cross-Validation via Loss Stability

• Ravi Kumar 0001
• Daniel Lokshtanov
• Sergei Vassilvitskii
• Andrea Vattani

Multi-fold cross-validation is an established practice to estimate the error rate of a learning algorithm. Quantifying the variance reduction gains due to cross-validation has been challenging due to the inherent correlations introduced by the folds. In this work we introduce a new and weak measure of stability called \emphloss stability and relate the cross-validation performance to loss stability; we also establish that this relationship is near-optimal. Our work thus quantitatively improves the current best bounds on cross-validation.

SODA Conference 2012 Conference Paper

LSH-preserving functions and their applications

• Flavio Chierichetti
• Ravi Kumar 0001

FOCS Conference 2011 Conference Paper

Markov Layout

• Flavio Chierichetti
• Ravi Kumar 0001
• Prabhakar Raghavan

Consider the problem of laying out a set of n images that match a query onto the nodes of a √n×√n grid. We are given a score for each image, as well as the distribution of patterns by which a user's eye scans the nodes of the grid and we wish to maximize the expected total score of images selected by the user. This is a special case of the Markov layout problem, in which we are given a Markov chain M together with a set of objects to be placed at the states of the Markov chain. Each object has a utility to the user if viewed, as well as a stopping probability with which the user ceases to look further at objects. This layout problem is prototypical in a number of applications in web search and advertising, particularly in an emerging genre of search results pages from major engines. In a different class of applications, the states of the Markov chain are web pages at a publishers website and the objects are advertisements. We study the approximability of the Markov layout problem. Our main result is an O(log n) approximation algorithm for the most general version of the problem. The core idea is to transform an optimization problem over partial permutations into an optimization problem over sets by losing a logarithmic factor in approximation, the latter problem is then shown to be sub modular with two matroid constraints, which admits a constant-factor approximation. In contrast, we also show the problem is APX-hard via a reduction from CUBIC MAX-BISECTION. We then study harder variants of greater practical interest of the problem in which no gaps - states of M with no object placed on them - are allowed. By exploiting the geometry, we obtain an O(log 3/2 n) approximation algorithm when the digraph underlying M is a grid and an O(log n) approximation algorithm when it is a tree. These special cases are especially appropriate for our applications.

STOC Conference 2010 Conference Paper

A sparse Johnson: Lindenstrauss transform

• Anirban Dasgupta 0001
• Ravi Kumar 0001
• Tamás Sarlós

Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work we obtain a sparse version of the fundamental tool in dimension reduction -- the Johnson-Lindenstrauss transform. Using hashing and local densification, we construct a sparse projection matrix with just ~O(1/ε) non-zero entries per column. We also show a matching lower bound on the sparsity for a large class of projection matrices. Our bounds are somewhat surprising, given the known lower bounds of Ω(1/ε 2 ) both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. Using this, we achieve an ~O(1/ε) update time per non-zero element for a (1 ε)-approximate projection, thereby substantially outperforming the ~O(1/ε 2 ) update time required by prior approaches. A variant of our method offers the same guarantees for sparse vectors, yet its ~O(d) worst case running time matches the best approach of Ailon and Liberty.

SODA Conference 2010 Conference Paper

Finding the Jaccard Median

• Flavio Chierichetti
• Ravi Kumar 0001
• Sandeep Pandey
• Sergei Vassilvitskii

FOCS Conference 2009 Conference Paper

Models for the Compressible Web

• Flavio Chierichetti
• Ravi Kumar 0001
• Silvio Lattanzi
• Alessandro Panconesi
• Prabhakar Raghavan

Graphs resulting from human behavior (the web graph, friendship graphs, etc.) have hitherto been viewed as a monolithic class of graphs with similar characteristics; for instance, their degree distributions are markedly heavy-tailed. In this paper we take our understanding of behavioral graphs a step further by showing that an intriguing empirical property of web graphs-their compressibility-cannot be exhibited by well-known graph models for the web and for social networks. We then develop amore nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.

SODA Conference 2008 Conference Paper

Sampling algorithms and coresets for ℓ p regression

• Anirban Dasgupta 0001
• Petros Drineas
• Boulos Harb
• Ravi Kumar 0001
• Michael W. Mahoney

SODA Conference 2008 Conference Paper

The hiring problem and Lake Wobegon strategies

• Andrei Z. Broder
• Adam Kirsch
• Ravi Kumar 0001
• Michael Mitzenmacher
• Eli Upfal
• Sergei Vassilvitskii

SODA Conference 2007 Conference Paper

Estimating the sortedness of a data stream

• Parikshit Gopalan
• T. S. Jayram
• Robert Krauthgamer
• Ravi Kumar 0001

SODA Conference 2004 Conference Paper

An improved data stream algorithm for frequency moments

• Don Coppersmith
• Ravi Kumar 0001

FOCS Conference 2004 Conference Paper

Approximating Edit Distance Efficiently

• Ziv Bar-Yossef
• T. S. Jayram
• Robert Krauthgamer
• Ravi Kumar 0001

Edit distance has been extensively studied for the past several years. Nevertheless, no linear-time algorithm is known to compute the edit distance between two strings, or even to approximate it to within a modest factor. Furthermore, for various natural algorithmic problems such as low-distortion embeddings into normed spaces, approximate nearest-neighbor schemes, and sketching algorithms, known results for the edit distance are rather weak. We develop algorithms that solve gap versions of the edit distance problem: given two strings of length n with the promise that their edit distance is either at most k or greater than /spl lscr/, decide which of the two holds. We present two sketching algorithms for gap versions of edit distance. Our first algorithm solves the k vs. (kn)/sup 2/3/ gap problem, using a constant size sketch. A more involved algorithm solves the stronger k vs. /spl lscr/ gap problem, where /spl lscr/ can be as small as O(k/sup 2/) - still with a constant sketch - but works only for strings that are mildly "nonrepetitive". Finally, we develop an n/sup 3/7/-approximation quasilinear time algorithm for edit distance, improving the previous best factor of n/sup 3/4/ (Cole and Hariharan, 2002); if the input strings are assumed to be nonrepetitive, then the approximation factor can be strengthened to n/sup 1/3/.

STOC Conference 2004 Conference Paper

Sublinear algorithms for testing monotone and unimodal distributions

• Tugkan Batu
• Ravi Kumar 0001
• Ronitt Rubinfeld

The complexity of testing properties of monotone and unimodal distributions, when given access only to samples of the distribution, is investigated. Two kinds of sublinear-time algorithms---those for testing monotonicity and those that take advantage of monotonicity---are provided. The first algorithm tests if a given distribution on [n] is monotone or far away from any monotone distribution in L 1 -norm; this algorithm uses O(√n) samples and is shown to be nearly optimal. The next algorithm, given a joint distribution on [n] x [n], tests if it is monotone or is far away from any monotone distribution in L 1 -norm; this algorithm uses O(n 3/2 ) samples. The problems of testing if two monotone distributions are close in L 1 -norm and if two random variables with a monotone joint distribution are close to being independent in L 1 -norm are also considered. Algorithms for these problems that use only poly(log n) samples are presented. The closeness and independence testing algorithms for monotone distributions are significantly more efficient than the corresponding algorithms as well as the lower bounds for arbitrary distributions. Some of the above results are also extended to unimodal distributions.

SODA Conference 2003 Conference Paper

A note on the set systems used for broadcast encryption

• Ravi Kumar 0001
• Alexander Russell

STOC Conference 2003 Conference Paper

Cell-probe lower bounds for the partial match problem

• T. S. Jayram
• Subhash Khot
• Ravi Kumar 0001
• Yuval Rabani

Given a database of n points in (0,1) d , the partial match problem is: In response to a query x in (0, 1, *) d , find a database point y such that for every i whenever x i ≠ *, we have x i = y i . In this paper we show randomized lower bounds in the cell-probe model for this well-studied problem[18, 11, 19, 16, 4, 6 ].Our lower bounds follow from a two-party asymmetric randomized communication complexity near-optimal lower bound for this problem, where we show that either Alice has to send Ω(d log n) bits or Bob has to send Ω(n 1 - o(1) ) bits. When applied to the cell-probe model, it means that if the number of cells is restricted to be poly(n, d) where each cell is of size poly(log n, d), then Ω(d/log 2 n) probes are needed. This is an exponential improvement over the previously known lower bounds for this problem[16, 4].

SODA Conference 2003 Conference Paper

Comparing top k lists

• Ronald Fagin
• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2003 Conference Paper

Two applications of information complexity

• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

We show the following new lower bounds in two concrete complexity models: (1) In the two-party communication complexity model, we show that the tribes function on n inputs[6] has two-sided error randomized complexity Ω(n), while its nondeterminstic complexity and co-nondeterministic complexity are both Θ(√n). This separation between randomized and nondeterministic complexity is the best possible and it settles an open problem in Kushilevitz and Nisan[17], which was also posed by Beame and Lawry[5]. (2) In the Boolean decision tree model, we show that the recursive majority-of-three function on 3 h inputs has randomized complexity Ω((7/3) h ). The deterministic complexity of this function is Θ(3 h ), and the nondeterministic complexity is Θ(2 h ). Our lower bound on the randomized complexity is a substantial improvement over any lower bound for this problem that can be obtained via the techniques of Saks and Wigderson [23], Heiman and Wigderson[14], and Heiman, Newman, and Wigderson[13]. Recursive majority is an important function for which a class of natural algorithms known as directional algorithms does not achieve the best randomized decision tree upper bound. These lower bounds are obtained using generalizations of information complexity , which quantifies the minimum amount of information that will have to be revealed about the inputs by every correct algorithm in a given model of computation.

FOCS Conference 2002 Conference Paper

An Information Statistics Approach to Data Stream and Communication Complexity

• Ziv Bar-Yossef
• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on the communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving (conditional) information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.

STOC Conference 2002 Conference Paper

Approximate counting of inversions in a data stream

• Miklós Ajtai
• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

(MATH) Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model {14, 2] is a natural setting to design efficient algorithms.We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation. The best space bound we achieve is $O(\log n \log \log n)$ through a deterministic algorithm. In contrast, we derive an $\Omega(n)$ lower bound for randomized exact computation for this problem; thus approximation is essential.(MATH) We also consider two generalizations of this problem: (1) approximating the number of inversions between two permutations, for which we obtain a randomized $O(\sqrt{n} \log n)$-space algorithm, and (2) approximating the number of inversions in a general list, for which we obtain a randomized $O(\sqrt{n} \log^2 n)$-space two-pass algorithm. In contrast, we derive $\Omega(n)$-space lower bounds for deterministic approximate computation for these problems; thus both randomization and approximation are essential.All our algorithms use only O (log n ) time per data item.

SODA Conference 2002 Conference Paper

Reductions in streaming algorithms, with an application to counting triangles in graphs

• Ziv Bar-Yossef
• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2002 Conference Paper

The complexity of approximating entropy

• Tugkan Batu
• Sanjoy Dasgupta
• Ravi Kumar 0001
• Ronitt Rubinfeld

(MATH) We consider the problem of approximating the entropy of a discrete distribution under several models. If the distribution is given explicitly as an array where the i -th location is the probability of the i -th element, then linear time is both necessary and sufficient for approximating the entropy.We consider a model in which the algorithm is given access only to independent samples from the distribution. Here, we show that a λ-multiplicative approximation to the entropy can be obtained in O ( n (1+η) /λ 2 < poly(log n ) ) time for distributions with entropy Ω(λ η), where n is the size of the domain of the distribution and η is an arbitrarily small positive constant. We show that one cannot get a multiplicative approximation to the entropy in general in this model. Even for the class of distributions to which our upper bound applies, we obtain a lower bound of Ω( n max(1/(2λ 2 ), 2/(5λ 2 —2)) .We next consider a hybrid model in which both the explicit distribution as well as independent samples are available. Here, significantly more efficient algorithms can be achieved: a λ-multiplicative approximation to the entropy can be obtained in O ( λ2 .Finally, we consider two special families of distributions: those for which the probability of an element decreases monotonically in the label of the element, and those that are uniform over a subset of the domain. In each case, we give more efficient algorithms for approximating the entropy.

STOC Conference 2001 Conference Paper

A sieve algorithm for the shortest lattice vector problem

• Miklós Ajtai
• Ravi Kumar 0001
• D. Sivakumar 0001

We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero vector in an n -dimensional rational lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

SODA Conference 2001 Conference Paper

On polynomial approximation to the shortest lattice vector length

• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2001 Conference Paper

Sampling algorithms: lower bounds and applications

• Ziv Bar-Yossef
• Ravi Kumar 0001
• D. Sivakumar 0001

We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc , where \domain and \range are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n) . We define two quantitative properties of functions --- the it block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds. We also point out some connections between sampling and streaming algorithms and lossy compression schemes.

FOCS Conference 2001 Conference Paper

Testing Random Variables for Independence and Identity

• Tugkan Batu
• Lance Fortnow
• Eldar Fischer
• Ravi Kumar 0001
• Ronitt Rubinfeld
• Patrick White

Given access to independent samples of a distribution A over [n] /spl times/ [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i. e. , whether A is /spl epsi/-close in the L/sub 1/ norm to the product distribution A/sub 1//spl times/A/sub 2/ for some distributions A/sub 1/ over [n] and A/sub 2/ over [m]. The sample complexity of our test is O/spl tilde/(n/sup 2/3/m/sup 1/3/poly(/spl epsi//sup -1/)), assuming without loss of generality that m/spl les/n. We also give a matching lower bound, up to poly (log n, /spl epsi//sup -1/) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is /spl epsi/-close in L/sub 1/ norm to an explicitly specified distribution Y. Our test uses O/spl tilde/(n/sup 1/2/poly(/spl epsi//sup -1/)) samples, which nearly matches the known tight bounds for the case when Y is uniform.

FOCS Conference 2000 Conference Paper

Combinatorial feature selection problems

• Moses Charikar
• Venkatesan Guruswami
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai

Motivated by frequently recurring themes in information retrieval and related disciplines, we define a genre of problems called combinatorial feature selection problems. Given a set S of multidimensional objects, the goal is to select a subset K of relevant dimensions (or features) such that some desired property /spl Pi/ holds for the set S restricted to K. Depending on /spl Pi/, the goal could be to either maximize or minimize the size of the subset K. Several well-studied feature selection problems can be cast in this form. We study the problems in this class derived from several natural and interesting properties /spl Pi/, including variants of the classical p-center problem as well as problems akin to determining the VC-dimension of a set system. Our main contribution is a theoretical framework for studying combinatorial feature selection, providing (in most cases essentially tight) approximation algorithms and hardness results for several instances of these problems.

FOCS Conference 2000 Conference Paper

Random graph models for the web graph

• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• D. Sivakumar 0001
• Andrew Tomkins
• Eli Upfal

The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional G/sub n, p/ models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by Erdos-Renyi models.

STOC Conference 1999 Conference Paper

Fast Approximate PCPs

• Funda Ergün
• Ravi Kumar 0001
• Ronitt Rubinfeld

SODA Conference 1999 Conference Paper

Minimizing Wirelength in Zero and Bounded Skew Clock Trees

• Moses Charikar
• Jon M. Kleinberg
• Ravi Kumar 0001
• Sridhar Rajagopalan
• Amit Sahai
• Andrew Tomkins

STOC Conference 1999 Conference Paper

On targeting Markov segments

• Moses Charikar
• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• Andrew Tomkins

SODA Conference 1999 Conference Paper

Roundness Estimation via Random Sampling

• Ravi Kumar 0001
• D. Sivakumar 0001

FOCS Conference 1998 Conference Paper

Recommendation Systems: A Probabilistic Analysis

• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• Andrew Tomkins

A recommendation system tracks past actions of a group of users to make recommendations to individual members of the group. The growth of computer-mediated marketing and commerce has led to increased interest in such systems. We introduce a simple analytical framework for recommendation systems, including a basis for defining the utility of such a system. We perform probabilistic analyses of algorithmic methods within this framework. These analyses yield insights into how much utility can be derived from the memory of past actions and on how this memory can be exploited.

STOC Conference 1998 Conference Paper

Spot-Checkers

• Funda Ergün
• Sampath Kannan
• Ravi Kumar 0001
• Ronitt Rubinfeld
• Mahesh Viswanathan 0001

FOCS Conference 1996 Conference Paper

Approximate Checking of Polynomials and Functional Equations (extended abstract)

• Funda Ergün
• Ravi Kumar 0001
• Ronitt Rubinfeld

The authors show how to check programs that compute polynomials and functions defined by addition theorems-in the realistic setting where the output of the program is approximate instead of exact. They present results showing how to perform approximate checking, self-testing, and self-correcting of polynomials, settling in the affirmative a question raised by Gemmell et al. (1991), and Rubinfeld and Sudan (1992, 1996). They then show how to perform approximate checking, self-testing, and self-correcting for those functions that satisfy addition theorems, settling a question raised by Rubinfeld (1994]) In both cases, they show that the properties used to test programs for these functions are both robust (in the approximate sense) and stable. Finally, they explore the use of reductions between functional equations in the context of approximate self-testing. Their results have implications to the stability theory of functional equations.

FOCS Conference 1996 Conference Paper

Efficient Self-Testing/Self-Correction of Linear Recurrences

• Ravi Kumar 0001
• D. Sivakumar 0001

The authors consider the problem of designing self-testers/self-correctors for functions defined by linear recurrences. They present the first complete package of efficient and simple self-testers, self-correctors, and result-checkers for such functions. The results are proved by demonstrating an efficient reduction from this problem to the problem of testing linear functions over certain matrix groups. The tools include spectral analysis of matrices over finite fields, and various counting arguments that extend known techniques. The matrix twist yields simple and efficient self-testers for all linear recurrences. They also show a technique of using convolution identities to obtain very simple self-testers and self correctors. Their techniques promise new and efficient ways of testing VLSI chips for applications in control engineering, signal processing, etc. An interesting consequence of their methods is a completely new and randomness-efficient self-tester for polynomials over finite fields and rational domains. In particular the self-tester for polynomials over rational domains overcomes a main drawback of the result of Rubinfeld and Sudan (1992)-the need for a test domain of much larger size and of much finer precision.