Conference papers

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 [SIComp].

[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 paper initiates a thorough study of distributed property testing. The idea is to take the approximation notion of graph property testing, but instead of the original querying model, couple it with the computational model of distributed computation, and specifically the CONGEST model (note that the communication graph is also the input to be analysed).

This paper has a general conversion result for property testing algorithms in the dense graph model, and algorithms for specific problems (e.g. bipartiteness) in the sparse and general model, that are mostly faster than their original property-testing counterparts. For bipartiteness and cycle-freeness a lower bound is also provided.

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

In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified many distribution testing results under a single umbrella of “shape-restricted properties”. Basically, all such properties require the distributions to be close to being “piece-wise uniform” with respect to an interval partition of {1,…,n} whose size is not too large, while possibly satisfying other requirements.

This paper provides a simpler testing algorithm with a better dependency on the partition size and without a direct dependency on n. Moreover, it provides very efficient tests for such properties under the conditional testing model, as well as a conditional test for an extended class of properties.

The main engine for these results is a way of very quickly producing a partition of {1,…,n} into intervals satisfying a small-weight requirement with respect to the tested distribution. It turns out that with such a partition at hand, we no longer need to learn anything about the original interval partition through which the distribution satisfied its shape-restriction requirement.

[FOCS17] N. Alon, O. Ben-Eliezer and E. Fischer, Testing hereditary properties of ordered graphs and matrices, Proceedings of the 58th FOCS (2017), to appear.

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.