Over the last three decades, function testing has been extensively studied over Boolean, finite fields, and discrete settings. However, to encode the real-world applications more succinctly, function testing over the reals (where the domain and range, both are reals) is of prime importance. Recently, there have been some works in the direction of testing for algebraic representations of such functions: the work by Fleming and Yoshida (ITCS 20), Arora, Kelman, and Meir (SOSA 25) on linearity testing and the work of Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 23) for testing low-degree polynomials. Our work follows the same avenue, wherein we study three well-studied sparse representations of functions, over the reals, namely (i) k-linearity, (ii) k-sparse, low-degree polynomials, and (iii) k-juntas. In this setting, given approximate query access to some f:ℝⁿ → ℝ, we want to decide if the function satisfies some property of interest, or if it is far from all functions that satisfy the property. Here, the distance is measured in the 𝓁₁-metric, under the assumption that we are drawing samples from the Standard Gaussian distribution. We present efficient testers and Ω(k) lower bounds for testing each of these three properties.

Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. Prior work has shown that given a distribution P defined as the marginal distribution of a Bayes net, it is NP-hard to decide whether there is a parameter-bounded Bayes net that represents P. They called this problem LEARN. In this work, we extend the NP-hardness result of LEARN and prove the NP-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net. We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution P, represented by some parameter-bounded Bayes net, thereby generalizing a degree-bounded sample complexity literature result.

We provide efficient algorithms for the problem of distribution learning from high-dimensional Gaussian data where in each sample, some of the variable values are missing. We suppose that the variables are {\em missing not at random (MNAR)}. The missingness model, denoted by $\mathbb{S}(\mathbf{y})$, is the function that maps any point $\mathbf{y}\in \mathbb{R}^d$ to the subsets of its coordinates that are seen. In this work, we assume that it is known. We study the following two settings: - [\textbf{Self-censoring}] An observation $\mathbf{x}$ is generated by first sampling the true value $\mathbf{y}$ from a $d$-dimensional Gaussian $\mathcal{N}(\mathbf{\mu}^*, \Sigma^*)$ with unknown $\mathbf{\mu}^*$ and $\Sigma^*$. For each coordinate $i$, there exists a set $S_i\subseteq \mathbb{R}^d$ such that $x_i=y_i$ if and only if $y_i\in S_i$. Otherwise, $x_i$ is missing and takes a generic value (e.g “?"). We design an algorithm that learns $\mathcal{N}(\mathbf{\mu}^*, \Sigma^*)$ up to TV distance $\varepsilon$, using $\textup{poly}(d, 1/\varepsilon)$ samples, assuming only that each pair of coordinates is observed with sufficiently high probability. - [\textbf{Linear thresholding}] An observation $\mathbf{x}$ is generated by first sampling $\mathbf{y}$ from a $d$-dimensional Gaussian $\mathcal{N}(\mathbf{\mu}^*, \Sigma)$ with unknown $\mathbf{\mu}^*$ and known $\Sigma$, and then applying the missingness model $\mathbb{S}$ where $\mathbb{S}(\mathbf{y}) = \{i \in [d]: \mathbf{v}_i^T \mathbf{y} \leq b_i\}$ for some $\mathbf{v}_1, …, \mathbf{v}_d \in \mathbb{R}^d$ and $b_1, …, b_d \in \mathbb{R}$. We design an efficient mean estimation algorithm, assuming that none of the possible missingness patterns is very rare conditioned on the values of the observed coordinates and that any small subset of coordinates is observed with sufficiently high probability.

We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm for checking equivalence between mixtures of product distributions, over arbitrary alphabets. This corresponds to a special case, whereby the TV distance between the two distributions is zero. Second, we prove that unless $\mathsf{NP} \subseteq \mathsf{RP}$ it is impossible to efficiently estimate the TV distance between arbitrary Ising models, even in a bounded-error randomized setting.

We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaussian distribution $N(\mu, \Sigma)$ in the PAC learning setting. Classically, in the advice-free setting, $\widetilde{\Theta}(d^2/\varepsilon^2)$ samples are sufficient and worst case necessary to learn $d$-dimensional Gaussians up to TV distance $\varepsilon$ with constant probability. When we are additionally given a parameter $\widetilde{\Sigma}$ as advice, we show that $\widetilde{\mathcal{O}}(d^{2-\beta}/\varepsilon^2)$ samples suffices whenever $|| \widetilde{\Sigma}^{-1/2} \Sigma \widetilde{\Sigma}^{-1/2} - I_d ||_1 \leq \varepsilon d^{1-\beta}$ (where $||\cdot||_1$ denotes the entrywise $\ell_1$ norm) for any $\beta > 0$, yielding a polynomial improvement over the advice-free setting.

Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\{0,1\}^d$, it is known that $\Omega(d/\epsilon^2)$ samples are necessary to learn $P$ within total variation (TV) distance $\epsilon$. We revisit this problem when the learner is also given as advice the parameters of a product distribution $Q$. We show that there is an efficient algorithm to learn $P$ within TV distance $\epsilon$ that has sample complexity $\tilde{O}(d^{1-\eta}/\epsilon^2)$, if $\|\mathbf{p} - \mathbf{q}\|_1<\epsilon d^{0.5 - \Omega(\eta)}$. Here, $\mathbf{p}$ and $\mathbf{q}$ are the mean vectors of $P$ and $Q$ respectively, and no bound on $\|\mathbf{p} - \mathbf{q}\|_1$ is known to the algorithm a priori.

This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. The problem of efficiently counting and sampling graphical structures, such as spanning trees and acyclic orientations, has been a vibrant area of research in algorithms. We show that this rich algorithmic foundation can be leveraged to develop new algorithms for learning high-dimensional graphical models. We present the first efficient algorithm for (both realizable and agnostic) learning of Bayes nets with a chordal skeleton. In particular, we present an algorithm that, given integers $k,d > 0$, error parameter $\varepsilon > 0$, an undirected chordal graph $G$ on $n$ vertices, and sample access to a distribution $P^\ast$ on $[k]^n$; (1) returns a Bayes net $\widehat{P}$ with skeleton $G$ and indegree $d$, whose KL-divergence from $P^\ast$ is at most $\varepsilon$ more than the optimal KL-divergence between $P^\ast$ and any Bayes net with skeleton $G$ and indegree $d$, (2) uses $\widetilde{O}(n^3k^{d+1}/\varepsilon^2)$ samples from $P^\ast$ and runs in time $\mathrm{poly}(n,k,\varepsilon^{-1})$ for constant $d$. Prior results in this spirit were for only for trees ($d=1$, tree skeleton) via Chow-Liu, and in the realizable setting for polytrees (arbitrary $d$ but tree skeleton). Thus, our result significantly extends the state-of-the-art in learning Bayes net distributions. We also establish new results for learning tree and polytree distributions.

We establish finite-sample guarantees for efficient proper learning of bounded-degree {\em polytrees}, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight.

We study the problem of robust multivariate polynomial regression: let $p\colon\mathbb{R}^n\to\mathbb{R}$ be an unknown $n$-variate polynomial of degree at most $d$ in each variable. We are given as input a set of random samples $(\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R}$ that are noisy versions of $(\mathbf{x}_i,p(\mathbf{x}_i))$. More precisely, each $\mathbf{x}_i$ is sampled independently from some distribution $χ$ on $[-1,1]^n$, and for each $i$ independently, $y_i$ is arbitrary (i.e., an outlier) with probability at most $ρ< 1/2$, and otherwise satisfies $|y_i-p(\mathbf{x}_i)|\leqσ$. The goal is to output a polynomial $\hat{p}$, of degree at most $d$ in each variable, within an $\ell_\infty$-distance of at most $O(σ)$ from $p$. Kane, Karmalkar, and Price [FOCS'17] solved this problem for $n=1$. We generalize their results to the $n$-variate setting, showing an algorithm that achieves a sample complexity of $O_n(d^n\log d)$, where the hidden constant depends on $n$, if $χ$ is the $n$-dimensional Chebyshev distribution. The sample complexity is $O_n(d^{2n}\log d)$, if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most $O(σ)$, and the run-time depends on $\log(1/σ)$. In the setting where each $\mathbf{x}_i$ and $y_i$ are known up to $N$ bits of precision, the run-time's dependence on $N$ is linear. We also show that our sample complexities are optimal in terms of $d^n$. Furthermore, we show that it is possible to have the run-time be independent of $1/σ$, at the cost of a higher sample complexity.

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between same-structure distributions over any class of Bayes nets for which there is an efficient probabilistic inference algorithm. In particular, it leads to an FPRAS for estimating TV distances between distributions that are defined over a common Bayes net of small treewidth. Prior to this work, such approximation schemes only existed for estimating TV distances between product distributions. Our approach employs a new notion of partial couplings of high-dimensional distributions, which might be of independent interest.

We study the problem of online unweighted bipartite matching with $n$ offline vertices and $n$ online vertices where one wishes to be competitive against the optimal offline algorithm. While the classic RANKING algorithm of (Karp et al., 1990) provably attains competitive ratio of $1-1/e > 1/2$, we show that no learning-augmented method can be both 1-consistent and strictly better than 1/2-robust under the adversarial arrival model. Meanwhile, under the random arrival model, we show how one can utilize methods from distribution testing to design an algorithm that takes in external advice about the online vertices and provably achieves competitive ratio interpolating between any ratio attainable by advice-free methods and the optimal ratio of 1, depending on the advice quality.

Interpretations of logical formulas over semirings (other than the Boolean semiring) have applications in various areas of computer science including logic, AI, databases, and security. Such interpretations provide richer information beyond the truth or falsity of a statement. Examples of such semirings include Viterbi semiring, min-max or access control semiring, tropical semiring, and fuzzy semiring. The present work investigates the complexity of constraint optimization problems over semirings. The generic optimization problem we study is the following: Given a propositional formula phi over n variable and a semiring (K,+, . ,0,1), find the maximum value over all possible interpretations of phi over K. This can be seen as a generalization of the well-known satisfiability problem (a propositional formula is satisfiable if and only if the maximum value over all interpretations/assignments over the Boolean semiring is 1). A related problem is to find an interpretation that achieves the maximum value. In this work, we first focus on these optimization problems over the Viterbi semiring, which we call optConfVal and optConf. We first show that for general propositional formulas in negation normal form, optConfVal and optConf are in FP^NP. We then investigate optConf when the input formula phi is represented in the conjunctive normal form. For CNF formulae, we first derive an upper bound on the value of optConf as a function of the number of maximum satisfiable clauses. In particular, we show that if r is the maximum number of satisfiable clauses in a CNF formula with m clauses, then its optConf value is at most 1/4^(m-r). Building on this we establish that optConf for CNF formulae is hard for the complexity class FP^NP[log]. We also design polynomial-time approximation algorithms and establish an inapproximability for optConfVal. We establish similar complexity results for these optimization problems over other semirings including tropical, fuzzy, and access control semirings.

We study the sample complexity of causal structure learning on a two-variable system with observational and experimental data. Specifically, for two variables $X$ and $Y$, we consider the classical scenario where either $X$ causes $Y$, $Y$ causes $X$, or there is an unmeasured confounder between $X$ and $Y$. Let $m_1$ be the number of observational samples of $(X,Y)$, and let $m_2$ be the number of interventional samples where either $X$ or $Y$ has been subject to an external intervention. We show that if $X$ and $Y$ are over a finite domain of size $k$ and are significantly correlated, the minimum $m_2$ needed is sublinear in $k$. Moreover, as $m_1$ grows, the minimum $m_2$ needed to identify the causal structure decreases. In fact, we can give a tight characterization of the tradeoff between $m_1$ and $m_2$ when $m_1 = O(k)$ or is sufficiently large. We build upon techniques for closeness testing when $m_1$ is small (e.g., sublinear in $k$), and for non-parametric density estimation when $m_2$ is large. Our hardness results are based on carefully constructing causal models whose marginal and interventional distributions form hard instances of canonical results on property testing.

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) $G^*$ while minimizing the number of interventions made. In our setting, we are additionally given side information about $G^*$ as advice, e.g. a DAG $G$ purported to be $G^*$. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on _algorithms with predictions_. When the advice is a DAG $G$, we design an adaptive search algorithm to recover $G^*$ whose intervention cost is at most $\mathcal{O}(\max\{1, \log \psi\})$ times the cost for verifying $G^*$; here, $\psi$ is a distance measure between $G$ and $G^*$ that is upper bounded by the number of variables $n$, and is exactly 0 when $G=G^*$. Our approximation factor matches the state-of-the-art for the advice-less setting.

Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV distance of two product distributions over the domain {0,1}^n. In particular, we establish the following results. 1. The problem of exactly computing the TV distance of two product distributions is #P-complete. This is in stark contrast with other distance measures such as KL, Chi-square, and Hellinger which tensorize over the marginals leading to efficient algorithms. 2. There is a fully polynomial-time deterministic approximation scheme (FPTAS) for computing the TV distance of two product distributions P and Q where Q is the uniform distribution. This result is extended to the case where Q has a constant number of distinct marginals. In contrast, we show that when P and Q are Bayes net distributions the relative approximation of their TV distance is NP-hard.

This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution P over {0, 1}n, given sample access toP. We show that the sample complexity of the problem is Θ(2n/2/ε2). Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this framework, we develop new algorithms for "near-proper" learning of Bayes nets, and high-probability learning under χ2divergence, which are of independent interest.1

We study the problem of testing whether a function f : ℝn → ℝ is a polynomial of degree at most d in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution D over ℝn from which we can draw samples. In contrast to previous work, we do not assume that D has finite support. We design a tester that given query access to f, and sample access to D, makes poly(d/ε) many queries to f, accepts with probability 1 if f is a polynomial of degree d, and rejects with probability at least 2/3 if every degree-d polynomial P disagrees with f on a set of mass at least ε with respect to D. Our result also holds under mild assumptions when we receive only a polynomial number of bits of precision for each query to f, or when f can only be queried on rational points representable using a logarithmic number of bits. Along the way, we prove a new stability theorem for multivariate polynomials that may be of independent interest. * The arXiv version of the paper can be accessed at https://arxiv.org/abs/2204.08404

Abstract. We provide finite sample guarantees for the classical Chow–Liu algorithm [Chow and Liu, IEEE Trans. Inform. Theory, 14 (1968), pp. 462–467] to learn a tree-structured graphical model of a distribution. For a distribution [Formula: see text] on [Formula: see text] and a tree [Formula: see text] on [Formula: see text] nodes, we say [Formula: see text] is an [Formula: see text]-approximate tree for [Formula: see text] if there is a [Formula: see text]-structured distribution [Formula: see text] such that [Formula: see text] is at most [Formula: see text] more than the best possible tree-structured distribution for [Formula: see text]. We show that if [Formula: see text] itself is tree-structured, then the Chow–Liu algorithm with the plug-in estimator for mutual information with [Formula: see text] independent and identically distributed samples outputs an [Formula: see text]-approximate tree for [Formula: see text] with constant probability. In contrast, for a general [Formula: see text] (which may not be tree-structured), [Formula: see text] samples are necessary to find an [Formula: see text]-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne et al. [ Proceedings of the 50 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 735–748]: we prove that for three random variables [Formula: see text] each over [Formula: see text], testing if [Formula: see text] is 0 or [Formula: see text] is possible with [Formula: see text] samples. Finally, we show that for a specific tree [Formula: see text], with [Formula: see text] samples from a distribution [Formula: see text] over [Formula: see text], one can efficiently learn the closest [Formula: see text]-structured distribution in KL divergence by applying the add-1 estimator at each node.

Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP’s and computation of zeroth frequency moments ( F 0 ) for data streams. Our investigations lead us to observe a striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and F 0 computation. We design a recipe for translating algorithms developed for F 0 estimation to model counting, resulting in new algorithms for model counting. We also provide a recipe for transforming sampling algorithm over streams to constraint sampling algorithms. We then observe that algorithms in the context of distributed streaming can be transformed into distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing F 0 estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields an algorithm for multidimensional range efficient F 0 estimation with a simpler analysis.

We study identifiability of linear Andersson-Madigan-Perlman (AMP) chain graph models, which are a common generalization of linear structural equation models and Gaussian graphical models. AMP models are described by DAGs on chain components which themselves are undirected graphs. For a known chain component decomposition, we show that the DAG on the chain components is identifiable if the determinants of the residual covariance matrices of the chain components are equal (or more generally, monotone non-decreasing in topological order). This condition extends the equal variance identifiability criterion for Bayes nets, and it can be generalized from determinants to any super-additive function on positive semidefinite matrices. When the component decomposition is unknown, we describe conditions that allow recovery of the full structure using a polynomial time algorithm based on submodular function minimization. We also conduct experiments comparing our algorithm's performance against existing baselines.

Gaussian Bayesian networks are widely used to model causal interactions among continuous variables. In this work, we study the problem of learning a fixed-structure Gaussian Bayesian network up to a bounded error in total variation distance. We analyze the commonly used node-wise least squares regression LeastSquares and prove that it has the near-optimal sample complexity. We also study a couple of new algorithms for the problem: BatchAvgLeastSquares takes the average of several batches of least squares solutions at each node, so that one can interpolate between the batch size and the number of batches. We show that BatchAvgLeastSquares also has near-optimal sample complexity. CauchyEst takes the median of solutions to several batches of linear systems at each node. We show that the algorithm specialized to polytrees, CauchyEstTree, has near-optimal sample complexity. Experimentally, we show that for uncontaminated, realizable data, the LeastSquares algorithm performs best, but in the presence of contamination or DAG misspecification, CauchyEst/CauchyEstTree and BatchAvgLeastSquares respectively perform better.

We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let P be a causal model on a set V of observable variables on a given causal graph G. For sets $X,Y \subseteq V$, and setting x to $X$, $P_x(Y)$ denotes the interventional distribution on Y with respect to an intervention x to variables X. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), proved that the ID algorithm is sound and complete for recovering P_x(Y) from observations. We give the first provably efficient version of the ID algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph G on observable variables V, a setting x of a set $X \subseteq V$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is epsilon-close (in total variation distance) to $P_x(Y)$ where $Y = V X$, if $P_x(Y)$ is identifiable. We also show that when Y is an arbitrary subset of $V X$, there is no efficient algorithm that outputs an evaluator of a distribution that is epsilon-close to $P_x(Y)$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.

A universal 1-bit compressive sensing (CS) scheme consists of a measurement matrix A such that for all signals x belonging to a particular class, x can be approximately recovered from sign(Ax). 1-bit CS models extreme quantization effects where only one bit of information is revealed per measurement. We focus on universal support recovery for 1-bit CS in the case of sparse signals with bounded dynamic range. Specifically, a vector x ∈ℝnis said to have sparsity k if it has at most k nonzero entries and dynamic range R if the ratio between its largest and smallest nonzero entries is at most R in magnitude. Our main result shows that if the entries of the measurement matrix Ax are i.i.d. Gaussians, then the number of measurements needs to be ${{\tilde \Omega }}\left({R{k^{3/2}}}\right)$ to recover the support of k-sparse signals with dynamic range R using 1-bit CS. This contrasts with the known lower bound of ${{\tilde \Omega }}\left({{k^2}\log n}\right)$ for the number of measurements to recover the support of arbitrary k-sparse signals. In broad scaling regimes of interest, our lower bounds match upper bounds implicit in prior works up to logarithmic factors.

We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact only linearly many samples are required.Specifically, if $P$ is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by $d$, then $\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.

We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of $\textit{covered edges}$, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using $\mathcal{O}(\log n)$ times the optimal number of interventions needed to $\textit{verify}$ (verifying size) the underlying DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search algorithm on an essential line graph has worst case approximation ratio of $\Omega(\log n)$ with respect to the verifying size. With bounded size interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log n \cdot \log k)$ factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.

We propose a new causal inference framework to learn causal effects from multiple, decentralized data sources in a federated setting. We introduce an adaptive transfer algorithm that learns the similarities among the data sources by utilizing Random Fourier Features to disentangle the loss function into multiple components, each of which is associated with a data source. The data sources may have different distributions; the causal effects are independently and systematically incorporated. The proposed method estimates the similarities among the sources through transfer coefficients, and hence requiring no prior information about the similarity measures. The heterogeneous causal effects can be estimated with no sharing of the raw training data among the sources, thus minimizing the risk of privacy leak. We also provide minimax lower bounds to assess the quality of the parameters learned from the disparate sources. The proposed method is empirically shown to outperform the baselines on decentralized data sources with dissimilar distributions.

In this paper, we study high-dimensional estimation from truncated samples. We focus on two fundamental and classical problems: (i) inference of sparse Gaussian graphical models and (ii) support recovery of sparse linear models. (i) For Gaussian graphical models, suppose d-dimensional samples x are generated from a Gaussian N(mu, Sigma) and observed only if they belong to a subset S of R^d. We show that mu and Sigma can be estimated with error epsilon in the Frobenius norm, using O (nz(Sigma^{-1})/epsilon^2) samples from a truncated N(mu, Sigma) and having access to a membership oracle for S. The set S is assumed to have non-trivial measure under the unknown distribution but is otherwise arbitrary. (ii) For sparse linear regression, suppose samples (x,y) are generated where y = + N(0,1) and (x, y) is seen only if y belongs to a truncation set S of the reals. We consider the case that Omega* is sparse with a support set of size k. Our main result is to establish precise conditions on the problem dimension d, the support size k, the number of observations n, and properties of the samples and the truncation that are sufficient to recover the support of Omega*. Specifically, we show that under some mild assumptions, only O(k^2 log d) samples are needed to estimate Omega* in the infinity-norm up to a bounded error. Similar results are also estabilished for estimating Omega* in the Euclidean norm up to arbitrary error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ell_1-regularization term. Cite this Paper BibTeX @InProceedings{pmlr-v130-bhattacharyya21a, title = { Efficient Statistics for Sparse Graphical Models from Truncated Samples }, author = {Bhattacharyya, Arnab and Desai, Rathin and Ganesh Nagarajan, Sai and Panageas, Ioannis}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {1450--1458}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/bhattacharyya21a/bhattacharyya21a.pdf}, url = {https://proceedings.mlr.press/v130/bhattacharyya21a.html}, abstract = { In this paper, we study high-dimensional estimation from truncated samples. We focus on two fundamental and classical problems: (i) inference of sparse Gaussian graphical models and (ii) support recovery of sparse linear models. (i) For Gaussian graphical models, suppose d-dimensional samples x are generated from a Gaussian N(mu, Sigma) and observed only if they belong to a subset S of R^d. We show that mu and Sigma can be estimated with error epsilon in the Frobenius norm, using O (nz(Sigma^{-1})/epsilon^2) samples from a truncated N(mu, Sigma) and having access to a membership oracle for S. The set S is assumed to have non-trivial measure under the unknown distribution but is otherwise arbitrary. (ii) For sparse linear regression, suppose samples (x,y) are generated where y = + N(0,1) and (x, y) is seen only if y belongs to a truncation set S of the reals. We consider the case that Omega* is sparse with a support set of size k. Our main result is to establish precise conditions on the problem dimension d, the support size k, the number of observations n, and properties of the samples and the truncation that are sufficient to recover the support of Omega*. Specifically, we show that under some mild assumptions, only O(k^2 log d) samples are needed to estimate Omega* in the infinity-norm up to a bounded error. Similar results are also estabilished for estimating Omega* in the Euclidean norm up to arbitrary error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ell_1-regularization term. } } Copy to Clipboard Download Endnote %0 Conference Paper %T Efficient Statistics for Sparse Graphical Models from Truncated Samples %A Arnab Bhattacharyya %A Rathin Desai %A Sai Ganesh Nagarajan %A Ioannis Panageas %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-bhattacharyya21a %I PMLR %P 1450--1458 %U https://proceedings.mlr.press/v130/bhattacharyya21a.html %V 130 %X In this paper, we study high-dimensional estimation from truncated samples. We focus on two fundamental and classical problems: (i) inference of sparse Gaussian graphical models and (ii) support recovery of sparse linear models. (i) For Gaussian graphical models, suppose d-dimensional samples x are generated from a Gaussian N(mu, Sigma) and observed only if they belong to a subset S of R^d. We show that mu and Sigma can be estimated with error epsilon in the Frobenius norm, using O (nz(Sigma^{-1})/epsilon^2) samples from a truncated N(mu, Sigma) and having access to a membership oracle for S. The set S is assumed to have non-trivial measure under the unknown distribution but is otherwise arbitrary. (ii) For sparse linear regression, suppose samples (x,y) are generated where y = + N(0,1) and (x, y) is seen only if y belongs to a truncation set S of the reals. We consider the case that Omega* is sparse with a support set of size k. Our main result is to establish precise conditions on the problem dimension d, the support size k, the number of observations n, and properties of the samples and the truncation that are sufficient to recover the support of Omega*. Specifically, we show that under some mild assumptions, only O(k^2 log d) samples are needed to estimate Omega* in the infinity-norm up to a bounded error. Similar results are also estabilished for estimating Omega* in the Euclidean norm up to arbitrary error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an ell_1-regularization term. Copy to Clipboard Download APA Bhattacharyya, A., Desai, R., Ganesh Nagarajan, S. & Panageas, I.. (2021). Efficient Statistics for Sparse Graphical Models from Truncated Samples . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:1450-1458 Available from https://proceedings.mlr.press/v130/bhattacharyya21a.html. Copy to Clipboard Download Related Material Download PDF Supplementary ZIP

We study the problems of {\em identity} and {\em closeness testing} of $n$-dimensional product distributions. Prior works of Canonne, Diakonikolas, Kane and Stewart (COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample complexity bounds for {\em non-tolerant testing over a binary alphabet}: given two product distributions $P$ and $Q$ over a binary alphabet, distinguish between the cases $P=Q$ and $d_{\mathrm{TV}}(P,Q)>\epsilon$. We build on this prior work to give a more comprehensive map of the complexity of testing of product distributions by investigating {\em tolerant testing with respect to several natural distance measures and over an arbitrary alphabet}. Our study gives a fine-grained understanding of how the sample complexity of tolerant testing varies with the distance measures for product distributions. In addition, we also extend one of our upper bounds on product distributions to bounded-degree Bayes nets.

Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments F0 for data streams.

We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans. Inform. Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution P on Σn and a tree T on n nodes, we say T is an ε-approximate tree for P if there is a T-structured distribution Q such that D(P || Q) is at most ε more than the best possible tree-structured distribution for P. We show that if P itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with O(|Σ|3 nε−1) i.i.d. samples outputs an ε-approximate tree for P with constant probability. In contrast, for a general P (which may not be tree-structured), Ω(n2ε−2) samples are necessary to find an ε-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart (STOC, 2018): we prove that for three random variables X,Y,Z each over Σ, testing if I(X; Y ∣ Z) is 0 or ≥ ε is possible with O(|Σ|3/ε) samples. Finally, we show that for a specific tree T, with O(|Σ|2nε−1) samples from a distribution P over Σn, one can efficiently learn the closest T-structured distribution in KL divergence by applying the add-1 estimator at each node.

The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that -Even Set is W [1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP) , in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any , -SVP is W [1]-hard to approximate (under randomized reductions) to some constant factor.

We study the problem of efficiently estimating the effect of an intervention on a single variable using observational samples. Our goal is to give algorithms with polynomial time and sample complexity in a non-parametric setting. Tian and Pearl (AAAI ’02) have exactly characterized the class of causal graphs for which causal effects of atomic interventions can be identified from observational data. We make their result quantitative. Suppose 𝒫 is a causal model on a set V of n observable variables with respect to a given causal graph G, and let do(x) be an identifiable intervention on a variable X. We show that assuming that G has bounded in-degree and bounded c-components (k) and that the observational distribution satisfies a strong positivity condition: (i) [Evaluation] There is an algorithm that outputs with probability 2/3 an evaluator for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The evaluator can return in O(n) time the probability P^(v) for any assignment v to V. (ii) [Sampling] There is an algorithm that outputs with probability 2/3 a sampler for a distribution P^ that satisfies TV(P(V | do(x)), P^(V)) < eps using m=O (n/eps^2) samples from P and O(mn) time. The sampler returns an iid sample from P^ with probability 1 in O(n) time. We extend our techniques to estimate P(Y | do(x)) for a subset Y of variables of interest. We also show lower bounds for the sample complexity, demonstrating that our sample complexity has optimal dependence on the parameters n and eps, as well as if k=1 on the strong positivity parameter.

A code is called a $q$-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index $i$ and a received word $w$ close to an encoding of a message $x$, outputs $x_i$ by querying only at most $q$ coordinates of $w$. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for $3$-query binary LDCs of dimension $k$ and length $n$, the best known bounds are: $2^{k^{o(1)}} \geq n \geq \tildeΩ(k^2)$. In this work, we take a second look at binary $3$-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of $\tildeΩ(k^2)$ for the length of strong $3$-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to $2$-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.

We design efficient distance approximation algorithms for several classes of well-studied structured high-dimensional distributions. Specifically, we present algorithms for the following problems (where dTV is the total variation distance): Given sample access to two Bayesian networks P1 and P2 over known directed acyclic graphs G1 and G2 having n nodes and bounded in-degree, approximate dTV(P1, P2) to within additive error ε using poly(n, 1/ε) samples and time. Given sample access to two ferromagnetic Ising models P1 and P2 on n variables with bounded width, approximate dTV(P1 , P2 ) to within additive error ε using poly(n, 1/ε) samples and time. Given sample access to two n-dimensional Gaussians P1 and P2, approximate dTV(P1, P2) to within additive error ε using poly(n, 1/ε) samples and time. Given access to observations from two causal models P and Q on n variables that are defined over known causal graphs, approximate dTV(Pa , Qa ) to within additive error ε using poly(n, 1/ε) samples and time, where Pa and Qa are the interventional distributions obtained by the intervention do(A = a) on P and Q respectively for a particular variable A. The distance approximation algorithms immediately imply new tolerant closeness testers for the corresponding classes of distributions. Prior to our work, only non-tolerant testers were known for both Bayes net distributions and Ising models, and no testers with quantitative guarantee were known for interventional distributions. To best of our knowledge, efficient distance approximation algorithms for Gaussian distributions were not present in the literature. Our algorithms are designed using a conceptually simple but general framework that is applicable to a variety of scenarios.

We give the first optimal bounds for returning the ℓ 1 -heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in { 1, 2, … , n } and parameters 0 < ε < φ ⩽ 1, let f i denote the frequency of item i , i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which f i ⩾ φ m , returns no items j for which f j ⩽ (φ −ε) m , and returns approximations f˜ i with | f˜ i − f i | ⩽ ε m for each item i that it returns. Our algorithm uses O (ε −1 log φ −1 + φ −1 log n + log log m ) bits of space, processes each stream update in O (1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive ε m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of ℓ 1 -heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.

We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs). In particular, we prove that for any constants $d \in \mathbb{Z}^+$ and $\eps > 0$, it is NP-hard to decide: given a set of $\{-1,1\}$-labeled points in $\mathbb{R}^n$ whether (YES Case) there exists a halfspace that classifies $(1-\eps)$-fraction of the points correctly, or (NO Case) any degree-$d$ PTF classifies at most $(1/2 + \eps)$-fraction of the points correctly. This strengthens to all constant degrees the previous NP-hardness of learning using degree-$2$ PTFs shown by Diakonikolas et al. (2011). The latter result had remained the only progress over the works of Feldman et al. (2006) and Guruswami et al. (2006) ruling out weakly proper learning adversarially noisy halfspaces.

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F_2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k. Here, k is the parameter of the problem. The question of whether k-Even Set is fixed parameter tractable (FPT) has been repeatedly raised in literature and has earned its place in Downey and Fellows' book (2013) as one of the "most infamous" open problems in the field of Parameterized Complexity. In this work, we show that k-Even Set does not admit FPT algorithms under the (randomized) Gap Exponential Time Hypothesis (Gap-ETH) [Dinur'16, Manurangsi-Raghavendra'16]. In fact, our result rules out not only exact FPT algorithms, but also any constant factor FPT approximation algorithms for the problem. Furthermore, our result holds even under the following weaker assumption, which is also known as the Parameterized Inapproximability Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only 0.99-satisfiable (where the parameter is the number of variables). We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l_p norm for some fixed p) is at most k. Similar to k-Even Set, this problem is also a long-standing open problem in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is hard to approximate (in FPT time) to some constant factor, assuming PIH. Furthermore, for the case of p = 2, the inapproximability factor can be amplified to any constant.

Sparsity is a basic property of real vectors that is exploited in a wide variety of machine learning applications. In this work, we describe property testing algorithms for sparsity that observe a low-dimensional projec- tion of the input. We consider two settings. In the first setting, we test sparsity with respect to an unknown basis: given input vectors $y_1 ,...,y_p \in R^d$ whose concatenation as columns forms $Y \in R^{d \times p}$ , does $Y = AX$ for matrices $A \in R^{d\times m}$ and $X \in R^{m \times p}$ such that each column of $X$ is $k$-sparse, or is $Y$ “far” from having such a decomposition? In the second setting, we test sparsity with respect to a known basis: for a fixed design ma- trix $A \in R^{d \times m}$ , given input vector $y \in R^d$ , is $y = Ax$ for some $k$-sparse vector $x$ or is $y$ “far” from having such a decomposition? We analyze our algorithms using tools from high-dimensional geometry and probability.

We consider testing and learning problems on causal Bayesian networks as defined by Pearl (Pearl, 2009). Given a causal Bayesian network M on a graph with n discrete variables and bounded in-degree and bounded ``confounded components'', we show that O(log n) interventions on an unknown causal Bayesian network X on the same graph, and O(n/epsilon^2) samples per intervention, suffice to efficiently distinguish whether X=M or whether there exists some intervention under which X and M are farther than epsilon in total variation distance. We also obtain sample/time/intervention efficient algorithms for: (i) testing the identity of two unknown causal Bayesian networks on the same graph; and (ii) learning a causal Bayesian network on a given graph. Although our algorithms are non-adaptive, we show that adaptivity does not help in general: Omega(log n) interventions are necessary for testing the identity of two unknown causal Bayesian networks on the same graph, even adaptively. Our algorithms are enabled by a new subadditivity inequality for the squared Hellinger distance between two causal Bayesian networks.

No abstract available.

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any 2-query locally correctable code C:{0,1}^k -> Sigma^n that can correct a constant fraction of corrupted symbols must have n >= exp(k/\log|Sigma|) under the assumption that the LCC is zero-error. We say that an LCC is zero-error if there exists a non-adaptive corrector algorithm that succeeds with probability 1 when the input is an uncorrupted codeword. All known constructions of LCCs are zero-error. Our result is tight upto constant factors in the exponent. The only previous lower bound on the length of 2-query LCCs over large alphabet was Omega((k/log|\Sigma|)^2) due to Katz and Trevisan (STOC 2000). Our bound implies that zero-error LCCs cannot yield 2-server private information retrieval (PIR) schemes with sub-polynomial communication. Since there exists a 2-server PIR scheme with sub-polynomial communication (STOC 2015) based on a zero-error 2-query locally decodable code (LDC), we also obtain a separation between LDCs and LCCs over large alphabet.

Unlike compressive sensing where the measurement outputs are assumed to be real-valued and have infinite precision, in one-bit compressive sensing, measurements are quantized to one bit, their signs. In this work, our contributions are as follows: 1. We show how to recover the support of sparse high-dimensional vectors in the 1-bit compressive sensing framework with an asymptotically near-optimal number of measurements. We do this by showing an equivalence between the task of support recovery using 1-bit compressive sensing and a well-studied combinatorial object known as Union Free Families. 2. We also improve the bounds on the number of measurements for approximately recovering vectors from 1-bit compressive sensing measurements. All our results are about universal measurements, namely the measurement schemes that work simultaneously for all sparse vectors. Our improved bounds naturally lead the way to suggest several interesting open problems.

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas. * For any fixed finite field $\mathbb{K}$, we show that the list decoding radius of the generalized Reed Muller code over $\mathbb{K}$ equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when $|\mathbb{K}|-1$ divides the order of the code [GKZ08]. * For any fixed finite field $\mathbb{K}$, we give a polynomial time algorithm to decide whether a given polynomial $P: \mathbb{K}^n \to \mathbb{K}$ can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15]. * For any fixed finite field $\mathbb{K}$, we prove that all locally characterized affine-invariant properties of functions $f: \mathbb{K}^n \to \mathbb{K}$ are testable with one-sided error. The same result was known when $\mathbb{K}$ is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field $\mathbb{F}$, an affine-invariant property of functions $f: \mathbb{K}^n \to \mathbb{F}$, where $\mathbb{K}$ is a growing field extension over $\mathbb{F}$, is testable if it is locally characterized by constraints of bounded weight.

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well-suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code $\mathcal{C} \subset Σ^{\mathbb{K}^n}$ is an $r$-query locally correctable code (LCC), where $\mathbb{K}$ is a finite field and $Σ$ is a finite alphabet, then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |Σ|}(n^{r-1}))$. Also, we show that if $\mathcal{C} \subset Σ^{\mathbb{K}^n}$ is an $r$-query locally testable code (LTC), then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |Σ|}(n^{r-2}))$. The dependence on $n$ in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty and Sudan (ITCS `13) construct affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM `11) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, upto a small error in the Gowers norm.

This work investigates the hardness of computing sparse solutions to systems of linear equations over F_2. Consider the k-EvenSet problem: given a homogeneous system of linear equations over F_2 on n variables, decide if there exists a nonzero solution of Hamming weight at most k (i.e. a k-sparse solution). While there is a simple O(n^{k/2})-time algorithm for it, establishing fixed parameter intractability for k-EvenSet has been a notorious open problem. Towards this goal, we show that unless k-Clique can be solved in n^{o(k)} time, k-EvenSet has no poly(n)2^{o(sqrt{k})} time algorithm and no polynomial time algorithm when k = (log n)^{2+eta} for any eta > 0. Our work also shows that the non-homogeneous generalization of the problem -- which we call k-VectorSum -- is W[1]-hard on instances where the number of equations is O(k log n), improving on previous reductions which produced Omega(n) equations. We also show that for any constant eps > 0, given a system of O(exp(O(k))log n) linear equations, it is W[1]-hard to decide if there is a k-sparse linear form satisfying all the equations or if every function on at most k-variables (k-junta) satisfies at most (1/2 + eps)-fraction of the equations. In the setting of computational learning, this shows hardness of approximate non-proper learning of k-parities. In a similar vein, we use the hardness of k-EvenSet to show that that for any constant d, unless k-Clique can be solved in n^{o(k)} time there is no poly(m, n)2^{o(sqrt{k}) time algorithm to decide whether a given set of m points in F_2^n satisfies: (i) there exists a non-trivial k-sparse homogeneous linear form evaluating to 0 on all the points, or (ii) any non-trivial degree d polynomial P supported on at most k variables evaluates to zero on approx. Pr_{F_2^n}[P(z) = 0] fraction of the points i.e., P is fooled by the set of points.

We give the first optimal bounds for returning the l1-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in {1, 2, ..., n} and parameters 0 < ε < φ ≤ 1, let fi denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items i for which fi ≥ φ m, returns no items j for which fj ≤ (φ -ε)m, and returns approximations ~fi with |~fi - fi| ≤ ε m for each item i that it returns. Our algorithm uses O(ε-1 logφ-1 + φ-1 log n + log log m) bits of space, processes each stream update in O(1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive ε m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of l1-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.

In analogy with the regularity lemma of Szemerédi [Sze75], regularity lemmas for polynomials proved by Green and Tao [GT09] and by Kaufman and Lovett [KL08] show that one can modify a given collection of polynomials ℱ = {P1, …, Pm} into a new collection ℱ′ so that the polynomials in ℱ′ are “pseudorandom”. These lemmas have various applications, such as (special cases of) Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from ℱ to ℱ′ in these works is not algorithmic. We define new notions of regularity for polynomials which, while being qualitatively equivalent to the above, also allow for efficient algorithms. Using the algorithmic regularity lemmas, we obtain an algorithmic version of the inverse theorem for Gowers norm (for bounded degree polynomials) over fields of high characteristic, by Green and Tao [GT09]. As an application, we show that if a polynomial P of degree d is within (normalized) Hamming distance of some unknown polynomial of degree k over a prime field (for k < d < | |), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance of P, for some η depending on ε, This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius, in the sense of finding one close codeword, when the received word P itself is a polynomial (of degree larger than k but smaller than | |). We also show an algorithmic inverse theorem for polynomials over fields of small characteristic and somewhat simplify the original proof by Tao and Ziegler [TZ12]. We also obtain an algorithmic version of the worstcase to average-case reductions by Kaufman and Lovett [KL08]. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d − 1. We give an effcient algorithm to find this collection. Finally, our algorithmic regularity lemma over low characteristics can be used to effciently decompose low-degree polynomials over n (for any prime order field ) into polynomials P1, …, Pm: n → that satisfy prescribed degree bounds and for which P(x) = Λ(P1(x), …. Pm(x)) for a given m and Λ.

We study convergence of the following discrete-time non-linear dynamical system: $n$ agents are located in Rd and at every time step, each moves synchronously to the average location of all agents within a unit distance of it. This popularly studied system was introduced by Krause to model the dynamics of opinion formation and is often referred to as the Hegselmann-Krause model. We prove the first polynomial time bound for the convergence of this system in arbitrary dimensions. This improves on the bound of nO(n) resulting from a more general theorem of Chazelle [4]. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n3).

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, for instance, that the Reed-Muller code over Fp of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials, except that having low degree is preserved by composition with affine maps. The complexity of an affine-invariant property refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize . A more precise statement of our main result is that for any fixed prime p ≥ 2 and fixed integer R ≥ 2, any affine-invariant property of functions f : Fnp → [R] is testable, if the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.

Set F = Fp for any fixed prime p ≥ 2. An affine-invariant property is a property of functions over Fn that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property cP, meaning that given an input function f, we make a constant number of queries to f, always accept if f satisfies cP, and otherwise reject with probability larger than a positive number that depends only on the distance between f and cP. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable.

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest $k$-TC-spanner of a given directed graph. We completely resolve the approximability of $2$-TC-spanners, showing that it is $\Theta(\log n)$ unless $\textsf{P} = \textsf{NP}$. For $k>2$, we present a polynomial time algorithm that finds a $k$-TC-spanner with size within $O((n \log n)^{1-1/k})$ of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when $k>3$: Directed $k$-Spanner, Client/Server Directed $k$-Spanner, and $k$-Diameter Spanning Subgraph. For constant $k \geq 3$, we show that the size of the sparsest $k$-TC-spanner is hard to approximate within a factor of $2^{\log^{1-\eps} n}$ for any $\eps \in (0,1)$ unless $\NP \subseteq \text{DTIME}(n^{\polylog n})$. Finally, we study the size of the sparsest $k$-TC-spanners for $H$-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with $O(\log^2 n /\eps)$ queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was $O(\sqrt{n/\eps})$.

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as G and (2) diameter at most k. Transitive-closure spanners are used in access control, property testing and data structures. We show a connection between 2-TC-spanners and local monotonicity filters. A local monotonicity filter, introduced by Saks and Seshadhri [SIAM J. Comput., pp. 2897–2926], is a randomized algorithm that, given access to an oracle for an almost monotone function $f : \{1,2,\dots,m\}^d \to \mathbb{R}$, can quickly evaluate a related function $g : \{1,2,\dots,m\}^d \to \mathbb{R}$ which is guaranteed to be monotone. Furthermore, the filter can be implemented in a distributed manner. We show that an efficient local monotonicity filter implies a sparse 2-TC-spanner of the directed hypergrid, providing a new technique for proving lower bounds for local monotonicity filters. Our connection is, in fact, more general: an efficient local monotonicity filter for functions on any partially ordered set (poset) implies a sparse 2-TC-spanner of the directed acyclic graph corresponding to the poset. We present nearly tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply stronger lower bounds for local monotonicity filters that nearly match the upper bounds of Saks and Seshadhri.

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction δ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^{Ω(δd)} on the length of linear 2-query LCCs over $\F_p$, that encode messages of length d. Our bound improves over the known bound of $2^{Ω(δd)} \cite{GKST06, KdW04, DS07} which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields \cite{SS10} and the second is a new analog of Beck's theorem over finite fields.

There has been a sequence of recent papers devoted to understanding the relation between the testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Invariance with respect to F2-linear transformations is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties. This is explicitly posed as an open problem in a recent survey of Sudan. We obtain the following results: 1. We show that every linear-invariant property that can be characterized by forbidding induced solutions to a (possibly infinite) set of linear equations can be tested with one-sided error. 2. We show that every linear-invariant property that can be tested with one-sided error can be characterized by forbidding induced solutions to a (possibly infinite) set of systems of linear equations. We conjecture that our result from item (1) can be extended to cover systems of linear equations. We further show that the validity of this conjecture would have the following implications: 1. It would imply that every linear-invariant property that is closed under restrictions to linear subspaces is testable with one-sided error. Such a result would unify several previous results on testing Boolean functions, such as the testability of low-degree polynomials and of Fourier dimensionality. 2. It would imply that a linear-invariant property P is testable with one-sided error if and only if P is closed under restrictions to linear subspaces, thus resolving Sudan's problem.

We consider the problem of testing if a given function f:F2n→ F2is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2d+1-query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2d)). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2-d)-far with Ω(1)probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1)st-Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F2nto F2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

Let be three Boolean functions. We say a triple (x, y, x + y) is a triangle in the function-triple (f1, f2, f3) if f1(x) = f2(y) = f3(x + y) = 1. (f1, f2, f3) is said to be triangle-free if there is no triangle in the triple. The distance between a function-triple and triangle-freeness is the minimum fraction of function values one needs to modify in order to make the function-triple triangle-free. A canonical tester for triangle-freeness repeatedly picks x and y uniformly and independently at random and checks if f1(x) = f2(y) = f3(x + y) = 1. Based on an algebraic regularity lemma, Green showed that the number of queries for the canonical testing algorithm is upper-bounded by a tower of 2's whose height is polynomial in 1/ε. A trivial query complexity lower bound of Ω(1/ε) is straightforward to show. In this paper, we give the first non-trivial query complexity lower bound for testing triangle-freeness in Boolean functions. We show that, for every small enough e there exists an integer n0(ε) such that for all n ≥ n0 there exists a function-triple depending on all the n variables which is ε-far from being triangle-free and requires queries for the canonical tester. For the single function case that f1 = f2 = f3, we obtain a weaker lower bound of . We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square-root of the query complexity of the corresponding canonical tester. Consequently, this yields and query complexity lower bounds for multi-function and single-function triangle-freeness respectively, with respect to general one-sided testers.

We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We study the approximability of the size of the sparsest k-TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family. Algorithms. We present two efficient deterministic algorithms that find k-TC-spanners of near optimal size. The first algorithm gives an -approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) Directed k-Spanner, a well-studied generalization of k-TC-Spanner, and (2) its variants Client/Server Directed k-Spanner, and the k-Diameter Spanning Subgraph. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k-TC-spanner problem, gives an -approximation. It shows that for , our problem has a provably better approximation ratio than Directed k-Spanner and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test due to Green for {}``triangle freeness'': A function $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies this property if $f(x),f(y),f(x+y)$ do not all equal $1$, for any pair $x,y\in\mathbb{F}_{2}^{n}$. Here we extend this test to a more systematic study of testing for linear-invariant non-linear properties. We consider properties that are described by a single forbidden pattern (and its linear transformations), i.e., a property is given by $k$ points $v_{1},\ldots,v_{k}\in\mathbb{F}_{2}^{k}$ and $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies the property that if for all linear maps $L:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{n}$ it is the case that $f(L(v_{1})),\ldots,f(L(v_{k}))$ do not all equal $1$. We show that this property is testable if the underlying matroid specified by $v_{1},\ldots,v_{k}$ is a graphic matroid. This extends Green's result to an infinite class of new properties. Our techniques extend those of Green and in particular we establish a link between the notion of {}``1-complexity linear systems'' of Green and Tao, and graphic matroids, to derive the results.