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 ... more >>>

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{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, or in other words, whether ... more >>>

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

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 $\epsilon > 0$, it is NP-hard to decide: given a set of $\{-1,1\}$-labeled points in $\mathbb{R}^n$ whether (YES Case) ... more >>>

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 zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ... more >>>

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{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 ... more >>>

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 ... more >>>

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 ... more >>>

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.

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 ... more >>>

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>>

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{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 ... more >>>

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

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.

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, ... more >>>

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

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 $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

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 ... more >>>

Properties of Boolean functions on the hypercube that are invariant
with respect to linear transformations of the domain are among some of
the most well-studied properties in the context of property testing.
In this paper, we study a particular natural class of linear-invariant
properties, called matroid freeness properties. These properties ... more >>>

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

We consider the problem of testing if a given function
$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial
in $n$ variables, also known as the Reed-Muller testing problem.
Alon et al.~\cite{AKKLR} proposed and analyzed a natural
$2^{d+1}$-query test for this property and showed that it accepts
more >>>

Let $f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$ be three Boolean functions.
We say a triple $(x,y,x+y)$ is a \emph{triangle} in the function-triple $(f_{1}, f_{2}, f_{3})$ if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$.
$(f_{1}, f_{2}, f_{3})$ is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function-triple
and ... more >>>

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 were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

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 ... more >>>

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>