This lists papers appearing in conferences with refereed proceedings. Whenever the summary just says that it is a preliminary version of another paper, first try looking for it in the journal papers section.
[STOC99] 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 [CompComp11]. This paper probably holds my personal record of time from conference version to journal version, not counting some papers that may remain conference-only.
[FOCS99] 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 [Comb00].
[SODA01] E. Fischer, Testing graphs for colorability properties, Proceedings of the 12th SODA (2001), 873–882.
This is the conference version of [RSA-05].
[STOC01] 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). On the other hand, there exists 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 proved 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 papers, [Comb07] and the improved (with N. Alon as an additional coauthor) [SIComp07b].
[FOCS01] 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 test 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.
I do not have a good copy of this paper to post here. My apologies.
[STOC02] 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 in 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 [IandC04]), and several works about 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 formulas, shows the existence of monotonicity-like properties for which non-adaptive testing is rather 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.
Again my apologies for not providing a copy here (some copies exist at large, among which the 1-column version is preferable).
[CCC02] 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 version of the improved [RSA-04] (now with J. Sgall as a coauthor).
[FOCS02] 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 [JCSS-04].
[COCOON03] 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 [JCTA-03]). Several venues of possible generalizations are explored; for some of them the theorem can be generalized, while for others counterexamples exist.
This paper is mostly subsumed in [2012] (it’s a book chapter so look for it under “Others”)
[STOC04] 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 [SIComp05].
[STOC05] 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 [SIComp07a].
[CCC05] 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 [ToC06].
[SODA06] E. Fischer and A. Matsliah, Testing graph isomorphism, Proceedings of the 17th SODA (2006), 299–308.
This is the preliminary version of [SIComp08].
[STOC06] 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 [SIComp09].
[LICS06] 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 improved and extended [SIComp10a].
[STACS07] 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 [Algo11].
[RANDOM07a] 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 programs (where the “parameter” consists of a whole branching program for deciding the property). [Algo11] above can be counted as another such example. A major line of investigation of such problems was 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 vertex t (st-connectivity) was not known to be testable. This article shows its testability with a number of queries depending only on ε, by using a sequence of combinatorial arguments and reductions ultimately leading to Newman’s result about branching programs.
[RANDOM07b] 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 [SIComp07b] hope was raised that the polynomial testing result there could be extended to matrices with more than two possible values, and perhaps also higher dimensional tensors (this question also appeared in some form already in [STOC01]). 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.
[FOCS07] 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 [SIComp10b].
[RANDOM08] 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 [TALG-12].
[STACS09] 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 [JoCO11].
[STACS10] 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.
[FSTTCS10] 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.
[ITCS11a] 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 variation 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.
[ITCS11b] 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 is the preliminary version of [ToC14].
[ICDT11] 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”, is defined and investigated. This paper provides an efficient test for this property (approximating the two parameters in its definition). It also provides a complementary method for speeding up database operations, such as natural join, when the property is known to hold.
[RANDOM11] 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 a test 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 this gap is bounded by a polynomial. Triangle-freeness is such a property.
[CCC12] 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 a fixed function g, where g depends only on the number of 1’s together with the values of a constant number of specific variables. An appealing conjecture is that such functions are essentially the only Boolean functions for which isomorphism can be tested. The paper also provides lower bounds for some isomorphism testing problems using the new method of “crunching”, introduced there. In particular it provides a simpler and more efficient (with respect to the produced constants) proof of the graph isomorphism testing result of [SIComp05].
[SWAT12] E. Fischer, Y. Goldhirsh and O. Lachish, Testing formula satisfaction, Proceedings of the 13th SWAT (2012), LNCS no. 7357, 376–387.
This is the preliminary version of [ToCT16].
[ICPP12] 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 Boolean circuits can be parallelized (but unfortunately not all of them).
[SODA13] 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 can be processed with 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 this 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 [Comb00] for dense graphs, but here it is the theoretical existence that counts.
[ITCS13] 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.
This is the preliminary version of [SIComp16].
[STOC13] 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 [SODA13]. Here variants of the techniques from [SODA13], that use so-called non-classical polynomials, are applied. We 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.
[ITCS14] E. Fischer, Y. Goldhirsh and O. Lachish, Partial tests, universal tests and decomposability, Proceedings of the 5th ITCS (2014), 483–500.
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 testing-with-proof scenario is essentially a decomposition of the original property into relatively few highly testable properties, 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” sample-based (as originally defined by Goldreich and Ron) tests with sublinear query complexity, whose querying scheme does not depend at all on the original.
[FOCS15] E. Fischer, O. Lachish and Y. Vasudev, Trading query complexity for sample-based testing and multi-testing scalability, Proceedings of the 48th FOCS (2015), 1163–1182.
The idea of this result is to take the last item of [ITCS14] to a new level. It is proved here that any property that has a test, whose number of queries depends only on the approximation parameter ε, can be tested using sample-based testing with sample probability n-α, where α depends only on ε. This holds for 2-sided error testing as well, while properties with a 1-sided error test will have respectively a 1-sided error sample-based test.
For the conversion to sample-based testing to happen, we show a way to treat a non-adaptive testing algorithm as little more than a uniform hypergraph. We then deploy a combinatorial lemma that may be interesting in its own right, that finds in every hypergraph with a linear number of edges a “constellation”, that is, a subset of the edges with good (average-like) guarantees on all its degrees outside a relatively small set of “core vertices”.
[DISC16] K. Censor-Hillel, E. Fischer, G. Schwartzman and Y. Vasudev, Fast distributed algorithms for testing graph properties, Proceedings of the 30th DISC (2016), 43–56.
This is the preliminary version of [DistComp19].
[STACS17] E. Fischer, O. Lachish and Y. Vasudev, Improving and extending the testing of distributions for shape-restricted properties, Proceedings of the 34th STACS (2017), article 23.
This is the preliminary version of [Algo19].
[FOCS17] N. Alon, O. Ben-Eliezer and E. Fischer, Testing hereditary properties of ordered graphs and matrices, Proceedings of the 58th FOCS (2017), 848–858.
In 2005 Alon and Shapira (following a line of research starting with [Comb00]) showed that every hereditary graph property is testable. But what about properties of graphs having a fixed vertex order, or the related question of properties of matrices? This paper settles this open question, establishing a removal lemma (and hence a test) that works for vertex-ordered graphs. This is done by establishing a regularity scheme that combines the notions of a regular graph partition with a special case of the regularity-like notion from [Comb07]. For proving the removal lemma from the regularity scheme, a quantitative Ramsey-like lemma is developed.
[SODA18] E. Fischer, F. Magniez and T. Starikovskaya, Improved bounds for testing Dyck languages, Proceedings of the 29th SODA (2018), 1529–1544.
A string of opening and closing parentheses of k types is said to be in Dyck-k if it consists only of well-formed (and balanced) parentheses. This paper improves both the upper and the lower bounds (in terms of the required power of n in the number of queries) for testing a string for being in a Dyck-k language for a fixed k.
The new upper bounds are made possible by a recursion technique for property testing. The lower bound follows from a lower bound proved for truestring equivalence – the property that two strings consisting of zero, one, and “null” elements become identical after removing the nulls.
[CCC18] O. Ben-Eliezer and E. Fischer, Earthmover resilience and testing in ordered structures, Proceedings of the 33rd CCC (2018), Article 18.
A followup of sorts to [FOCS17], this paper considers the application of graph “meta-testing” methods, such as those of [SIComp07a] and [SIComp09], to ordered graphs and similar structures. Logically, testing ordered graph properties is the same as the most general property testing question, but here there is progress on identifying which of those properties have a degree of “graphness” in them. Such properties would be expected to either be testable with a canonical test or not at all. This paper defines a notion of earthmover-resilience, and proves the equivalence of being canonically testable with being both earthmover-resilient and tolerantly testable. These in turn are equivalent to being estimable (as in [SIComp07a]), and to being regular-reducible (in a similar vain to [SIComp09]).
[ITCS20] O. Ben-Eliezer, E. Fischer, Amit Levi and Ron D. Rothblum, Hard properties with (very) short PCPPs and their applications, Proceedings of the 11th ITCS, LIPIcs vol. 151 (2020), Article 9.
A separation of intolerant from tolerant testing was proved in [ToC06] (originally [CCC05]). But exactly how hard is it to tolerantly test can a fully testable property be? This question is related to a deeper one – what is the minimum size of the proof needed for a PCPP for a property computable in time O(t)? Certainly one cannot go below a size linear in t, but for now it appears that going below quasilinear in t is also very hard (especially that differing computational models are usually also quasilinear in each other).
A related question is whether there exists any property that is maximally hard to test (which implies a linear lower bound on the proof size) and still has a linear proof size. We make progress on this question, and construct a hard property with a much smaller than quasilinear (though not yet linear) proof size. This in itself is also sufficient for improving upon the previously known tolerant testing separation. On the way we define some PCPP-related primitives that might be useful in the future.
[ITCS21] O. Ben-Eliezer, E. Fischer, Amit Levi and Yuichi Yoshida, Ordered graph limits and their applications, Proceedings of the 12th ITCS (2021), Article 42.
This paper develops an analytic regularity framework for ordered graphs, for which a “classical” regularity framework was developed in [FOCS17]. Analyzing limit objects of vertex-ordered graphs pose extra challenges when compared to the graph limit objects (called “graphons”) originally developed by Borgs, Chayes, Lovász, Sós, B. Szegedy, and Vesztergombi.
For proving the compactness of the space of limit objects (which we call “orderons”), we use a new shape-restricting technique (the vertex order makes the “shape” of sets of “vertices of a certain type” important, while for graphs only its size is important). For making the limit object useful for analyzing hereditary properties, we prove a new “pixelization” lemma, that allows to approximate an orderon by a stochastic block model with a guarantee of “no new features”.
[RANDOM22] S. Chakraborty, E. Fischer, A. Ghosh, G. Mishra and Sayantan Sen, Exploring the gap between tolerant and non-tolerant distribution testing, Proceedings of the 26th RANDOM (2022), Article 27.
This paper goes back to the original sampling model of distribution testing, and explores the possible relations between standard (“intolerant”) and tolerant testing of properties. For index-invariant properties, it shows that (up to polylog factors) the difference can be at most quadratic. The tolerant test uses only the existence of the original standard test, not its details. Some evidence towards the same relationship for general (not index-invariant) properties is presented, though an actual proof (if such exists) remains an open question. The paper also contains a learning algorithm for small support distributions, that adapts to the input without knowing the support size parameter in advance.
[COLT23] S. Chakraborty, E. Fischer, A. Ghosh, G. Mishra and Sayantan Sen, Testing of index-invariant properties in the Huge Object model, Proceedings of the 36th COLT (2023), 3065–3136.
The Huge Object model of distribution testing, first defined by Goldreich and Ron in 2022, deals with distributions over objects that in themselves are too large to be read directly, hence mandating queries into the samples obtained. In turn this requires using a different norm, the Earth-mover distance, and re-introduces “algorithmic” elements and adaptivity into the testers’ query strategies. This paper defines and investigate a natural notion of invariance that is weaker (allowing for more interesting properties) as compared to the label-invariance notion defined for the standard distribution testing model. In particular, we show that index-invariant properties that also have a VC-dimension bound are testable (by learning) with a number of queries independent of the input length, along with corresponding lower bound examples. We also show that the quadratic upper bound between adaptive and non-adaptive algorithms (shown by a canonical testing construction) is nearly optimal, by constructing a property exhibiting such a gap, based on hard to test codes.
[CSL24] E. Fischer and J.A. Makowsky, Extensions and limits of the Specker-Blatter theorem, Proceedings of the 32nd CSL (2024), Article 26.
This is the preliminary version of [JSL-24].