Source author record

Arnab Bhattacharyya

Arnab Bhattacharyya appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

28works
19topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

28 published item(s)

preprint2023arXiv

An Adaptive Kernel Approach to Federated Learning of Heterogeneous Causal Effects

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.

preprint2023arXiv

Independence Testing for Bounded Degree Bayesian Network

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Θ(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.

preprint2022arXiv

Low Degree Testing over the Reals

We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the distance between functions is measured with respect to an unknown distribution $\mathcal{D}$ over $\mathbb{R}^n$ from which we can draw samples. In contrast to previous work, we do not assume that $\mathcal{D}$ has finite support. We design a tester that given query access to $f$, and sample access to $\mathcal{D}$, makes $(d/\varepsilon)^{O(1)}$ 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 $\varepsilon$ with respect to $\mathcal{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.

preprint2022arXiv

Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals

A {\em universal 1-bit compressive sensing (CS)} scheme consists of a measurement matrix $A$ such that all signals $x$ belonging to a particular class can be approximately recovered from $\textrm{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 {\em sparse} signals with bounded {\em dynamic range}. Specifically, a vector $x \in \mathbb{R}^n$ is 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 $A$ are i.i.d.~Gaussians, then under mild assumptions on the scaling of $k$ and $R$, the number of measurements needs to be $\tildeΩ(Rk^{3/2})$ to recover the support of $k$-sparse signals with dynamic range $R$ using $1$-bit CS. In addition, we show that a near-matching $O(R k^{3/2} \log n)$ upper bound follows as a simple corollary of known results. The $k^{3/2}$ scaling contrasts with the known lower bound of $\tildeΩ(k^2 \log n)$ for the number of measurements to recover the support of arbitrary $k$-sparse signals.

preprint2020arXiv

Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning

We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems: - Given sample access to two Bayesian networks $P_1$ and $P_2$ over known directed acyclic graphs $G_1$ and $G_2$ having $n$ nodes and bounded in-degree, approximate $d_{tv}(P_1,P_2)$ to within additive error $ε$ using $poly(n,ε)$ samples and time - Given sample access to two ferromagnetic Ising models $P_1$ and $P_2$ on $n$ variables with bounded width, approximate $d_{tv}(P_1, P_2)$ to within additive error $ε$ using $poly(n,ε)$ samples and time - Given sample access to two $n$-dimensional Gaussians $P_1$ and $P_2$, approximate $d_{tv}(P_1, P_2)$ to within additive error $ε$ using $poly(n,ε)$ 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 $d_{tv}(P_a, Q_a)$ to within additive error $ε$ using $poly(n,ε)$ samples, where $P_a$ and $Q_a$ are the interventional distributions obtained by the intervention $do(A=a)$ on $P$ and $Q$ respectively for a particular variable $A$. Our results are the first efficient distance approximation algorithms for these well-studied problems. They are derived using a simple and general connection to distribution learning algorithms. The distance approximation algorithms imply new efficient algorithms for {\em tolerant} testing of closeness of the above-mentioned structured high-dimensional distributions.

preprint2020arXiv

Efficient Statistics for Sparse Graphical Models from Truncated Samples

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 ${\bf x}$ are generated from a Gaussian $N(μ,Σ)$ and observed only if they belong to a subset $S \subseteq \mathbb{R}^d$. We show that $μ$ and $Σ$ can be estimated with error $ε$ in the Frobenius norm, using $\tilde{O}\left(\frac{\textrm{nz}(Σ^{-1})}{ε^2}\right)$ samples from a truncated $\mathcal{N}(μ,Σ)$ 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 $({\bf x},y)$ are generated where $y = {\bf x}^\top{Ω^*} + \mathcal{N}(0,1)$ and $({\bf x}, y)$ is seen only if $y$ belongs to a truncation set $S \subseteq \mathbb{R}$. We consider the case that $Ω^*$ 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 $Ω^*$. Specifically, we show that under some mild assumptions, only $O(k^2 \log d)$ samples are needed to estimate $Ω^*$ in the $\ell_\infty$-norm up to a bounded error. For both problems, our estimator minimizes the sum of the finite population negative log-likelihood function and an $\ell_1$-regularization term.

preprint2020arXiv

Learning and Sampling of Atomic Interventions from Observations

We study the problem of efficiently estimating the effect of an intervention on a single variable (atomic interventions) using observational samples in a causal Bayesian network. Our goal is to give algorithms that are efficient in both 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 P is a causal model on a set $\vec{V}$ of n observable variables with respect to a given causal graph G with observable distribution $P$. Let $P_x$ denote the interventional distribution over the observables with respect to an intervention of a designated variable X with x. Assuming that $G$ has bounded in-degree, bounded c-components ($k$), and that the observational distribution is identifiable and satisfies certain strong positivity condition, we give an algorithm that takes $m=\tilde{O}(nε^{-2})$ samples from $P$ and $O(mn)$ time, and outputs with high probability a description of a distribution $\hat{P}$ such that $d_{\mathrm{TV}}(P_x, \hat{P}) \leq ε$, and: 1. [Evaluation] the description can return in $O(n)$ time the probability $\hat{P}(\vec{v})$ for any assignment $\vec{v}$ to $\vec{V}$ 2. [Generation] the description can return an iid sample from $\hat{P}$ in $O(n)$ time. We also show lower bounds for the sample complexity showing that our sample complexity has an optimal dependence on the parameters $n$ and $ε$, as well as if $k=1$ on the strong positivity parameter.

preprint2016arXiv

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

We give the first optimal bounds for returning the $\ell_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, \dots, n\}$ and parameters $0 < ε< ϕ\leq 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 \geq ϕm$, returns no items $j$ for which $f_j \leq (ϕ-ε)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq ε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 $\ell_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.

preprint2016arXiv

Sample Complexity for Winner Prediction in Elections

Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election on a small sample of randomly chosen votes and output the winner as the prediction. We analyze the performance of this algorithm for many common voting rules. More formally, we introduce the $(ε, δ)$-winner determination problem, where given an election on $n$ voters and $m$ candidates in which the margin of victory is at least $εn$ votes, the goal is to determine the winner with probability at least $1-δ$. The margin of victory of an election is the smallest number of votes that need to be modified in order to change the election winner. We show interesting lower and upper bounds on the number of samples needed to solve the $(ε, δ)$-winner determination problem for many common voting rules, including scoring rules, approval, maximin, Copeland, Bucklin, plurality with runoff, and single transferable vote. Moreover, the lower and upper bounds match for many common voting rules in a wide range of practically appealing scenarios.

preprint2015arXiv

Fishing out Winners from Vote Streams

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined by popular voting rules. As we show, finding the exact winner requires storing essentially all the votes. So, we focus on the problem of finding an {\em $\eps$-winner}, a candidate who could win by a change of at most $\eps$ fraction of the votes. We show non-trivial upper and lower bounds on the space complexity of $\eps$-winner determination for several voting rules, including $k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland, and plurality with run off.

preprint2015arXiv

How friends and non-determinism affect opinion dynamics

The Hegselmann-Krause system (HK system for short) is one of the most popular models for the dynamics of opinion formation in multiagent systems. Agents are modeled as points in opinion space, and at every time step, each agent moves to the mass center of all the agents within unit distance. The rate of convergence of HK systems has been the subject of several recent works. In this work, we investigate two natural variations of the HK system and their effect on the dynamics. In the first variation, we only allow pairs of agents who are friends in an underlying social network to communicate with each other. In the second variation, agents may not move exactly to the mass center but somewhere close to it. The dynamics of both variants are qualitatively very different from that of the classical HK system. Nevertheless, we prove that both these systems converge in polynomial number of non-trivial steps, regardless of the social network in the first variant and noise patterns in the second variant.

preprint2015arXiv

Lower bounds for constant query affine-invariant LCCs and LTCs

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.

preprint2015arXiv

On the hardness of learning sparse parities

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.

preprint2015arXiv

Using higher-order Fourier analysis over general fields

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.

preprint2014arXiv

An explicit sparse recovery scheme in the L1-norm

Consider the approximate sparse recovery problem: given Ax, where A is a known m-by-n dimensional matrix and x is an unknown (approximately) sparse n-dimensional vector, recover an approximation to x. The goal is to design the matrix A such that m is small and recovery is efficient. Moreover, it is often desirable for A to have other nice properties, such as explicitness, sparsity, and discreteness. In this work, we show that we can use spectral expander graphs to explicitly design binary matrices A for which the column sparsity is optimal and for which there is an efficient recovery algorithm (l1-minimization). In order to recover x that is close to δn-sparse (where δ is a constant), we design an explicit binary matrix A that has m = O(sqrt{δ} log(1/δ) * n) rows and has O(log(1/δ)) ones in each column. Previous such constructions were based on unbalanced bipartite graphs with high vertex expansion, for which we currently do not have explicit constructions. In particular, ours is the first explicit non-trivial construction of a measurement matrix A such that Ax can be computed in O(n log(1/δ)) time.

preprint2013arXiv

A New Paradigm in Space Based Experiments Using Rubber Balloons

Indian Centre for Space Physics is engaged in long duration balloon borne experiments with typical payloads less than ~ 3kg. Low cost rubber balloons are used. In a double balloon system, the booster balloon lifts the orbiter balloon to its cruising altitude where data is taken for a long time. Here we present results of muon detections and recent solar activities, including the light curves and flare spectra in the 20-100keV range. We not only show that we have successfully obtained several flares and there spectra at different altitudes, we also found that the high energy X-ray flux of strong flares at altitudes of 10-13 km (the flight altitude of commercial planes) could be more than the contribution due to cosmic rays.

preprint2013arXiv

Algorithmic regularity for polynomials and applications

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials \calF = {P_1,...,P_m} to a new collection \calF' so that the polynomials in \calF' 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 \calF to \calF' is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection \calF'. In particular, when the field is of high characteristic, in polynomial time, we can refine \calF into \calF' where every nonzero linear combination of polynomials in \calF' has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -\eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -ηof P, for some ηdepending on \eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. 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 efficient (randomized) algorithm to find this collection.

preprint2013arXiv

Every locally characterized affine-invariant property is testable

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties.

preprint2012arXiv

On the Convergence of the Hegselmann-Krause System

We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d 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 n^{O(n)} resulting from a more general theorem of Chazelle. Also, we show a quadratic lower bound and improve the upper bound for one-dimensional systems to O(n^3).

preprint2012arXiv

Testing Low Complexity Affine-Invariant Properties

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 F_p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials except that low degree is preserved by composition with affine maps. The complexity of an affine-invariant property P refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize P. 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 P of functions f: F_p^n -> [R] is testable, assuming 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.

preprint2012arXiv

Testing Permanent Oracles -- Revisited

Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task. The oracle-testing problem is of interest because a recent paper of Aaronson and Arkhipov showed that if there is a polynomial-time algorithm for simulating boson-boson interactions in quantum mechanics, then an approximation oracle for the permanent (of the type described above) exists in BPP^NP. Since computing the permanent of even 0/1 matrices is #P-complete, this seems to demonstrate more computational power in quantum mechanics than Shor's factoring algorithm does. However, unlike factoring, which is in NP, it was unclear previously how to test the correctness of an approximation oracle for the permanent, and this is the contribution of the paper. The technical difficulty overcome here is that univariate polynomial self-correction, which underlies similar oracle-testing algorithms for permanent over finite fields --- and whose discovery led to a revolution in complexity theory --- does not seem to generalize to complex (or even, real) numbers. We believe that this tester will motivate further progress on understanding the permanent of Gaussian matrices.

preprint2011arXiv

Testing Odd-Cycle-Freeness in Boolean Functions

Call a function f : F_2^n -> {0,1} odd-cycle-free if there are no x_1, ..., x_k in F_2^n with k an odd integer such that f(x_1) = ... = f(x_k) = 1 and x_1 + ... + x_k = 0. We show that one can distinguish odd-cycle-free functions from those eps-far from being odd-cycle-free by making poly(1/eps) queries to an evaluation oracle. To obtain this result, we use connections between basic Fourier analysis and spectral graph theory to show that one can reduce testing odd-cycle-freeness of Boolean functions to testing bipartiteness of dense graphs. Our work forms part of a recent sequence of works that shows connections between testability of properties of Boolean functions and of graph properties. We also prove that there is a canonical tester for odd-cycle-freeness making poly(1/eps) queries, meaning that the testing algorithm operates by picking a random linear subspace of dimension O(log 1/eps) and then checking if the restriction of the function to the subspace is odd-cycle-free or not. The test is analyzed by studying the effect of random subspace restriction on the Fourier coefficients of a function. Our work implies that testing odd-cycle-freeness using a canonical tester instead of an arbitrary tester incurs no more than a polynomial blowup in the query complexity. The question of whether a canonical tester with polynomial blowup exists for all linear-invariant properties remains an open problem.

preprint2010arXiv

A Unified Framework for Testing Linear-Invariant Properties

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean functions on the hypercube. Hence, an important goal in Property Testing is to describe necessary and sufficient conditions for the testability of linear-invariant properties. This direction was explicitly proposed for investigation 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.

preprint2010arXiv

Optimal Testing of Reed-Muller Codes

We consider the problem of testing if a given function f : F_2^n -> F_2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. The Gowers norm is based on a natural 2^{d+1}-query test for this property. Alon et al. [AKKLR05] rediscovered this test and showed that it accepts every degree d polynomial with probability 1, while it rejects functions that are Omega(1)-far with probability Omega(1/(d 2^{d})). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Omega(2^{-d})-far with Omega(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 [BLR93] linearity test, for the setting of functions mapping F_2^n to F_2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [GT09,LMS08]. 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 [VW07]. 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 [GKNR09] for graph properties.

preprint2010arXiv

Separations of Matroid Freeness Properties

Properties of Boolean functions on the hypercube invariant with respect to linear transformations of the domain are among the most well-studied properties in the context of property testing. In this paper, we study the fundamental class of linear-invariant properties called matroid freeness properties. These properties have been conjectured to essentially coincide with all testable linear-invariant properties, and a recent sequence of works has established testability for increasingly larger subclasses. One question left open, however, is whether the infinitely many syntactically different properties recently shown testable in fact correspond to new, semantically distinct ones. This is a crucial issue since it has also been shown that there exist subclasses of these properties for which an infinite set of syntactically different representations collapse into one of a small, finite set of properties, all previously known to be testable. An important question is therefore to understand the semantics of matroid freeness properties, and in particular when two syntactically different properties are truly distinct. We shed light on this problem by developing a method for determining the relation between two matroid freeness properties P and Q. Furthermore, we show that there is a natural subclass of matroid freeness properties such that for any two properties P and Q from this subclass, a strong dichotomy must hold: either P is contained in Q or the two properties are "well separated." As an application of this method, we exhibit new, infinite hierarchies of testable matroid freeness properties such that at each level of the hierarchy, there are functions that are far from all functions lying in lower levels of the hierarchy. Our key technical tool is an apparently new notion of maps between linear matroids, called matroid homomorphisms, that might be of independent interest.

preprint2010arXiv

Steiner Transitive-Closure Spanners of d-Dimensional Posets

Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diameter at most k. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner). Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TCspanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d-dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with low Lipschitz constant. The proof of the lower bound constructs a dual solution to a linear programming relaxation of the Steiner 2-TC-spanner problem. We also show that one can efficiently construct a Steiner 2-TC-spanner, of size matching the lower bound, for any low-dimensional poset. Finally, we present a lower bound on the size of Steiner k-TC-spanners of d-dimensional posets that shows that the best-known construction, due to De Santis et al., cannot be improved significantly.