List of publications

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.


Conference papers

[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 L1 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 L1 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 l1 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.


Journal papers

[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)!k2) 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 n1,...,nl 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 n1,...,nl 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 n1,...,nl 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 εn2 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 Computing37 (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<ε12<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 G1, G2, G3... 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