Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, William Gasarch, Evan Golub, ...
In the June issue Jacobo Torán will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the...
Hardness and Algorithms for Rainbow Connectivity (2009)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph $G$ is {em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {em rainbow connectivity} of a connected graph $G$, denoted...
Testing versus Estimation of Graph Properties Extended Abstract + Appendix (2008)
Abstract Some properties are testable but not tolerantly testable. We show here that testable graphproperties, however, also admit an algorithm that approximates the distance from the property up to...
On the Query Complexity of Testing for Eulerian Orientations (2008)
Eldar Fischer, Arie Matsliah, Ilan Newman, Orly Yahalom
We consider testing directed graphs for being Eulerian in the orientation model introduced in [15]. Despite the local nature of the property of being Eulerian, it turns out to be significantly harder...
Hardness and Algorithms for Rainbow Connection (2008)
Chakraborty, Sourav, Fischer, Eldar, Matsliah, Arie, Yuster, Raphael
An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph $G$, denoted...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
We show that any partition-problem of hypergraphs has an O(n) time approximate partitioning algorithm and an efficient property tester. This extends the results of Goldreich, Goldwasser and Ron who...
Abstract: A property tester with high probability accepts inputs satisfying a given prop-erty and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
Abstract We show that any partition-problem of hypergraphs has a sublinear O(n) time algorithm(where n is the number of vertices) with the following property: Given an input hypergraph H,which...
Testing graphs for colorability properties \Lambda (2008)
Abstract Let P be a property of graphs. An ffl-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...
Approximate Hypergraph Partitioning and Applications (2008)
Eldar Fischer, Arie Matsliah, Asaf Shapira
We show that any partition-problem of hypergraphs has an O(n) time approximate partitioning algorithm and an efficient property tester. This extends the results of Goldreich, Goldwasser and Ron who...
Linear Recurrence Relations for Graph Polynomials (2008)
Eldar Fischer, Johann A. Makowsky
on the occasion of his 85th birthday. Abstract. A sequence of graphs Gn is iteratively constructible if it can be built from an initial labeled graph by means of a repeated fixed succession of...
Testing convexity properties of tree colorings (2008)
A coloring of a graph is 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...
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-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...
Partite Graphs In, Eldar Fischer
It is proven that for every fixed h, a and b, a graph with n vertices and minimum degree at least h\Gamma1 h n, which contains no copy of K b (the complete graph with b vertices), contains at least...
Induced Complete H-Partite Graphs in Dense Clique-Less Graphs (2007)
It is proven that for every fixed h, a and b, a graph with n vertices and minimum degree at least h\Gamma1 h n, which contains no copy of K b (the complete graph with b vertices), contains at least...
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a distribution A over [n] [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is...
Eldar Fischer, Guy Kindler, Dana Ron, Alex Samorodnitsky
We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation...
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz
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...
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -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...
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
random variables for independence and identity
Tugkan Batu, Eldar Fischer, Lance Fortnow, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a distribution A over [n] [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is...
A Survey on Private Information Retrieval (2007)
Lance Fortnow, Eric Allender, Stephen Fenner, Eldar Fischer, Evan Golub, Clyde Kruskal, ...
In the June issue Jacobo Torn will take over as editor of this column and I look forward to many exciting columns under his direction. I would like to thank Grzegorz Rozenberg who served as BEATCS...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
Abstract. We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be...
Efficient testing of bipartite graphs for forbidden induced subgraphs ∗ (2007)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
Testing of matrix-poset properties* (2007)
Abstract Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally definedby Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems:...
Testing st-connectivity (2007)
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property of st-connectivity can be tested...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning testing dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Approximate Satisfiability and Equivalence (2006)
Eldar Fischer, Frédéric Magniez, Michel Rougemont
Inspired by Property Testing, we relax the classical satisfiability U | = F between a finite structure U of a class K and a formula F, to a notion of ε-satisfiability U |=ε F, and the classical...
Testing of matrix-poset properties* (2006)
Abstract Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally definedby Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems:...
Testing Graph Isomorphism (2006)
Abstract We deal with the question of how many queries arerequired to distinguish between the case that two graphs G and H on n vertices are isomorphic, and the case thatthey are s^-far, that is they...
Approximate Satisfiability and Equivalence (2006)
Eldar Fischer, Frédéric Magniez, Michel Rougemont
Inspired by Property Testing, for every ε> 0 we relax the classical satisfiability U | = F between a finite structure U of a class K and a formula F, to a notion of ε-satisfiability U |=ε F,...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Approximate Satisfiability and Equivalence (2006)
Eldar Fischer, Frédéric Magniez, Michel Rougemont
We relax the classical satisfiability U | = F between a finite structure U of a class K and a formula F, to a notion of ε-satisfiability U |=ε F, and the classical equivalence F1 ≡ F2 between two...
Testing Graph Isomorphism (2006)
Two graphs G and H on n vertices are ɛ-far from being isomorphic if at least ɛ � � n 2 edges must be added or removed from E(G) in order to make G and H isomorphic. In this paper we deal with...
Approximate satisfiability and equivalence (2006)
Eldar Fischer, Frédéric Magniez, Michel Rougemont
Inspired by Property Testing, for every ε> 0 we relax the classical satisfiability U | = F between a finite structure U of a class K and a formula F, to a notion of ε-satisfiability U |=ε F,...
Tolerant versus intolerant testing for boolean properties (2005)
Abstract: 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...
Testing of bipartite graph properties ∗ (2005)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
Testing versus estimation of graph properties (2005)
In the course of the proof we develop a framework for extending Szemer'edi's Regularity Lemma, both as a prerequisite for formulating what kind of information about the input graph will...
Tolerant versus intolerant testing for boolean properties (2005)
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...
Rougemont. Property and equivalence testing on strings (2004)
Eldar Fischer, Frédéric Magniez, Michel Rougemont
We investigate property testing and related questions, where instead of the usual Hamming and edit distances between input strings, we consider the more relaxed edit distance with moves. Using a...
Rougemont. Property and equivalence testing on strings (2004)
Eldar Fischer, Frédéric Magniez, Michel 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...
Rougemont. Property and equivalence testing on strings (2004)
Eldar Fischer, Frédéric Magniez
Michel de Rougemont £ We investigate property testing and related questions, where instead of the usual Hamming and edit distances between input strings, we consider the more relaxed edit distance...
Journal of Computer and System Sciences] (]]]])]]]–]]] (2003)
Eldar Fischer, Guy Kindler, B Dana Ron, Shmuel Safra, Alex Samorodnitsky D
Functions That Have Read-Twice Constant Width Branching Programs Are Not Necessarily Testable (2003)
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a, b ∈ C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi ∈ {ai, bi} for all 1...
Testing of matrix properties (2001)
Combinatorial property testing, initiated by Rubinfeld and Sudan [15] and formally dened by Goldreich, Goldwasser and Ron in [12], deals with the following relaxation of decision problems: Given a...
Testing of matrix properties (2001)
Combinatorial property testing deals with the following relaxation of decision problems: Given a xed property P and an input f, distinguish between the case that f satises P, and the case that no...
Testing of matrix properties (2001)
Combinatorial property testing, initiated by Rubinfeld and Sudan [15] and formally dened by Goldreich, Goldwasser and Ron in [12], deals with the following relaxation of decision problems: Given a...
On the strength of comparisons in property testing (2001)
An -test for a property P of functions from D = f1; : : : ; dg to the positive integers is a randomized algorithm, which makes queries on the value of an input function at specied locations, and...
Testing graphs for colorability properties (2001)
Let P be a property of graphs. An -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...
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a; b 2 C, let D(a; b) be the set of all descendants of a and b, that is, all words x of length 4 where x i 2 fa i; b i g for all 1...
The art of uninformed decisions: A primer to property testing (2001)
Property testing is a new field in computational theory, that deals with the information that can be deduced from the input where the number of allowable queries (reads from the input) is...
Testing of matrix properties (2001)
Both collections above are variants of properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations (and some...
Testing random variables for independence and identity (2001)
Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, Patrick White
Given access to independent samples of a ¤ distribution ¥¦ § ¨ ¥© § over, we show how to test whether the distributions formed by projecting ¤ to each coordinate are independent, i.e.,...
Alon and Yuster [4] have proven that if a fixed graph K on g vertices is (h + 1)-colorable, then any graph G with n vertices and minimum degree at least h n h+1n contains at least (1 − ɛ) g vertex...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a witness for the membership of a given input...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -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...
Variants of the Hajnal-Szemerédi Theorem (1999)
The Hajnal-Szemer'edi Theorem [6] states that a graph with hk vertices and minimum degree at least (h \Gamma 1)k contains k vertex disjoint copies of K h . Its proof is not algorithmic. Here, we...
Induced Complete H-Partite Graphs in Dense Clique-Less Graphs (1999)
It is proven that for every fixed h, a and b, a graph with n vertices and minimum degree at least h-1 h n, which contains no copy of K b (the complete graph with b vertices), contains at least (1 -...
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (1999)
Irit Dinur Eldar, Eldar Fischer, Guy Kindler, Ran Raz
this paper we show a PCP-characterization of NP of small (sub-constant) error probability. In addition, we impose additional structure on the local-readers, namely require the tests to be...
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ɛ-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...
2-factors in dense graphs (1996)
A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2 3n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven...
2-factors in Dense Graphs (1996)
A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2 3 n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven...
Refining the Graph Density Condition for the Existence of Almost K-factors
Alon and Yuster [4] have proven that if a fixed graph K on g vertices is (h + 1)-colorable, then any graph G with n vertices and minimum degree at least h h+1 n contains at least (1 \Gamma ffl) n g...
It is proven that a graph with n vertices and minimum degree at least h+2 2h n contains n h \Gamma O(h 2 ) vertex disjoint cycles of size h, and that a graph with n ? N (h) vertices and minimum...
Efficient Testing of Large Graphs
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-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...