All reports by Author Arnab Bhattacharyya:

__
TR19-115
| 4th September 2019
__

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx#### Parameterized Intractability of Even Set and Shortest Vector Problem

__
TR19-079
| 28th May 2019
__

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka#### Average Bias and Polynomial Sources

Revisions: 2

__
TR18-057
| 26th March 2018
__

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi#### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

__
TR17-115
| 5th July 2017
__

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket#### Hardness of learning noisy halfspaces using polynomial thresholds

__
TR16-189
| 21st November 2016
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for 2-query LCCs over large alphabet

__
TR15-193
| 26th November 2015
__

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket#### On the hardness of learning sparse parities

__
TR15-185
| 24th November 2015
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for constant query affine-invariant LCCs and LTCs

__
TR15-135
| 19th August 2015
__

Arnab Bhattacharyya, Palash Dey#### Fishing out Winners from Vote Streams

Revisions: 1

__
TR15-077
| 4th May 2015
__

Arnab Bhattacharyya, Abhishek Bhowmick#### Using higher-order Fourier analysis over general fields

__
TR15-037
| 20th February 2015
__

Arnab Bhattacharyya, Palash Dey#### Sample Complexity for Winner Prediction in Elections

__
TR14-018
| 13th February 2014
__

Arnab Bhattacharyya#### Polynomial decompositions in polynomial time

__
TR13-166
| 28th November 2013
__

Arnab Bhattacharyya#### On testing affine-invariant properties

__
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

__
TR12-103
| 16th August 2012
__

Arnab Bhattacharyya, Yuichi Yoshida#### Testing Assignments of Boolean CSPs

__
TR12-094
| 19th July 2012
__

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva#### Testing Permanent Oracles -- Revisited

__
TR12-001
| 1st January 2012
__

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett#### Testing Low Complexity Affine-Invariant Properties

__
TR11-075
| 6th May 2011
__

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira#### Testing Odd-Cycle-Freeness in Boolean Functions

__
TR11-054
| 13th April 2011
__

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka#### Tight lower bounds for 2-query LCCs over finite fields

__
TR10-161
| 25th October 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira#### A Unified Framework for Testing Linear-Invariant Properties

__
TR10-136
| 26th August 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie#### Separations of Matroid Freeness Properties

Revisions: 1

__
TR10-116
| 21st July 2010
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing linear-invariant non-linear properties: A short report

__
TR10-027
| 28th February 2010
__

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant#### Testing monotonicity of distributions over general partial orders

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-066
| 13th August 2009
__

Arnab Bhattacharyya, Ning Xie#### Lower Bounds for Testing Triangle-freeness in Boolean Functions

__
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

__
TR08-088
| 13th September 2008
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

__
TR08-012
| 20th November 2007
__

Arnab Bhattacharyya#### A Note on the Distance to Monotonicity of Boolean Functions

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

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

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

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

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

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

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

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

Arnab Bhattacharyya, Sivakanth Gopi

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

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

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

Arnab Bhattacharyya, Sivakanth Gopi

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

Arnab Bhattacharyya, Palash Dey

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

Arnab Bhattacharyya, Abhishek Bhowmick

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 >>>Arnab Bhattacharyya, Palash Dey

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

Arnab Bhattacharyya

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

Arnab Bhattacharyya

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

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

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

Arnab Bhattacharyya, Yuichi Yoshida

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

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

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 >>>Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

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

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

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

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

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

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

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

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

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

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

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

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

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

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

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

Arnab Bhattacharyya, Ning Xie

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

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

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

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

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

Arnab Bhattacharyya

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