A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a perfectly calibrated predictor. Hu and Wu (FOCS’24) use this to define an approximate calibration measure called calibration decision loss (CDL), which measures the maximal improvement achievable by any post-processing over any proper loss. Unfortunately, CDL turns out to be intractable to even weakly approximate in the offline setting, given black-box access to the predictions and labels.

Multiaccuracy and multicalibration are multi-group fairness notions for prediction that have found numerous applications in learning and computational complexity [HKRR18]. They can be achieved from a single learning primitive: weak agnostic learning. A line of work starting from [GKR+22] has shown that multicalibration implies a very strong form of learning. Here we investigate the power of multiaccuracy as a learning primitive, both with and without the additional assumption of calibration. We find that multiaccuracy in itself is rather weak, but that the addition of global calibration (this notion is called calibrated multiaccuracy) boosts its power substantially, enough to recover implications that were previously known only assuming the stronger notion of multicalibration. We give evidence that multiaccuracy might not be as powerful as standard weak agnostic learning, by showing that there is no way to post-process a multiaccurate predictor to get a weak learner, even assuming the best hypothesis has correlation 1/2. Rather, we show that it yields a restricted form of weak agnostic learning, which requires some concept in the class to have correlation greater than 1/2 with the labels. However, by also requiring the predictor to be calibrated, we recover not just weak, but strong agnostic learning. A similar picture emerges when we consider the derivation of hardcore measures from predictors satisfying multigroup fairness notions [TTV09], [CDV24]. On the one hand, while multiaccuracy only yields hardcore measures of density half the optimal, we show that (a weighted version of) calibrated multiaccuracy achieves optimal density. Our results yield new insights into the complementary roles played by multiaccuracy and calibration in each setting. They shed light on why multiaccuracy and global calibration, although not particularly powerful by themselves, together yield considerably stronger notions.

We give a principled method for decomposing the predictive uncertainty of a model into aleatoric and epistemic components with explicit semantics relating them to the real-world data distribution. While many works in the literature have proposed such decompositions, they lack the type of formal guarantees we provide. Our method is based on the new notion of higher-order calibration, which generalizes ordinary calibration to the setting of higher-order predictors that predict _mixtures_ over label distributions at every point. We show how to measure as well as achieve higher-order calibration using access to $k$-snapshots, namely examples where each point has $k$ independent conditional labels. Under higher-order calibration, the estimated aleatoric uncertainty at a point is guaranteed to match the real-world aleatoric uncertainty averaged over all points where the prediction is made. To our knowledge, this is the first formal guarantee of this type that places no assumptions whatsoever on the real-world data distribution. Importantly, higher-order calibration is also applicable to existing higher-order predictors such as Bayesian and ensemble models and provides a natural evaluation metric for such models. We demonstrate through experiments that our method produces meaningful uncertainty decompositions in tasks such as image classification.

Large language models (LLMs) have demonstrated impressive performance on several tasks and are increasingly deployed in real-world applications. However, especially in high-stakes settings, it becomes vital to know when the output of an LLM may be unreliable. Depending on whether an answer is trustworthy, a system can then choose to route the question to another expert, or otherwise fall back on a safe default behavior. In this work, we study the extent to which LLMs can reliably indicate confidence in their answers, and how this notion of confidence can translate into downstream accuracy gains. We propose Self-Reflection with Error-based Feedback (Self-REF), a lightweight training strategy to teach LLMs to express confidence in whether their answers are correct in a reliable manner. Self-REF introduces confidence tokens into the LLM, from which a confidence score can be extracted. Compared to conventional approaches such as verbalizing confidence and examining token probabilities, we demonstrate empirically that confidence tokens show significant improvements in downstream routing and rejection learning tasks.

Consider a multi-class labelling problem, where the labels can take values in $[k]$, and a predictor predicts a distribution over the labels. In this work, we study the following foundational question: \emph{Are there notions of multi-class calibration that give strong guarantees of meaningful predictions and can be achieved in time and sample complexities polynomial in $k$?} Prior notions of calibration exhibit a tradeoff between computational efficiency and expressivity: they either suffer from having sample complexity exponential in $k$, or needing to solve computationally intractable problems, or give rather weak guarantees. Our main contribution is a notion of calibration that achieves all these desiderata: we formulate a robust notion of \emph{projected smooth calibration} for multi-class predictions, and give new recalibration algorithms for efficiently calibrating predictors under this definition with complexity polynomial in $k$. Projected smooth calibration gives strong guarantees for all downstream decision makers who want to use the predictor for binary classification problems of the form: does the label belong to a subset $T \subseteq [k]$: \emph{e.g. is this an image of an animal?} It ensures that the probabilities predicted by summing the probabilities assigned to labels in $T$ are close to some perfectly calibrated binary predictor for that task. We also show that natural strengthenings of our definition are computationally hard to achieve: they run into information theoretic barriers or computational intractability. Underlying both our upper and lower bounds is a tight connection that we prove between multi-class calibration and the well-studied problem of agnostic learning in the (standard) binary prediction setting. This allows us to use kernel methods to design efficient algorithms, and also to use known hardness results for agnostic learning based on the hardness of refuting random CSPs to show lower bounds.

Consider the supervised learning setting where the goal is to learn to predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An \textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class $\mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$. Since the work of Gopalan et al. (2021) that introduced the notion, there has been a large body of work in the setting of binary labels where $\mathbf y \in \{0, 1\}$, but much less is known about the regression setting where $\mathbf y \in [0,1]$ can be continuous. The naive generalization of the previous approaches to regression is to predict the probability distribution of $y$, discretized to $\varepsilon$-width intervals. The running time would be exponential in the size of the output of the omnipredictor, which is $1/\varepsilon$. Our main conceptual contribution is the notion of \textit{sufficient statistics} for loss minimization over a family of loss functions: these are a set of statistics about a distribution such that knowing them allows one to take actions that minimize the expected loss for any loss in the family. The notion of sufficient statistics relates directly to the approximate rank of the family of loss functions. Thus, improved bounds on the latter yield improved runtimes for learning omnipredictors. Our key technical contribution is a bound of $O(1/\varepsilon^{2/3})$ on the $\epsilon$-approximate rank of convex, Lipschitz functions on the interval $[0,1]$, which we show is tight up to a factor of $\mathrm{polylog} (1/\epsilon)$. This yields improved runtimes for learning omnipredictors for the class of all convex, Lipschitz loss functions under weak learnability assumptions about the class $\mathcal C$. We also give efficient omnipredictors when the loss families have low-degree polynomial approximations, or arise from generalized linear models (GLMs). This translation from sufficient statistics to faster omnipredictors is made possible by lifting the technique of loss outcome indistinguishability introduced by Gopalan et al. (2023a) for Boolean labels to the regression setting.

Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be a distinct goal than loss minimization, even for simple predictors such as linear functions. In this work, we consider the setting where the protected groups can be represented by neural networks of size $k$, and the predictors are neural networks of size $n > k$. We show that minimizing the squared loss over all neural nets of size $n$ implies multicalibration for all but a bounded number of unlucky values of $n$. We also give evidence that our bound on the number of unlucky values is tight, given our proof technique. Previously, results of the flavor that loss minimization yields multicalibration were known only for predictors that were near the ground truth, hence were rather limited in applicability. Unlike these, our results rely on the expressivity of neural nets and utilize the representation of the predictor.

We present a new perspective on loss minimization and the recent notion of Omniprediction through the lens of Outcome Indistingusihability. For a collection of losses and hypothesis class, omniprediction requires that a predictor provide a loss-minimization guarantee simultaneously for every loss in the collection compared to the best (loss-specific) hypothesis in the class. We present a generic template to learn predictors satisfying a guarantee we call Loss Outcome Indistinguishability. For a set of statistical tests--based on a collection of losses and hypothesis class--a predictor is Loss OI if it is indistinguishable (according to the tests) from Nature's true probabilities over outcomes. By design, Loss OI implies omniprediction in a direct and intuitive manner. We simplify Loss OI further, decomposing it into a calibration condition plus multiaccuracy for a class of functions derived from the loss and hypothesis classes. By careful analysis of this class, we give efficient constructions of omnipredictors for interesting classes of loss functions, including non-convex losses. This decomposition highlights the utility of a new multi-group fairness notion that we call calibrated multiaccuracy, which lies in between multiaccuracy and multicalibration. We show that calibrated multiaccuracy implies Loss OI for the important set of convex losses arising from Generalized Linear Models, without requiring full multicalibration. For such losses, we show an equivalence between our computational notion of Loss OI and a geometric notion of indistinguishability, formulated as Pythagorean theorems in the associated Bregman divergence. We give an efficient algorithm for calibrated multiaccuracy with computational complexity comparable to that of multiaccuracy. In all, calibrated multiaccuracy offers an interesting tradeoff point between efficiency and generality in the omniprediction landscape.

Optimizing proper loss functions is popularly believed to yield predictors with good calibration properties; the intuition being that for such losses, the global optimum is to predict the ground-truth probabilities, which is indeed calibrated. However, typical machine learning models are trained to approximately minimize loss over restricted families of predictors, that are unlikely to contain the ground truth. Under what circumstances does optimizing proper loss over a restricted family yield calibrated models? What precise calibration guarantees does it give? In this work, we provide a rigorous answer to these questions. We replace the global optimality with a local optimality condition stipulating that the (proper) loss of the predictor cannot be reduced much by post-processing its predictions with a certain family of Lipschitz functions. We show that any predictor with this local optimality satisfies smooth calibration as defined in [Kakade and Foster, 2008, Błasiok et al., 2023]. Local optimality is plausibly satisfied by well-trained DNNs, which suggests an explanation for why they are calibrated from proper loss minimization alone. Finally, we show that the connection between local optimality and calibration error goes both ways: nearly calibrated predictors are also nearly locally optimal.

We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable setting or required the activation to be known. Moreover, we only require the marginal to have bounded second moments, whereas all prior work required stronger distributional assumptions (such as anticoncentration or boundedness). Our algorithm is based on recent work by Gopalan et al. [2023] on Omniprediction using predictors satisfying calibrated multiaccuracy. Our analysis is simple and relies on the relationship between Bregman divergences (or matching losses) and $\ell_p$ distances. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.

We introduce and study the notion of Swap Agnostic Learning. The problem can be phrased as a game between a *predictor* and an *adversary*: first, the predictor selects a hypothesis $h$; then, the adversary plays in response, and for each level set of the predictor, selects a loss-minimizing hypothesis $c_v \in \mathcal{C}$; the predictor wins if $h$ competes with the adaptive adversary's loss. Despite the strength of the adversary, our main result demonstrates the feasibility Swap Agnostic Learning for any convex loss. Somewhat surprisingly, the result follows by proving an *equivalence* between Swap Agnostic Learning and swap variants of the recent notions Omniprediction (ITCS'22) and Multicalibration (ICML'18). Beyond this equivalence, we establish further connections to the literature on Outcome Indistinguishability (STOC'20, ITCS'23), revealing a unified notion of OI that captures all existing notions of omniprediction and multicalibration.

We study the fundamental question of how to define and measure the distance from calibration for probabilistic predictors. While the notion of perfect calibration is well-understood, there is no consensus on how to quantify the distance from perfect calibration. Numerous calibration measures have been proposed in the literature, but it is unclear how they compare to each other, and many popular measures such as Expected Calibration Error (ECE) fail to satisfy basic properties like continuity.

The ratio between the probability that two distributions assign to points in the domain are called importance weights or density ratios and they play a fundamental role in machine learning and information theory. However, there are strong lower bounds known for point-wise accurate estimation of density ratios, and most theoretical guarantees require strong assumptions about the distributions. We motivate the problem of seeking accuracy guarantees for the distribution of importance weights conditioned on sub-populations belonging to a family $\mathcal{C}$ of subsets of the domain. We formulate {\em sandwiching bounds} for sets: upper and lower bounds on the expected importance weight conditioned on a set; as a notion of set-wise accuracy for importance weights. We argue that they capture intuitive expectations about importance weights, and are not subject to the strong lower bounds for point-wise guarantees. We introduce the notion of multicalibrated partitions for a class $\mathcal{C}$, inspired by recent work on multi-calibration in supervised learning and show that the importance weights resulting from such partitions do satisfy sandwiching bounds. In contrast, we show that importance weights returned by popular algorithms in the literature may violate the sandwiching bounds. We present an efficient algorithm for constructing multi-calibrated partitions, given a weak agnostic learner for the class $\mathcal{C}$.

Introduced as a notion of algorithmic fairness, multicalibration has proved to be a powerful and versatile concept with implications far beyond its original intent. This stringent notion—that predictions be well-calibrated across a rich class of intersecting subpopulations—provides its strong guarantees at a cost: the computational and sample complexity of learning multicalibrated predictors are high, and grow exponentially with the number of class labels. In contrast, the relaxed notion of multiaccuracy can be achieved more efficiently, yet many of the most desirable properties of multicalibration cannot be guaranteed assuming multiaccuracy alone. This tension raises a key question: \emph{Can we learn predictors with multicalibration-style guarantees at a cost commensurate with multiaccuracy?} In this work, we define and initiate the study of \emph{Low-Degree Multicalibration}. Low-Degree Multicalibration defines a hierarchy of increasingly-powerful multi-group fairness notions that spans multiaccuracy and the original formulation of multicalibration at the extremes. Our main technical contribution demonstrates that key properties of multicalibration, related to fairness and accuracy, actually manifest as low-degree properties. Importantly, we show that low-degree multicalibration can be significantly more efficient than full multicalibration. In the multi-class setting, the sample complexity to achieve low-degree multicalibration improves exponentially (in the number of classes) over full multicalibration. Our work presents compelling evidence that low-degree multicalibration represents a sweet spot, pairing computational and sample efficiency with strong fairness and accuracy guarantees.

Say that we are given samples from a distribution $ψ$ over an $n$-dimensional space. We expect or desire $ψ$ to behave like a product distribution (or a $k$-wise independent distribution over its marginals for small $k$). We propose the problem of enumerating/list-decoding all large subcubes where the distribution $ψ$ deviates markedly from what we expect; we refer to such subcubes as skewed subcubes. Skewed subcubes are certificates of dependencies between small subsets of variables in $ψ$. We motivate this problem by showing that it arises naturally in the context of algorithmic fairness and anomaly detection. In this work we focus on the special but important case where the space is the Boolean hypercube, and the expected marginals are uniform. We show that the obvious definition of skewed subcubes can lead to intractable list sizes, and propose a better definition of a minimal skewed subcube, which are subcubes whose skew cannot be attributed to a larger subcube that contains it. Our main technical contribution is a list-size bound for this definition and an algorithm to efficiently find all such subcubes. Both the bound and the algorithm rely on Fourier-analytic techniques, especially the powerful hypercontractive inequality. On the lower bounds side, we show that finding skewed subcubes is as hard as the sparse noisy parity problem, and hence our algorithms cannot be improved on substantially without a breakthrough on this problem which is believed to be intractable. Motivated by this, we study alternate models allowing query access to $ψ$ where finding skewed subcubes might be easier.

We consider the problem of detecting anomalies in a large dataset. We propose a framework called Partial Identification which captures the intuition that anomalies are easy to distinguish from the overwhelming majority of points by relatively few attribute values. Formalizing this intuition, we propose a geometric anomaly measure for a point that we call PIDScore, which measures the minimum density of data points over all subcubes containing the point. We present PIDForest: a random forest based algorithm that finds anomalies based on this definition. We show that it performs favorably in comparison to several popular anomaly detection methods, across a broad range of benchmarks. PIDForest also provides a succinct explanation for why a point is labelled anomalous, by providing a set of features and ranges for them which are relatively uncommon in the dataset.

Hillview is a distributed spreadsheet for browsing very large datasets that cannot be handled by a single machine. As a spread-sheet, Hillview provides a high degree of interactivity that permits data analysts to explore information quickly along many dimensions while switching visualizations on a whim. To provide the required responsiveness, Hillview introduces visualization sketches, or vizketches , as a simple idea to produce compact data visualizations. Vizketches combine algorithmic techniques for data summarization with computer graphics principles for efficient rendering. While simple, vizketches are effective at scaling the spreadsheet by parallelizing computation, reducing communication, providing progressive visualizations, and offering precise accuracy guarantees. Using Hillview running on eight servers, we can navigate and visualize datasets of tens of billions of rows and trillions of cells, much beyond the published capabilities of competing systems.

We consider the problem of finding anomalies in high-dimensional data using popular PCA based anomaly scores. The naive algorithms for computing these scores explicitly compute the PCA of the covariance matrix which uses space quadratic in the dimensionality of the data. We give the first streaming algorithms that use space that is linear or sublinear in the dimension. We prove general results showing that \emph{any} sketch of a matrix that satisfies a certain operator norm guarantee can be used to approximate these scores. We instantiate these results with powerful matrix sketching techniques such as Frequent Directions and random projections to derive efficient and practical algorithms for these problems, which we validate over real-world data sets. Our main technical contribution is to prove matrix perturbation inequalities for operators arising in the computation of these measures.

We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in logspace that have been considered in the literature, including halfspaces (over general domains), modular tests, and combinatorial shapes. For all these classes, our generator is the first to achieve near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize $\mathsf{RL}$---a central question in complexity theory. Our construction combines ideas from a large body of prior work, ranging from the classical construction of [J. Naor and M. Naor, SIAM J. Comput., 22 (1993), pp. 838--856] to the recent gradually increasing independence paradigm of [D. M. Kane, R. Meka, and J. Nelson, Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6845, Springer, Heidelberg, 2011, pp. 628--639; L. E. Celis et al., SIAM J. Comput., 42 (2013), pp. 1030--1050; P. Gopalan et al., Proceedings of the $53$rd Annual IEEE Symposium on Foundations of Computer Science, 2012, pp. 120--129], while also introducing some novel analytic machinery which might find other applications.

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two step process. The first step is choose a topology of the code, which incorporates knowledge about the correlate d failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field Fq. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recover ability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove the following results about codes for such topologies: The first super-polynomial lower bound on the field size needed for achieving maximal recoverability in a simple grid-like topology. To our knowledge, there was no super-linear lower bound known before, for any topology. A combinatorial characterization of erasure patterns correctable by Maximally Recoverable codes for a topology which corresponds to tensoring MDS codes with a parity check code. This topology is used in practice (for instance see [MLR+14]). We conjecture a similar characterization for Maximally Recoverable codes instantiating arbitrary tensor product topologies.

The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely the number of Hamming neighbors of x with different f-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree s^{O(1)}. The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be eps-approximated (in l_2) by a polynomial whose degree is s * polylog(1/eps). This is the first improvement on the folklore bound of s/eps. We prove this via a new "switching lemma for low-sensitivity functions" which establishes that a random restriction of a low-sensitivity function is very likely to have low decision tree depth. This is analogous to the well-known switching lemma for AC^0 circuits. Our proof analyzes the combinatorial structure of the graph G_f of sensitive edges of a Boolean function f. Understanding the structure of this graph is of independent interest as a means of understanding Boolean functions. We propose several new complexity measures for Boolean functions based on this graph, including tree sensitivity and component dimension, which may be viewed as relaxations of worst-case sensitivity, and we introduce some new techniques, such as proper walks and shifting, to analyze these measures. We use these notions to show that the graph of a function of full degree must be sufficiently complex, and that random restrictions of low-sensitivity functions are unlikely to lead to such complex graphs. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets. We prove a lower bound on tree sensitivity in terms of decision tree depth, and show that a polynomial strengthening of this lower bound implies the robust conjecture. We feel that studying the graph G_f is interesting in its own right, and we hope that some of the notions and techniques we introduce in this work will be of use in its further study.

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can be computed by a shallow decision tree. While this conjecture implies that smooth functions are easy to compute in the simplest computational model, to date no non-trivial upper bounds were known for such functions in any computational model, including unrestricted Boolean circuits. Even a bound on the description length of such functions better than the trivial 2n does not seem to have been known.

We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in log space that have been considered in the literature, including half spaces (over general domains), modular tests and combinatorial shapes. For all these classes, our generator is the first that achieves near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize RL -- a central question in complexity theory. Our construction combines ideas from a large body of prior work, ranging from a classical construction of [1] to the recent gradually increasing independence paradigm of [2] -- [4], while also introducing some novel analytic machinery which might find other applications.

Border's theorem gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment, and it has several applications in economic and algorithmic mechanism design. All known generalizations of Border's theorem either restrict attention to relatively simple settings, or resort to approximation. This paper identifies a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art. We also identify a surprisingly tight connection between Myerson's optimal auction theory, when applied to public project settings, and some fundamental results in the analysis of Boolean functions.

The long code is a central tool in hardness of approximation, especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: (1) For any $\varepsilon>0$, we show the existence of an $n$-vertex graph $G$ where every set of $o(n)$ vertices has expansion $1-\varepsilon$, but $G$'s adjacency matrix has more than $\exp(\log^{\delta}n)$ eigenvalues larger than $1-\varepsilon$, where $\delta$ depends only on $\varepsilon$. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563--572], who asked whether one can improve over the noise graph on the Boolean hypercube that has ${\rm poly}(\log n)$ such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo $K$ into instances with alphabet $k$ with a blowup of $k^{{\rm polylog}(K)}$, improving over the previously known gadget with blowup of $k^{\Omega(K)}$. (3) An $n$-variable integrality gap for Unique Games that survives $\exp({\rm poly}(\log\log n))$ rounds of the semidefinite programming version of the Sherali--Adams hierarchy, improving on the previously known bound of ${\rm poly}(\log\log n)$. We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

We give two new characterizations of ( 2-linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over Fh2:

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size.

Zombie is an endurance management framework that enables a variety of error correction mechanisms to extend the lifetimes of memories that suffer from bit failures caused by wearout, such as phase-change memory (PCM). Zombie supports both single-level cell (SLC) and multi-level cell (MLC) variants. It extends the lifetime of blocks in working memory pages (primary blocks) by pairing them with spare blocks, i.e., working blocks in pages that have been disabled due to exhaustion of a single block's error correction resources, which would be 'dead' otherwise. Spare blocks adaptively provide error correction resources to primary blocks as failures accumulate over time. This reduces the waste caused by early block failures, making working blocks in discarded pages a useful resource. Even though we use PCM as the target technology, Zombie applies to any memory technology that suffers stuck-at cell failures.

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, $\epsilon$-biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n\rightarrow\{0,1\}$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n\subseteq[m]$ and a symmetric function $h:\{0,1\}^n\rightarrow\{0,1\}$ such that $f(x_1,\ldots,x_n)=h(1_{A_1}(x_1),\ldots,1_{A_n}(x_n))$. Our generator uses seed-length $O(\log m+\log n+\log^2(1/\varepsilon))$ to get error $\varepsilon$. When $m=2$, this gives the first generator of seed-length $O(\log n)$ that fools all weight-based tests, meaning that the distribution of the weight of any subset is $\varepsilon$-close to the appropriate binomial distribution in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed-length $O(\log^{3/2}n)$ and error $1/\mathrm{poly}(n)$, matching Lu's bound from ICALP 1998. For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. As a corollary of our technique, we give an alternative proof of a powerful variant of the classical central limit theorem showing convergence in statistical distance, instead of the usual Kolmogorov distance.

We give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF or CNF. Given a DNF(or CNF) f on n variables and poly(n) terms, we give a deterministic nÕ((log log n)2)time algorithm that computes an (additive) ε approximation to the fraction of satisfying assignments of f for ε = 1/poly(logn). The previous best algorithm due to Luby and Velickovic from nearly two decades ago had a run-time of nexp(O(√log log n)). A crucial ingredient in our algorithm is a structural result which allows us to sparsify any small-width DNFformula. It says that any width w DNF(irrespective of the number of terms) can be ε-approximated by a width w DNFwith at most (w log(1/ε))O(w)terms. Further, our approximating DNFs have an additional “sandwiching” property which is crucial for applications to derandomization. We believe the sparsification result to be of independent interest and use it to show a weak derandomization of the switching lemma wherein the random restrictions need only have limited independence.

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε >; 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - ε, but G's adjacency matrix has more than exp(logδn) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of Kpolylog(K), improving over the previously known gadget with blowup of 2Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length Õ(log (n/ε)) for error ε. Previously, only constructions with seed-length O(log3/2n) or O(log2n) were known for these classes with error ε = 1/poly(n). The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

Consider a linear [n,k,d]qcodeC. We say that theith coordinate ofChas localityr, if the value at this coordinate can be recovered from accessing some otherrcoordinates ofC. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancyn-kin terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance.

Given $n$ elements with non-negative integer weights $w_1,..., w_n$ and an integer capacity $C$, we consider the counting version of the classic knapsack problem: find the number of distinct subsets whose weights add up to at most $C$. We give the first deterministic, fully polynomial-time approximation scheme (FPTAS) for estimating the number of solutions to any knapsack constraint (our estimate has relative error $1 \pm \epsilon$). Our algorithm is based on dynamic programming. Previously, randomized polynomial-time approximation schemes (FPRAS) were known first by Morris and Sinclair via Markov chain Monte Carlo techniques, and subsequently by Dyer via dynamic programming and rejection sampling. In addition, we present a new method for deterministic approximate counting using {\em read-once branching programs.} Our approach yields an FPTAS for several other counting problems, including counting solutions for the multidimensional knapsack problem with a constant number of constraints, the general integer knapsack problem, and the contingency tables problem with a constant number of rows.

An $(r,\delta,\epsilon)$-locally decodable code encodes a k-bit message x to an N-bit codeword $C(x)$, such that for every $i\in[k]$, the ith message bit can be recovered with probability $1-\epsilon$, by a randomized decoding procedure that queries only r bits, even if the codeword $C(x)$ is corrupted in up to $\delta N$ locations. Recently a new class of locally decodable codes (LDCs), based on families of vectors with restricted dot products, has been discovered. We refer to those codes as matching vector (MV) codes. Several families of $(r,\delta,\Theta(r\delta))$-locally decodable MV codes have been obtained. While codes in those families were shorter than codes of earlier generations, they suffered from having large values of $\epsilon=\Omega(r\delta)$, which meant that r-query MV codes could only handle error rates below $\frac{1}{r}$. Thus larger query complexity gave shorter length codes but at the price of less error tolerance. No MV codes of a superconstant number of queries capable of tolerating a constant fraction of errors were known to exist. In this paper we present a new view of matching vector codes and uncover certain similarities between MV codes and classical Reed–Muller (RM) codes. Our view allows us to obtain deeper insights into the power and limitations of MV codes. Specifically, we obtain the following: (1) We show that existing families of MV codes can be enhanced to tolerate a large constant fraction of errors, independent of the number of queries. Such enhancement comes at a price of a moderate increase in the number of queries. (2) Our construction yields the first families of MV codes of superconstant query complexity that can tolerate a constant fraction of errors. Our codes are shorter than RM LDCs for all values of $r\leq\log k/(\log\log k)^c$, for some constant c. (3) We show that any MV code encodes messages of length k to codewords of length at least $k2^{\Omega(\sqrt{\log k})}$. Therefore MV codes do not improve upon RM LDCs for $r\geq(\log k)^{\Omega(\sqrt{\log k})}$.

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for every code, the ratio of its list decoding radius (LDR) to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. We show that for every code, its LDR remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur et al. [in Proceedings of the 40th ACM Symposium on Theory of Computing (STOC '08), 2008, pp. 275–284], who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). Using the notion of generalized Hamming weights, we give better list size bounds for both the tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to one of bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank reduction together with other ideas, we obtain list size bounds that are tight over small fields. Our results give better bounds on the LDR than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson radius.

We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable. We give the first efficient algorithms for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients) and for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing that any testing algorithm—even an adaptive one—must have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Building on these results, we give an “implicit learning” algorithm that lets us test any subproperty of Fourier concision. We also present some applications of these results to exact learning and decoding. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from [V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 563–576].

... under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0. Our first main result shows that a recent pseudorandom generator construction of Meka and Zuckerman [MZ09], when suitably modified, can fool arbitrary functions of d halfspaces under product distributions where each coordinate has bounded fourth moment. To ǫ-fool any size-s, depth-d decision tree of halfspaces, our pseudorandom generator uses seed length O((dlog(ds/ǫ)+logn)·log(ds/ǫ)). For monotone functions of d halfspaces, the seed length can be improved to O((dlog(d/ǫ)+logn)·log(d/ǫ)). We get better bounds for larger ǫ; for example, to1/polylog(n)-foolallmonotonefunctionsof(logn)/loglognhalfspaces,ourgeneratorrequires a seed of length just O(logn). Our second main result generalizes the work of Diakonikolas et al. [DGJ + 09] to show that bounded independence suffices to fool functions of halfspaces under product distributions. Assuming each coordinatesatisfiesacertainstrongermoment condition, we showthat anyfunction computable by a size-s, depth-d decision tree of halfspaces is ǫ-fooled by Õ(d4 s 2 /ǫ 2)-wise independence. Our technical contributions include: a new multidimensional version of the classical Berry-Esseen theorem; a derandomization thereof; a generalization of Servedio [Ser07]’s regularity lemma for halfspaceswhichworksunderanyproduct distribution with bounded fourth moments; an extension of this regularity lemma to functions of many halfspaces; and, new analysis of the sandwiching polynomials technique of Bazzi [Baz09] for arbitrary product distributions.

A locally decodable code encodes a message by a codeword, such that even if the codeword is corrupted by noise, each message bit can be recovered with high probability by a randomized decoding procedure that reads only few bits of the codeword. Recently a new class of locally decodable codes, based on families of vectors with restricted dot products has been discovered. We refer to those codes as Matching Vector (MV) codes. In this work we develop a new view of MV codes and uncover certain similarities between them and classical Reed Muller codes. Our view allows us to obtain a deeper insight into the power and limitations of MV codes. We use it to construct codes that can tolerate more errors or are shorter than previously known codes for certain parameter settings. We also show super-linear lower bounds on the codeword length of any MV code.

We present a Fourier-analytic approach to list-decoding Reed–Muller codes over arbitrary finite fields. We use this to show that quadratic forms over any field are locally list-decodable up to their minimum distance. The analogous statement for linear polynomials was proved in the celebrated works of GoldreichPreviously, tight bounds for quadratic polynomials were known only for$q = 2$and 3; the best bound known for other fields was the Johnson radius. Departing from previous work on Reed–Muller decoding which relies on some form of self-corrector, our work applies ideas from Fourier analysis of Boolean functions to low-degree polynomials over finite fields, in conjunction with results about the weight-distribution. We believe that the techniques used here could find other applications, we present some applications to testing and learning.

We show that any distribution on $\{-1,+1\}^n$ that is k-wise independent fools any halfspace (or linear threshold function) $h:\{-1,+1\}^n\to\{-1,+1\}$, i.e., any function of the form $h(x)=\operatorname{sign}(\sum_{i=1}^{n}w_{i}x_{i}-\theta)$, where the $w_1,\dots,w_n$ and $\theta$ are arbitrary real numbers, with error $\epsilon$ for $k=O(\epsilon^{-2}\log^2(1/\epsilon))$. Our result is tight up to $\log(1/\epsilon)$ factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators $G:\{-1,+1\}^s\to\{-1,+1\}^n$ that fool halfspaces. Specifically, we fool halfspaces with error $\epsilon$ and seed length $s=k\cdot\log n=O(\log n\cdot\epsilon^{-2}\log^2(1/\epsilon))$. Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180–209].

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space $\Omega(\sqrt{n})$. This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM–SIAM Symposium on Discrete Algorithms, 2007, pp. 318–327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

We study the polynomial reconstruction problem for low-degree multivariate polynomials over finite field $\mathbb{F}[2]$. In this problem, we are given a set of points $\mathbf{x}\in\{0,1\}^n$ and target values $f(\mathbf{x})\in\{0,1\}$ for each of these points, with the promise that there is a polynomial over $\mathbb{F}[2]$ of degree at most d that agrees with f at $1-\varepsilon$ fraction of the points. Our goal is to find a degree d polynomial that has good agreement with f. We show that it is NP-hard to find a polynomial that agrees with f on more than $1-2^{-d}+\delta$ fraction of the points for any $\epsilon,\delta>0$. This holds even with the stronger promise that the polynomial that fits the data is in fact linear, whereas the algorithm is allowed to find a polynomial of degree d. Previously the only known hardness of approximation (or even NP-completeness) was for the case when $d =1$, which follows from a celebrated result of Håstad [J. ACM, 48 (2001), pp. 798–859]. In the setting of Computational Learning, our result shows the hardness of nonproper agnostic learning of parities, where the learner is allowed a low-degree polynomial over $\mathbb{F}[2]$ as a hypothesis. This is the first nonproper hardness result for this central problem in computational learning. Our results can be extended to multivariate polynomial reconstruction over any finite field.

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0,1}nrarr {0,1} which depend on all n variables, and distinct primes p, q: (1) If f has degree o(log n) modulo p, then it must have degree Omega(n1-o(1)) modulo q. Thus a Boolean function has degree o(log n) in only one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. (2) If f has degree d = o(log n) modulo p, it cannot be computed correctly on more than 1 - p-O(d)fraction of the hypercube by polynomials of degree n1/2-isinmodulo q. As a corollary of the above results it follows that if f has degree o(log n) modulo p, then it requires super-polynomial size A C0[q] circuits. This gives a lower bound for a broad and natural class of functions.

We show that any distribution on {-1,+1}nthat is k-wise independent fools any halfspace (a.k.a. threshold) h : {-1,+1}n¿ {-1,+1}, i.e., any function of the form h(x) = sign(¿i=1nwiXi- ¿) where the w1,..., wn, ¿ are arbitrary real numbers, with error ¿ for k = O(¿-2log2(1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G : {-1,+1}s¿ {-1,+1}nthat fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿-2log2(1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

Given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((log m)3) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently.

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. (1) We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. (2) We show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur.et.al, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). (3)Using the notion of generalized Hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain tight list size bounds for small fields.

We study the learnability of several fundamental concept classes in the agnostic learning framework of [D. Haussler, Inform. and Comput., 100 (1992), pp. 78–150] and [M. Kearns, R. Schapire, and L. Sellie, Machine Learning, 17 (1994), pp. 115–141]. We show that under the uniform distribution, agnostically learning parities reduce to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of [A. Blum, A. Kalai, and H. Wasserman, J. ACM, 50 (2003), pp. 506–519], this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of disjunctive normal form (DNF) expressions reduces to learning noisy parities of just logarithmic number of variables, and learning of k-juntas reduces to learning noisy parities of k variables. We give essentially optimal hardness results for agnostic learning of monomials over $\{0,1\}^n$ and halfspaces over $\mathbb{Q}^n$. We show that for any constant $\epsilon$ finding a monomial (halfspace) that agrees with an unknown function on $1/2+\epsilon$ fraction of the examples is NP-hard even when there exists a monomial (halfspace) that agrees with the unknown function on $1-\epsilon$ fraction of the examples. This resolves an open question due to Blum and significantly improves on a number of previous hardness results for these problems. We extend these results to $\epsilon=2^{-\log^{1-\lambda}n}$ ($\epsilon=2^{-\sqrt{\log n}}$ in the case of halfspaces) for any constant $\lambda>0$ under stronger complexity assumptions.

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics, and threshold phenomena. Recent work on heuristics and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions of Boolean satisfiability problems and establish various dichotomies in Schaefer's framework. On the structural side, we obtain dichotomies for the kinds of subgraphs of the hypercube that can be induced by the solutions of Boolean formulas, as well as for the diameter of the connected components of the solution space. On the computational side, we establish dichotomy theorems for the complexity of the connectivity and $st$-connectivity questions for the graph of solutions of Boolean formulas. Our results assert that the intractable side of the computational dichotomies is PSPACE-complete, while the tractable side—which includes but is not limited to all problems with polynomial-time algorithms for satisfiability—is in P for the $st$-connectivity question, and in coNP for the connectivity question. The diameter of components can be exponential for the PSPACE-complete cases, whereas in all other cases it is linear; thus, diameter and complexity of the connectivity problems are remarkably aligned. The crux of our results is an expressibility theorem showing that in the tractable cases, the subgraphs induced by the solution space possess certain good structural properties, whereas in the intractable cases, the subgraphs can be arbitrary.

We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant mu Gt 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 - (log n)-mu fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm can decide L' correctly on a 3/4 + (log n)-mu fraction of inputs of length n. In coding theoretic terms, we give a construction of a monotone code that can be uniquely decoded up to error rate 1/4 by a deterministic local decoder.

We give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. Given black-box access to an *arbitrary* binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees with f on almost (within an epsilon fraction) as many inputs as the best size-t decision tree, in time poly(n,t,1ε).

We present the first local list-decoding algorithm for the rth order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: Fm -< F, our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance (2-r - ε) from R for any ε < 0 in time poly(mr,ε-r). The list size could be exponential in m at radius 2-r, so our bound is optimal in the local setting. Since RM(2,m) has relative distance 2-r, our algorithm beats the Johnson bound for r ≥ 2. In the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. We give a deterministic list-decoder that works at error rate below J(21-r), where J(δ) denotes the Johnson radius for minimum distance δ. This shows that RM(2,m) codes are list-decodable up to radius η for any constant η < 1/2 in time polynomial in the block-length. Over small fields Fq, we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. We conjecture that the list-decoding radius approaches the minimum distance (like over F), and prove this holds true when the degree is divisible by q-1.

The problem of polynomial interpolation is to reconstruct a polynomial based on its valuations on a set of inputs I. We consider the problem over $\mathbb{Z}_m$ when m is composite. We ask the following question: Given $I \subseteq \mathbb{Z}_m$, how many evaluations of a polynomial at points in I are required to compute its value at every point in I? Surprisingly for composite m, this number can vary exponentially between $\log |I|$ and $|I|$, in contrast to the prime case where $|I|$ evaluations are necessary. While we show this minimization problem to be NP-hard, we give an efficient algorithm of query complexity within a factor t of the optimum, where t is the number of prime factors of m. We use our interpolation algorithm to design algorithms for zero testing and distributional learning of polynomials over $\mathbb{Z}_m$. In some cases, we get an exponential improvement over known algorithms in query complexity and running time. Our main technical contribution is the notion of an interpolating set for I which is a subset S of I such that a polynomial which is 0 over S must be 0 at every point in I. Any interpolation algorithm needs to query an interpolating set for I. Our query-efficient algorithms are obtained by constructing interpolating sets whose size is close to optimal.

We show that any deterministic data-stream algorithm that, makes a constant number of passes over the input and gives a constant, factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space Omega(radicn). This proves a conjecture made by Gopalan, Jayram, Krauthgamer and Kumar |10| who proved a matching upper bound. Our results yield asymptotically tight tower bounds for all approximation factors, thus resolving the main open problem, from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

We study the polynomial reconstruction problem, for low-degree multivariate polynomials over F[2]. In this problem, we are given a set of points x epsi {0, 1}nand target values f(x) epsi {0, 1} for each of these points, with the promise that there is a polynomial over F[2] of degree at most d that agrees with f at 1 - epsiv fraction of the points. Our goal is to find agree d polynomial that has good-agreement with f. We show that it is NP-hard to find a polynomial that agrees with f on more than 1 - 2-d+ delta fraction of the points for any epsiv, delta > 0. This holds even with the stronger promise that the polynomial that fits the data is in fact linear, wherejis the algorithm is allowed to find a polynomial of degree d. Previously the only known, hardness of approximation (or even NP-completeness) was for the case when d = I, which follows from a celebrated result of Has tad. In the setting of computational learning, our result shows the hardness of (non-proper) agnostic learning of parities, where the learner is allowed, a low-degree polynomial over F[2] as a hypothesis. This is the first non-proper hardness result for this central problem in computational learning. Our results extend-to multivariate polynomial reconstruction over any finite field.

We address well-studied problems concerning the learn-ability of parities and halfspaces in the presence of classification noise. Learning of parities under the uniform distribution with random classification noise, also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding learning under the uniform distribution to learning of noisy parities. We show that under the uniform distribution, learning parities with adversarial classification noise reduces to learning parities with random classification noise. Together with the parity learning algorithm of Blum et al. (2003), this gives the first nontrivial algorithm for learning parities with adversarial noise. We show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables. We show that learning of k-juntas reduces to learning noisy parities of k variables. These reductions work even in the presence of random classification noise in the original DNF or junta. We then consider the problem of learning halfspaces over Qopfnwith adversarial noise or finding a halfspace that maximizes the agreement rate with a given set of examples. We prove an essentially optimal hardness factor of 2 - epsi, improving the factor of (85/84) - epsi due to Bshouty and Burroughs (2002). Finally, we show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem

We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied by M. Minsky and S. Papert (1968) and J. Aspnes (1994), relatively little is known about their sparsity. We study this problem using Descartes rule of signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. We show that sign representing parity over {0,1,..., m - 1}/sup n/ with the degree in each variable at most m - 1 requires sparsity at least m/sup n/. We show a bound of (m - l)/sup n/ for weak representations. We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1 on the sparsity of polynomials of any degree representing parity over {0, 1, ..., m -1 }/sup n/. We prove exact bounds on the sparsity of such polynomials for any two element subset A. We show that for depth-two and-or-not circuits with a threshold gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain basis. We use this to give a simple proof that such circuits need size (3/2)/sup n/ to compute parity, which improves on previous bounds by M. Goldmann (1997). We also show a tight lower bound of 2/sup n/ for the inner product function over {0,1}/sup n/ /spl times/ {0,1}/sup n/. The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.

We study the problem of representing symmetric Boolean functions as symmetric polynomials over /spl Zopf//sub m/. We show an equivalence between such representations and simultaneous communication protocols. Computing a function f on 0 - 1 inputs with a polynomial of degree d modulo pq is equivalent to a two player simultaneous protocol for computing f where one player is given the first [log/sub p/d] digits of the weight in base q. This reduces the problem of proving bounds on the degree of symmetric polynomials to proving bounds on simultaneous communication protocols. We use this equivalence to show lower bounds of /spl Omega/(n) on symmetric polynomials weakly representing classes of Mod/sub r/ and Threshold functions. We show there exist symmetric polynomials over /spl Zopf//sub m/ of degree o(n) strongly representing Threshold c for c constant, using the fact that the number of solutions of certain exponential Diophantine equations are finite. Conversely, the fact that the degree is o(n) implies that some classes of Diophantine equations can have only finitely many solutions. Our results give simplifications of many previously known results and show that polynomial representations are intimately related to certain questions in number theory.