Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms. In this work, we establish the ... more >>>
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 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 ... more >>>
For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>
We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.
Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>
A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... 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 >>>
Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.
In this paper, we show that a ...
more >>>
Long Code testing is a fundamental problem in the area of property
testing and hardness of approximation.
Long Code is a function of the form $f(x)=x_i$ for some index $i$.
In the Long Code testing, the problem is, given oracle access to a
collection of Boolean functions, to decide whether ...
more >>>