All reports by Author Eldar Fischer:

__
TR17-058
| 7th April 2017
__

Noga Alon, Omri Ben-Eliezer, Eldar Fischer#### Testing hereditary properties of ordered graphs and matrices

Revisions: 1

__
TR15-089
| 31st May 2015
__

Eldar Fischer, Oded Lachish, Yadu Vadusev#### Trading query complexity for sample-based testing and multi-testing scalability}

__
TR13-082
| 6th June 2013
__

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish#### Some properties are not even partially testable

__
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-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1

__
TR12-001
| 1st January 2012
__

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

__
TR10-067
| 14th April 2010
__

Sourav Chakraborty, Eldar Fischer, Arie Matsliah#### Query Complexity Lower Bounds for Reconstruction of Codes

__
TR10-027
| 28th February 2010
__

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

__
TR06-053
| 6th April 2006
__

Eldar Fischer, Orly Yahalom#### Testing Convexity Properties of Tree Colorings

__
TR04-105
| 19th November 2004
__

Eldar Fischer, Lance Fortnow#### Tolerant Versus Intolerant Testing for Boolean Properties

__
TR04-096
| 4th November 2004
__

Eldar Fischer, Frederic Magniez, Michel de Rougemont#### Property and Equivalence Testing on Strings

Revisions: 1

__
TR01-008
| 6th November 2000
__

Eldar Fischer#### On the strength of comparisons in property testing

__
TR00-083
| 18th September 2000
__

Eldar Fischer#### Testing graphs for colorability properties

Revisions: 1

__
TR98-066
| 3rd November 1998
__

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra#### PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.

We also explain how the proof can ...
more >>>

Eldar Fischer, Oded Lachish, Yadu Vadusev

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query ... more >>>

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... 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 >>>

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... 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 >>>

Sourav Chakraborty, Eldar Fischer, Arie Matsliah

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... 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 >>>

Eldar Fischer, Orly Yahalom

A coloring of a graph is {\it convex} if it

induces a partition of the vertices into connected subgraphs.

Besides being an interesting property from a theoretical point of

view, tests for convexity have applications in various areas

involving large graphs. Our results concern the important subcase

of testing for ...
more >>>

Eldar Fischer, Lance Fortnow

A property tester with high probability accepts inputs satisfying a given property and rejects

inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron

and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We

construct properties of binary functions ...
more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Eldar Fischer

An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it ...
more >>>

Eldar Fischer

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a

randomized algorithm which, given the ability to make queries whether

a desired pair of vertices of an input graph $G$ with $n$ vertices are

adjacent or not, distinguishes, with high probability, between the

case of $G$ satisfying ...
more >>>

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the ...
more >>>