Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Arnab Bhattacharyya:

TR17-115 | 5th July 2017
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

Hardness of learning noisy halfspaces using polynomial thresholds

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

TR16-189 | 21st November 2016
Arnab Bhattacharyya, Sivakanth Gopi

Lower bounds for 2-query LCCs over large alphabet

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

TR15-193 | 26th November 2015
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

On the hardness of learning sparse parities

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

TR15-185 | 24th November 2015
Arnab Bhattacharyya, Sivakanth Gopi

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

TR15-135 | 19th August 2015
Arnab Bhattacharyya, Palash Dey

Fishing out Winners from Vote Streams

Revisions: 1

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

TR15-077 | 4th May 2015
Arnab Bhattacharyya, Abhishek Bhowmick

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.

... more >>>

TR15-037 | 20th February 2015
Arnab Bhattacharyya, Palash Dey

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

TR14-018 | 13th February 2014
Arnab Bhattacharyya

Polynomial decompositions in polynomial time

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

TR13-166 | 28th November 2013
Arnab Bhattacharyya

On testing affine-invariant properties

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

TR12-184 | 26th December 2012
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Every locally characterized affine-invariant property is testable.

Revisions: 1

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

TR12-103 | 16th August 2012
Arnab Bhattacharyya, Yuichi Yoshida

Testing Assignments of Boolean CSPs

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

TR12-094 | 19th July 2012
Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

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.

... more >>>

TR12-001 | 1st January 2012
Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

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

TR11-075 | 6th May 2011
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Testing Odd-Cycle-Freeness in Boolean Functions

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

TR11-054 | 13th April 2011
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

Tight lower bounds for 2-query LCCs over finite fields

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

TR10-161 | 25th October 2010
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

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

TR10-136 | 26th August 2010
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Separations of Matroid Freeness Properties

Revisions: 1

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

TR10-116 | 21st July 2010
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing linear-invariant non-linear properties: A short report

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

TR10-027 | 28th February 2010
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

Testing monotonicity of distributions over general partial orders

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

TR09-086 | 2nd October 2009
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

Optimal testing of Reed-Muller codes

Revisions: 1

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

TR09-066 | 13th August 2009
Arnab Bhattacharyya, Ning Xie

Lower Bounds for Testing Triangle-freeness in Boolean Functions

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

TR09-046 | 9th May 2009
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Transitive-Closure Spanners of the Hypercube and the Hypergrid

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

TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing Linear-Invariant Non-Linear Properties

Revisions: 1

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

TR08-012 | 20th November 2007
Arnab Bhattacharyya

A Note on the Distance to Monotonicity of Boolean Functions

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

ISSN 1433-8092 | Imprint