**Update Notice:** Since a move to a new website might be mandated this year, updates are being suspended for the time being.

**File formats:** From 2010 I am using the PDF format
for newly posted papers. Older papers are usually in Postscript,
but I will convert any of them by request.

**Last updated:** 12.11.2013: decided to remove all the old "update news". Many changes from the previous 26.1.2012 version. Seven new conference papers (five of which can be downloaded here), updates about journal versions, and various tweaks.

**Versions provided:** I try to provide here online versions
for all papers which I expect people will be interested in downloading.
Usually, if a non-conference online version
is provided for a conference-only paper, then it is the future journal
version of the paper and may be newer. If the paper is already in a journal,
then the version there may contain last-minute corrections
not in the online version. Apart from some exceptions, the following
does not contain older versions of articles, such as online
conference versions of papers for which a full journal version
already exists (old files may remain without a link to them from this page,
but note that they are indeed old versions). If you would like
an electronic copy of a paper that is not available here, please email me.
I also in general do not put not-yet-accepted papers online (though
sometimes my coauthors do), but I am more accommodating through email.

**Copyrights:** Almost without exception, all publications are
the copyright of the journal and/or proceeding publishers in which they
appeared (and posting the versions here is within the generally
acceptable practice for published articles). One notable exception is
the open-content
Theory of Computing
journal that does not require a copyright transfer.

**[S99]**
I. Dinur,
E. Fischer,
G. Kindler,
R. Raz
and S. Safra,
**PCP characterizations of NP: Towards a polynomially-small
error-probability**,
*Proceedings of the
31st STOC* (1999), 29-40.

This is the preliminary version of the much revised [11b]. Indeed, this paper probably holds my personal record of time from conference version to journal version.

**[F99]**
N. Alon, E. Fischer,
M. Krivelevich and
M. Szegedy,
**Efficient testing of large graphs**,
*Proceedings of the
40th FOCS* (1999),
656-666.

This is the conference version of [00].

**[D01]**
E. Fischer,
**Testing graphs for colorability properties**,
*Proceedings of
the 12th SODA*
(2001), 873-882.

This is the conference version of [05a].

**[S01]**
E. Fischer and
I. Newman,
**Testing of matrix properties**,
*Proceedings of the
33rd STOC* (2001),
286-295.

We consider the testability of first order properties of binary matrices with a fixed dimension. We prove that properties defined using the product-order relation (between matrix locations) and no quantifier alternations are testable (and with a good dependency of the parameters involved), while there exist such a property with one quantifier alternation that is not testable. We also show the testability of such properties for matrices over fixed non-binary alphabets, and give testing algorithms for certain properties of binary graphs that are more efficient than those that were known before. The proof methods make use of certain Ramsey-like lemmas that are proven for the purpose, as well as a new restricted version of Szemerédi's Regularity Lemma that does not force a tower-like dependency on the parameters involved.

This paper is split into two journal paper, [07a] and [07c].

**[F01]**
T. Batu,
E. Fischer,
L. Fortnow,
R. Kumar,
R. Rubinfeld
and P. White,
**Testing random variables for independence
and identity**,
*Proceedings of the
42nd FOCS* (2001),
442-451.

This paper deals with statistical deductions - an algorithm has to
distinguish between the case that a given distribution over {1,...,n}
satisfies a certain property, and the case that no distribution that
is close (in the L_{1} norm) to the given one satisfies the
property. Unlike the case with combinatorial property testing, here
the algorithm is only allowed to obtain samples of values that were
independently chosen according to the distribution, and cannot make
any queries into it. One way to do it is using nlog(n) samples to
actually write down an L_{1} approximation of the
distribution, but for some properties one can do better. This paper
gives semi-tight bounds on the number of samples required for
comparing the given distribution against one that was written down in
advance, and for checking that a given joint distribution is close to
being independent.

Note: A new version of this paper that fixes some issues is in the works.

**[S02]**
E. Fischer,
E. Lehman,
I. Newman,
S. Raskhodnikova,
R. Rubinfeld
and A. Samorodnitsky,
**Monotonicity testing over general poset domains**,
*Proceedings of the
34th STOC* (2002),
474-483.

Testing of properties defined by notions of monotonicity was investigated in many works on the field, such as the O(log n) upper bound on testing that an integer sequence is monotone (later also a lower bound was provided in the paper "On the strength of comparisons in property testing", see above), and several works of testing monotonicity of functions defined over the hypercube. This paper provides further study into testing for monotonicity. In particular it shows the connection between monotonicity testing and testing of assignments to 2-CNF formulae, shows the existence of monotonicity-like properties for which non-adaptive testing is very hard, provides a non-trivial lower bound for testing for monotonicity over the Boolean hypercube, and proves several positive testing results over particular posets, such as tree-like ones.

**[C02]**
E. Fischer and
I. Newman,
**Functions that have read-twice constant width
branching programs are not necessarily testable**,
*Proceedings of the
17th CCC* (2002),
73-79.

This is a preliminary partial version of [04b] (now with J. Sgall as a coauthor).

**[F02]**
E. Fischer,
G. Kindler,
D. Ron,
S. Safra,
and A. Samorodnitsky,
**Testing juntas**,
*Proceedings of the
43rd FOCS* (2002),
103-112.

This is the preliminary version of [04c].

**[O03]**
E. Fischer and
J. A. Makowsky,
**The Specker-Blatter Theorem revisited**,
*Proceedings of the
9th COCOON*,
LNCS no. 2697 (2003), 90-101.

This paper further investigates the Specker-Blatter Theorem (see [03]). Several venues of possible generalizations are explored; for some of them the theorem can be generalized, while for others counterexamples exist. A future version of this paper (not yet available) will also include a simplified version of the proof of the original theorem.

I did not put an online version because we currently work on a journal version that is very much revised.

**[S04]**
E. Fischer,
**The difficulty of testing for isomorphism against
a graph that is given in advance**,
*Proceedings of the
36th STOC*
(2004), 391-397.

This is the preliminary version of [05b].

**[S05]**
E. Fischer and
I. Newman,
**Testing versus estimation of graph properties**,
*Proceedings of the
37th STOC* (2005),
138-146.

This is the preliminary version of [07b].

**[C05]**
E. Fischer and
L. Fortnow,
**Tolerant versus intolerant testing for Boolean properties**,
*Proceedings of the
21th CCC*
(2005), 135-140.

This is the preliminary version of [06].

**[D06]**
E. Fischer and
A. Matsliah,
**Testing graph isomorphism**,
*Proceedings of the
17th SODA*
(2006), 299-308.

This is the preliminary version of [08b].

**[S06]**
N. Alon, E. Fischer,
I. Newman and
A. Shapira
**A combinatorial characterization of the testable graph
properties: It's all about regularity**,
*Proceedings of the
38th STOC*
(2006), 251-260.

This is the preliminary version of [09].

**[L06]**
E. Fischer,
F. Magniez and
M. de Rougemont
**Approximate satisfiability and equivalence**,
*Proceedings of the
21st LICS*
(2006), 412-430.

This is the preliminary version of the extended [10a].

**[T07]**
E. Fischer and
Orly Yahalom
**Testing convexity properties of tree colorings**,
*Proceedings of the
24th
STACS*, LNCS no. 4393 (2007), 109-120.

This is the preliminary version of [11c].

**[R07a]**
S. Chakraborty, E. Fischer,
O. Lachish,
A. Matsliah
and I. Newman,
**Testing st-connectivity**,
*Proceedings of the
11th RANDOM*,
LNCS no. 4627 (2007), 380-394.

In recent years more and more research is directed at problems whose parameterization is as big as the input itself, usually given in form of a combinatorial structure. An old example is Ilan Newman's result about read-once branching program (where the problem parameters consists of a whole branching program for deciding the property). [T07] above can be counted as another such example. A major line of investigation of such problems has started with the works of S. Halevy, O. Lachish, I. Newman and D. Tzur about orientation properties. Here the parameter is an underlying undirected graph, and the property is stated in terms of a directed graph with the same edges. It is the edge directions that are considered as the input that needs to be queried. It seems rather hard to test even for simple graph properties in this setting, and in fact even the existence of a path from a special vertex s to t (st-connectivity) was not known to be testable. This article shows its testability with a constant number of queries, by using a sequence of combinatorial arguments and reductions ultimately leading to Newman's result about branching programs.

**[R07b]**
E. Fischer and E. Rozenberg,
**Lower bounds for testing forbidden induced
substructures in bipartite-graph-like combinatorial objects**,
*Proceedings of the
11th RANDOM*,
LNCS no. 4627 (2007), 464-478.

In [07c] a hope was raised that the polynomial testing result could be extended to matrices with more than two possible values, and perhaps also higher dimensional tensors (this question appeared in some form already in [S01]). This article shows that this is not the case. In fact, testing multi-valued matrices may be as hard as the general (and long-time frustrating) problem of testing for subgraph-freeness.

**[F07]**
E. Fischer, A. Matsliah
and A. Shapira,
**Approximate hypergraph partitioning and applications**,
*Proceedings of the
48th FOCS* (2007), 579-589.

This is the preliminary version of [10b].

**[R08]**
E. Fischer, O. Lachish,
A. Matsliah,
I. Newman and
Orly Yahalom
**On the query complexity of testing orientations
for being Eulerian**,
*Proceedings of the
12th RANDOM*,
LNCS no. 5171 (2008), 402-415.

This is the preliminary version of [12].

**[T09]**
S. Chakraborty, E. Fischer,
A. Matsliah
and R. Yuster,
**Hardness and algorithms for rainbow connectivity**, *Proceedings of the
26th STACS*
(2009), 243-254.

This is the preliminary version of [11a].

**[T10]**
S. Chakraborty, E. Fischer,
O. Lachish
and R. Yuster,
**Two-phase algorithms for the parametric
shortest path problem**,
*Proceedings of the
27th
STACS* (2010), 167-178.

Suppose that we would like to solve the shortest path problem (or a variant thereof) on a weighted graph. This problem has tried and true algorithms. But what if the weights are given as functions of a variable whose value is yet unknown? This paper shows for some classes of functions (such as linear ones), how we can use preprocessing to make sure that once the value of the variable is given, the remaining work needed to provide the shortest path solution is very small.

**[FS10]**
S. Chakraborty, E. Fischer,
A. Matsliah
and R. de Wolf,
**New Results on Quantum Property Testing**,
*Proceedings of the
30th
FSTTCS*, LIPIcs vol. 8 (2010), 145-156.

Quantum computational theory is an expanding field in computer science that deals with alternate computational models that are feasible under the physical framework of quantum theory, and mainly the underlying notion of quantum probability. Questions about property testing can be naturally formulated for the quantum scheme, and have been investigated in several papers. This paper provides new upper and lower bounds for some commonly investigated properties.

**[I11a]**
A. Bhattacharyya, E. Fischer,
A. Matsliah,
R. Rubinfeld
and P. A. Valiant,
**Testing monotonicity of distributions over
general partial orders**,
*Proceedings of the
2nd ICS
(now ITCS)* (2011), 239-252.

This deals again with statistical testing of distributions, a topic
that is by now well researched
in connection with property testing. In this paper monotonicity is considered,
in a setting resembling the massively parametrized model. A partially ordered
domain is given in advance, and a distribution from which only independent samples
are available is tested. The algorithm needs to distinguish distributions that
are monotone over the domain from those that are far in the l_{1} distance
from being monotone. Upper and lower bounds are given for some cases, including some
very general ones, and also a strong lower bound is given for the special case
of the partial order being a matching.

**[I11b]**
S. Chakraborty, E. Fischer
and A. Matsliah,
**Query complexity lower bounds for
reconstruction of codes**,
*Proceedings of the
2nd ICS
(now ITCS)* (2011), 264-274.

This paper deals with a new model where a redundant encoding with some errors has to be decoded (recovering from the errors). Here, not only each bit has to be locally decoded, but for the decoding to be deemed successful all bits must be recovered correctly at once. It is shown for some cases that a good success probability cannot be achieved for query complexities much better than what can be done by applying a simple amplification technique to a traditional locally decodable code.

**[DT11]**
S. Ben Moshe, E. Fischer,
M. Fischer,
Y. Kanza,
A. Matsliah
and C. Staelin,
**Detecting and exploiting near-sortedness for
efficient relational query evaluation**,
*Proceedings of the
14th ICDT* (2011), 256-267.

This paper proposes a realistic application of the property testing method. A naturally appearing property of database files called "near sortedness" (with two parameters) is defined and investigated. The paper provides an efficient test for this property (approximating the two parameters) as well as a method for speeding up database operations such as natural join when the property is known to hold.

**[R11]**
E. Fischer and E. Rozenberg,
**Inflatable graph properties and natural property
tests**,
*Proceedings of the
15th RANDOM*,
LNCS no. 6845 (2011), 542-554.

For some dense graph properties, mainly hereditary ones, one would think that any test (even one that depends on the graph order and has 2-sided error) would have no more than a polynomial advantage over the "natural" test that just samples a random induced subgraph and checks it for the property. However, this is not known, and the known best lower bound for general testers for triangle-freeness (one of the most investigated properties) is provided by an ad-hoc proof. The main result here is that for properties that are both hereditary and inflatable (a condition that could be thought of as being "upward-hereditary") indeed the gap is bounded by a polynomial. Triangle-freeness is such a property.

**[C12]**
S. Chakraborty, E. Fischer, D. García-Soriano and A. Matsliah,
**Junto-symmetric functions, hypergraph isomorphism, and crunching**,
*Proceedings of the
27th IEEE CCC* (2012), 148-158.

This paper provides an upper bound, independent of the input length, for testing a Boolean function of n variables for isomorphism (that is, identity up to a permutation of the variables) with one that depends only on the number of 1's together with the values of a constant number of specific variables. An appealing conjecture is that these are essentially the only Boolean functions for which isomorphism can be tested. The paper also provides lower bounds for some isomorphism testing problems (such as graph isomorphism) using the new method of "crunching", introduced there.

**[W12]**
E. Fischer, Y. Goldhirsh and O. Lachish,
**Testing formula satisfaction**,
*Proceedings of the
13th SWAT* (2012), LNCS no. 7357, 376-387.

A read-once formula can be thought of as a tree, where the leaves each holds a distinct variable identifier, while the internal nodes are labeled with operators over the set of possible values (e.g. {0,1} for Boolean formulas). This is given in advance, and the tested property is that an assignment to the variables will result at a given value at the root node, when evaluated from the bottom up. This paper starts the investigation of such properties with some upper and lower bounds. In particular, all Boolean formulas (over {0,1}) with general bounded fan-in gates admit a test whose number of queries is independent of the formula size, and for And/Or formulas the bound is quasi-polynomial in the approximation paremeter. On the other hand, there are formulas over {0,1,2,3}, with only one type of binary operator at the internal nodes (all of which being of degree 2), that do not admit a test with a number of queries independent of the tree size.

**[PP12]**
Y. Ben Asher, E. Fischer, G. Haber and V. Tartakovski,
**Fast evaluation of Boolean circuits based on two-players game and optical connectivity circuits**,
*Proceedings of the 41st ICPP* (2012), 21-29.

This paper deals with a way that the evaluation of some (but unfortunately not all) Boolean circuits can be parallelized.

**[D13]**
A. Bhattacharyya, E. Fischer and S. Lovett,
**Testing low complexity affine-invariant properties**,
*Proceedings of the 24th ACM-SIAM SODA* (2013), 1337-1355.

Dense graphs have Szemerédi's regularity lemma, and for Boolean functions over the linear space {0,1}^{n} there are decompositions of the space by low degree polynomials that relate to the Gowers norm. Here the technique is taken a step further to show that many properties characterized by forbidden affine "configurations" admit a test whose number of queries depends only on ε. The dependency itself is even worse than the one found in [00] for dense graphs, but here it is the theory that counts.

**[I13]**
S. Chakraborty, E. Fischer, Y. Goldhirsh and A. Matsliah,
**On the power of conditional samples in distribution Testing**,
*Proceedings of the 4th ITCS* (2013), 561-180.

Here a new model for distribution testing is introduced. Apart from the usual ability to take independent samples according to the distribution, the tester is also allowed to request samples drawn from a subset of the base set, according to the corresponding conditional distribution. This allows the tester to have "algorithmic" features, which are usually uncommon in distribution testing, and allows for meaningful answers using much fewer samples than in the traditional model (in some cases even a constant number of samples is sufficient). On the other hand, there are still properties which (provably) resist testing also in this model. A very similar model was introduced independently by Cannone, Ron and Servedio [ECCC TR12-155], where they proved other results for it.

**[D13]**
A. Bhattacharyya, E. Fischer, H. Hatami, P. Hatami and S. Lovett,
**Every locally characterized affine-invariant property is testable**,
*Proceedings of the 45th ACM STOC* (2013), 429-436.

The sequel to [D13]. Here variants of the techniques that use so-called non-classical polynomials are applied to show that every property characterized by a finite number of forbidden affine configurations admits a test whose number of queries does not depend on n.

**[I13]**
E. Fischer, Y. Goldhirsh and O. Lachish,
**Partial tests, universal tests and decomposability**,
*Proceedings of the 5th ITCS* (2014), to appear.

Can the non-testability of a property be "softened" if we allow a prover to provide in advance a sublinear size proof? Not always, as here we prove that some properties do not only completely resist a property test, but are such that any sub-property whose size is not much smaller than the original is still hard to test (the size reduction factor is exponential in the query complexity reduction factor). A proof scenario is essentially a decomposition of the property into relatively few highly testable ones, and hence it cannot occur here.

The proof uses several new techniques. One is related to the way Shannon entropy is used to bound the size of the sub-property. Another technique is a way to provide bounds against property tests that relate to the structure of the tester itself, rather than the customary reliance on Yao's method. This allows for lower bounds in situations where the old techniques are inapplicable.

There is also a result in the other direction: Any property that is decomposable into not a lot of very highly testable properties (properties with proximity-oblivious constant query complexity 1-sided error tests) will admit some sublinear query complexity test. This is because tests as above can be converted into (much less efficient) "universal" tests with sublinear query complexity, whose querying scheme does not depend at all on the original.

**[96]**
N. Alon and E. Fischer,
**2-factors in dense graphs**,
*
Discrete Mathematics* 152 (1996), 13-23.

The conjecture of Sauer and Spencer, stating that a graph with n vertices and minimum degree at least 2n/3 contains as a subgraph any possible graph with n vertices and maximum degree 2, is proven for here every n that is larger than some global constant. Preliminary results regarding the minimum degree required for a graph to contain subgraphs with maximum degree 2 but without small cycles are also outlined (these have been later superseded in some of the papers below and other papers). Some of the methods used here are also used in some of the papers in this list.

As it later turned out,
the full conjecture was proven using other methods in:
M. Aigner and S. Brandt,
**Embedding arbitrary graphs of maximum degree two**,
*J. of the London Math. Soc.* 48 (1993), 39-51.

**[99a]**
N. Alon and E. Fischer,
**Refining the Graph Density Condition for the
Existence of Almost K-factors**,
*
Ars Combinatoria* 52 (1999), 296-308.

Results regarding the minimum degree required for a graph with n vertices
to contain (1-o(1))n/k vertex disjoint copies of a fixed complete h-partite
graph with k vertices are proven, and a conjecture is formulated. These
generalize the results proven by N. Alon and R. Yuster in their paper
**Almost H-factors in dense graphs**
(*Graphs and Combinatorics*, 8 (1992), 95-102).

The full conjecture was proven in:
János Komlós, **Tiling Turán theorems**,
*Combinatorica* 20 (2000), 203-218.

**[99b]**
E. Fischer,
**Variants of the Hajnal-Szemerédi Theorem**,
*J. of Graph Theory*
31 (1999), 275-282.

A classical theorem of Hajnal and Szemerédi states that a graph
with hk vertices and minimum degree at least (h-1)k contains k vertex
disjoint copies of the complete graph with h vertices. Its proof, however,
does not yield an efficient algorithm for finding them. By using
an incremental approach, an algorithm for finding k-(h-1)^{2} such
copies in time O((h+5)!k^{2}) is presented. A conjecture that can be
considered a variant of the aforementioned theorem is also suggested along
With some evidence to its validity, as well as a conjecture regarding cycles
in graphs, that is somewhat related to the El-Zahar Conjecture.

**[99c]**
E. Fischer,
**Cycle factors in dense graphs**,
*
Discrete Mathematics* 197/198 (1999), 309-323.

A conjecture of El-Zahar states that if n_{1},...,n_{l}
are integers whose sum is n, with k of them being odd, and G is a graph with
n vertices and minimum degree (n+k)/2, then G contains vertex disjoint
cycles of sizes n_{1},...,n_{l} respectively. Results
regarding the upper bounds on the minimum degree of G that ensures it
contains the required cycles are presented for some special cases
(mostly cases where n_{1},...,n_{l} are bounded and n is
large). These are proven using the Regularity Lemma of Szemerédi,
combined with a result proven by an incremental approach, and
additional arguments.

Later, strong results regarding the El-Zahar Conjecture were proven by Sarmad Abbasi.

**[99d]**
E. Fischer,
**
Induced complete h-partite graphs in dense clique-less graphs**,
*
The Electronic Journal of Combinatorics* 6 (1999), R43.

This short paper shows, for every fixed h, a and b, that a graph with n vertices and minimum degree at least (h-1)n/h, which does not contain a copy of the complete graph with b vertices, contains (1-o(1))n/ah vertex disjoint induced copies of the complete h-partite graph with a vertices in each color class. The proof of this result, from the aforementioned result of Alon and Yuster dealing with not necessarily induced graphs, is quite simple, but the formulation of the result itself and its connection to other results in this area may be of interest.

**[00]**
N. Alon, E. Fischer,
M. Krivelevich and
M. Szegedy,
**Efficient testing of large graphs**,
*
Combinatorica* 20 (2000), 451-476
(a preliminary version appeared as [F99]).

We call a graph property testable if for every 0<ε<1
there exists
a randomized algorithm that makes a constant number of queries on the
input graph G (a query consisting of a check whether a vertex pair
is an edge or not), and distinguishes with high probability between the case
of the case that G satisfies the property and the case that no graph
differing from G in less than εn^{2} places satisfies it. This
notion of testability, that has applications to approximation and machine
learning, was first formulated for various combinatorial structures by
Rubinfeld and Sudan, and in the context of graphs it was first investigated
by Goldreich, Goldwasser and Ron. It is quite different from the
traditional complexity notions. In this paper the notion of testability
is investigated from the point of view of logic. it is proven that all first
order graph properties of type "∃∀"
are testable, while there exists a first order property of
type "∀∃" that is not testable.

**[01a]**
N. Alon,
E. Fischer and
M. Szegedy,
**Parent-identifying codes**,
*Journal of Combinatorial
Theory Series A* 95 (2001), 349-359.

In a paper of Hollmann, Van Lint, Linnartz and Tolhuizen a new type of codes is introduced, with the property that for every word created by selecting two words from the code, and then arbitrarily taking each character from its corresponding place in any of the words, at least one of of the selected code words can be identified. In this paper the question from the aforementioned article as to the maximum possible size of such a code for words of length 4 over an alphabet of size n is answered. The proofs combine graph theoretic tools with techniques from additive number theory.

**[01b]**
E. Fischer,
**The art of uninformed decisions:
A primer to property testing**,
The Computational Complexity Column of
*
The Bulletin of
the European Association for Theoretical Computer Science* 75 (2001),
97-126.
Also in: *Current Trends in Theoretical Computer Science:
The Challenge of the New Century* (G. Paun, G. Rozenberg
and A. Salomaa eds.), World Scientific Publishing (2004), Vol. I 229-264.

Despite its relatively young age, property testing has progressed enough to merit several surveys. This one gives an introduction to the field, and presents several of its state of art methods with examples.

The version appearing here is the updated one, which appears in the "Current Trends in Theoretical Computer Science" volume that is based on the BEATCS.

**[03]**
E. Fischer,
**The Specker-Blatter theorem
does not hold for quaternary relations**,
*Journal of Combinatorial
Theory Series A* 103 (2003), 121-136.

A remarkable theorem by Specker and Blatter states that for all monadic second order logic expressions over a language containing unary and binary relations only, the number of models over a finite universe, as a function of the order of the universe is ultimately periodic modulo m for every fixed integer m. As an example, if follows that the number of, say, the connected 3-regular graphs with n vertices, satisfies this property. Specker and Blatter conjectured that their theorem holds true also for monadic second order expression over higher arity relations (and thus in particular similar statements about hypergraph counting hold). In this paper a counter example involving a relation of arity 4 is constructed, leaving only the arity 3 case still open.

**[04a]**
E. Fischer,
**
On the strength of comparisons in property testing**,
*
Information and Computation* 189 (2004), 107-116.

We consider the minimum number of queries required for a randomized algorithm to distinguish between the case of a sequence of n integers satisfying a certain property, and the case that it has to be modified in more than εn places to make it satisfy the property. It is proven here that for properties defined in terms of weak inequalities between the input integers, such an algorithm cannot perform better then the best algorithm that relies only on comparisons between the queried values (by comparison, similar statements are not always true for other computational models, e.g. for the running time of sorting algorithms). In particular, this implies a tight lower bound of O(log n) queries on the number queries required to test whether the sequence is monotone nondecreasing (or εn-far from it).

**[04b]**
E. Fischer,
I. Newman
and J. Sgall,
**Functions that have read-twice constant width
branching programs are not necessarily testable**,
*
Random Structures and Algorithms* 24 (2004), 175-193
(a previous partial version by the first two authors appeared as [C02]).

Newman proved in 2000 that all languages that can be recognized by a read-once constant width oblivious branching program are testable. He then posed the natural question as to whether this result can be extended to branching programs that can read each variable up to a constant number of times (instead of just once). The paper answers this question in the negative. The proofs use a notion resembling graph expansions, and a good deal of elementary linear algebra.

**[04c]**
E. Fischer,
G. Kindler,
D. Ron,
S. Safra,
and A. Samorodnitsky,
**Testing juntas**,
*Journal of Computer and System Sciences*
68 (2004, 43rd FOCS special issue), 753-787
(naturally, an older version has appeared as [F02]).

Given a Boolean function with n variables, can one test for the property of it being dependent on only k of them? This paper provides such a test with a polynomial dependence in k and an inverse linear one in the approximation parameter. There are also related results, such as a lower bound with an interesting implication concerning random walks on groups, and results about testing for the property of being identical to a given function h up to a permutation of its variables.

The older version is also put here because of an interesting comparison between the proof methods of the two versions: In the old version, the proof of the main result was done through use of Fourier analysis. In the new version, this machinery was replaced with a different one (centered around the variance of certain random variables) that makes it more general. In some sense the new proof still shows its "Fourier-analytic" origins; perhaps the newer method can be also adapted to other similar proofs.

**[04d]**
E. Fischer and
J. A. Makowsky,
**On spectra of sentences of monadic second
order logic with counting**,
*Journal
of Symbolic Logic* 69 (2004), 617-640.

For a property of graphs given by a Monadic Second Order Logic expression, what can be said about the sizes of all graphs satisfying it? Questions of this type can be rather hard. Here it is proven that if there is a fixed limit on the clique-width of the graphs (or other relational structures) satisfying the given property, then the set of numbers for which there exist a satisfying graph with this many vertices is ultimately periodic. An extension to many-sorted logic is also presented.

**[05a]**
E. Fischer,
**
Testing graphs for colorability properties**,
*
Random Structures and Algorithms* 26 (2005), 289-309
(a preliminary version appeared as [D01]).

The positive part of [00] is proven by showing the testability of a certain generalized notion of graph colorability. In this paper the testability of two generalizations of this notion of colorability is proven. In the [D01] version it was also explained how to generalize the results of [00] (positive and negative) to other related combinatorial structures, such as tournaments.

**[05b]**
E. Fischer,
**The difficulty of testing for isomorphism against
a graph that is given in advance**,
*
SIAM Journal on Computing* 34 (2005), 1147-1158
(a preliminary version appeared as [S04]).

Classifying the set of all efficiently testable graph properties is hard, but what about just deciding whether the input graph is isomorphic to a known graph that is given in advance? This paper provides a sort of an answer: A graph that is close to being "simple" has a respective upper bound on the number of queries required for this test, while for a graph that is far from all "simple" graphs a lower bound exists. The gap between the upper bound and the lower bounds (as functions of the parameter of the appropriate notion of simplicity) is large, however, on account of the use of the Regularity Lemma of Szemerédi. Interestingly, this time it is used for proving the lower bound.

In case you are wondering what has happened to the notation in the "mathfrak" font in this version, a referee has suggested that I replace it with a more conventional one.

**[06]**
E. Fischer and
L. Fortnow,
**Tolerant versus intolerant testing for
Boolean properties**,
*Theory of Computing*
2 (2006), Article 9, 173-183 (a preliminary version appeared as [C05]).

A tolerant (ε,δ)-test for a property is an ε-test that in addition is guaranteed to accept (with probability at least 2/3) any input that is δ-close to satisfying the property. Parnas, Ron and Rubinfeld (ECCC TR04-010) have defined the notion of tolerant property testing; a property is called tolerantly testable if for every ε there exists an (ε,δ)-test for a constant δ that makes a constant number of queries. Their definition motivated this paper, as well as [S05] above.

It is not hard to show that the number of queries required for tolerant testing may be larger than the number of queries required for testing (in the old sense), and that there exist properties over infinite alphabets that are testable but not tolerantly testable. The question of constructing such properties over the Boolean alphabet however is harder, and is resolved in this paper by going back to the roots of the field of property testing, and mainly exploring its connection to that of Probabilistically Checkable Proofs.

**[07a]**
E. Fischer and
I. Newman,
**Testing of matrix-poset properties**,
*
Combinatorica* 27 (2007), 293-327.

This is the journal version of the first part of [S01]. It proves that properties defined using the product-order relation (between matrix locations) and no quantifier alternations are testable (and with a good dependency of the parameters involved), while there exist a property with one quantifier alternation that is not testable.

**[07b]**
E. Fischer and
I. Newman,
**Testing versus estimation of graph properties**,
*
SIAM Journal on Computing*37 (2007), 482-501
(a preliminary version appeared as [S05]).

From [05b] one could garner hopes for finding a combinatorial
characterization for the hardness of testing whole graph properties,
not just single graphs. As it turns out, there is a correlation
between testability and having an approximation in terms of regular
partitions, but the more interesting feature is what this implies:
If a graph property has a test with a constant number of queries
for every ε, then it is also possible for every
0<ε_{1}<ε_{2}<1
to distinguish between graphs that are
ε_{1}-close to satisfying the property, and graphs
that are ε_{2}-far from satisfying it.

**[07c]**
N. Alon, E. Fischer and
I. Newman,
**Efficient testing of bipartite graphs
for forbidden induced subgraphs**,
*
SIAM Journal on Computing* 37 (2007), 959-976.

This is a very extended and enhanced version of the second part of [S01]. It shows that properties of bipartite graphs (or binary matrices) characterized by a finite family of forbidden subgraphs (or correspondingly a permutation invariant finite family of forbidden submatrices) is not only testable with a constant number of queries, but that this number is in fact a polynomial in the approximation parameter ε, rather than the double or triple exponent known from [S01] or the tower function that was known from previous results.

**[08a]**
E. Fischer,
J. A. Makowsky
and E. V. Ravve,
**Counting truth assignments of formulas of bounded
tree-width or clique-width**,
*
Discrete Applied Mathematics 156 (2008)* (P. Hammer 60th birthday special issue),
511-529.

Knowing the number of satisfying assignments for a given SAT formula is #P-hard, but what if the underlying combinatorial structure of this formula has a bounded tree-width or a bounded clique-width? In this case and if you already have the corresponding tree-decomposition or clique-decomposition (note also that for a fixed k, a k-tree-decomposition can be found in polynomial time if one exists), this problem is solvable in time that is polynomial in the input size with coefficients that depend (badly) on the corresponding bound on the width, by a paper by Courcelle, Makowsky and Rotics from 2001. This paper gives another algorithm that is based on the particular combinatorial properties of SAT formulas, with a better ("only" exponential) dependency on the width parameter k.

**[08b]**
E. Fischer and
A. Matsliah,
**Testing graph isomorphism**,
*
SIAM Journal on Computing* 38 (2008), 207-225
(a preliminary version appeared as [D06]).

Testing for graph isomorphism is already known not to be possible with a constant number of queries from [00], but how many queries are indeed required? Apart from the setting of two graphs that need to be queried, there is the setting of [05b]: Given that one of the graphs is already known in full, how hard in the worst case is it to test an input graph for isomorphism with it? This paper investigated the upper and lower bounds for 1-sided and 2-sided error algorithms in both settin. This problem is one of the few natural problems that do not explicitly involve counting and yet for which 1-sided and 2-sided testing differs.

**[08c]**
E. Fischer and
J. A. Makowsky,
**Linear recurrence relations for graph polynomials**,
*Pillars of Computer Science: Essays Dedicated to Boris (Boaz)
Trakhtenbrot on the Occasion of His 85th Birthday* (A. Avron,
N. Dershowitz and A. Rabinovich eds.), LNCS no. 4800 (2008), 266-279.

Suppose that you build a sequence of graphs G_{1},
G_{2}, G_{3}... by applying the same elementary operations
over and over again. What would this mean for the invariants of the graphs?
Here it is shown that for a wide class of graph polynomials, a linear
recurrence relation for calculating them will exist.

**[09]**
N. Alon, E. Fischer,
I. Newman and
A. Shapira
**A combinatorial characterization of the testable graph
properties: It's all about regularity**,
*
SIAM Journal on Computing* 39 (2009, 38th STOC special issue), 143-167
(naturally an older version appeared as [S06]).

The question of characterizing the testable graph properties has been a long standing one. With the culmination of results improving the understanding of Szemerédi's Regularity Lemma and its use in property testing of graphs, it is not surprising that this lemma takes center stage in a characterization result. This paper essentially takes a final natural step, proving that a property is testable (in the dense graph model) if and only if it is approximable by the property of the graph having a regular partition with a specified range of densities.

**[10a]**
E. Fischer,
F. Magniez and
M. de Rougemont
**Approximate satisfiability and equivalence**,
*
SIAM Journal on Computing* 39 (2010), 2251-2281
(a preliminary version appeared as [L06]).

In property testing a given input is approximately measured against a given language. What if one wants to compare two whole languages instead? This paper define an approximate notion of language equivalence that is inspired by the property testing approximation. That is, two languages are considered to be approximately equivalent if almost all the words in any of these languages are ε-close to being in the other language. The exact version of the equivalence problem is in many cases in a high complexity class, or even not recursively computable. Here, under a sufficiently weak norm (the edit distance with moves), several instances of the equivalence testing problems have far more efficient algorithms for a fixed approximation parameter ε. An extension to languages of trees is also discussed.

**[10b]**
E. Fischer, A. Matsliah
and A. Shapira,
**Approximate hypergraph partitioning and applications**,
*
SIAM Journal on Computing* 39 (2010), 3155-3185
(a preliminary version appeared as [F07]).

One of the best known milestones in the theory of property testing is the result of Goldreich, Goldwasser and Ron that allows us to test (over the dense model) any property of a graph that is defined as having a partition with prescribed densities. A sublinear time (linear in the output size) algorithm for actually constructing an approximate partition was also given there.

Can a similar result be proven for hypergraphs? This paper provides a positrive answer. Moreover, the inherent complexity in hypergraphs can now work for us, leading to new and unforseen applications of this extension. The main application is a new algorithms for finding regular partitions (in Szemerédi's sense) of graphs. Unlike previous algorithms concerning Szemerédi's Regularity Lemma, here the algorithm can guarantee to find a small regular partition if one exists, rather than just finding some regular partition whose size is bounded only by what the Regularity Lemma provides.

**[11a]**
S. Chakraborty, E. Fischer,
A. Matsliah
and R. Yuster,
**Hardness and algorithms for rainbow
connectivity**,
*Journal
of Combinatorial Optimization* 21 (2011), 330-347
(a preliminary version appeared as [T09]).

A rainbow coloring of a (connected) graph is an edge coloring in which every two vertices are connected by a path with no repeated colors. Some hardness results are proven for this problem, as well as some upper bounds on the required number of colors in some special cases, such as the case where the graph has a linear minimum degree.

**[11b]**
I. Dinur,
E. Fischer,
G. Kindler,
R. Raz
and S. Safra,
**PCP characterizations of NP: Towards a polynomially-small
error-probability**, *Journal of Computational Complexity*
20 (2011), 413-504
(a preliminary version appeared as [S99]).

Cook has characterized the class NP in terms of the problem of determining whether or not a given set of boolean functions, each dependent on a constant number of variables, can be satisfied by one assignment. If these variables are allowed to have any fixed range, it is known that also distinguishing between the existence of an assignment satisfying all functions and the nonexistence of an assignment satisfying any fixed fraction of the functions, is NP-hard (for a fixed range which depends only on the above fraction). Bellare, Goldwasser, Lund and Russell have conjectured that if the range of the variables is allowed to be polynomial in the number of functions, than it is NP-hard to distinguish between the existence of a satisfying assignment to all and the nonexistence of an assignment satisfying an exponentially small fraction of the functions. This paper proves an asymptotic version of the conjecture, thus improving previously known results.

**[11c]**
E. Fischer and
Orly Yahalom
**Testing convexity properties of
tree colorings**,
*Algorithmica* 60 (2011), 766-805
(a preliminary version appeared as [T07]).

A coloring of the vertices of a tree is called convex, if the vertices colored with each color form induce a (connected) sub-tree. This notion is used for the definition of phylogenetic trees, and several of its computational aspects have been widely investigated. Here convexity, and several variants of this thereof (such as the convexity of all colors but one), are provided with constant query complexity property testers. The working assumption is that the tree structure is given in advance while the colors need to be queried. Weighted testing is also possible, and for convexity itself it is also distribution-free. The running time is as expected polynomial in the tree structure, but this can be done in a pre-processing stage and then only an additional constant time is required to process the results of the queries.

**[12]**
E. Fischer, O. Lachish,
A. Matsliah,
I. Newman and
Orly Yahalom
**On the query complexity of testing orientations
for being Eulerian**,
*Transactions on Algorithms*
8 (2012), article 15
(a preliminary version appeared as [R08]).

A problem which is about as old as the orientation model itself (see [R07a] above) is that of testing whether a graph orientation is Eulerian, i.e. whether every vertex has its incoming and outgoing degrees equal. A simple formulation, but testing for this is involved. First, it may be that the orientation is far from being Eulerian but all witnesses for this are linear in size, precluding 1-sided testing in the most general case.

2-sided testing is possible in a sublinear number of queries, but not a a constant number - even if the underlying graph is only a toroidal grid. All this is proven here. In the most general case, the algorithm is still non-adaptive and with a horrendous running time (some better special cases are also presented), so the investigation of this problem may not be over yet.

Back