This lists papers appearing in refereed journals. Many of them are final (and extended) versions of conference papers.
[Disc96] 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 proved here for 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).
As it later turned out, the full conjecture was proved 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.
[Ars99] 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 proved, and a conjecture is formulated. These generalize the results proved 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 proved in: János Komlós, Tiling Turán theorems, Combinatorica 20 (2000), 203–218.
[JoGT99] 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.
Note: the conjectures in their exact form are now known not to hold. A thorough treatment of what holds is found in: P. Keevash and R. Mycroft, A multipartite Hajnal-Szemerédi theorem, J. of Combinatorial Theory Ser. B 114, 187–236 (2015).
[Disc99] 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 proved using the Regularity Lemma of Szemerédi, combined with a result proved by an incremental approach, and additional arguments.
Later, strong results regarding the El-Zahar Conjecture were proved by Sarmad Abbasi.
[EJComb99] 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.
[Comb00] N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451–476 (a preliminary version appeared as [FOCS99]).
We call a graph property testable if for every 0<ε<1 there exists a randomized algorithm that makes a constant number of queries from 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 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 proved that all first order graph properties of type “∃∀” are testable, while there exists a first order property of type “∀∃” that is not testable.
[JCTA-01] 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.
[JCTA-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 (a property also referred to as MC-finiteness). As an example, it 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 also for monadic second order expressions 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.
[IandC04] 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 proved 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 of queries required to test whether the sequence is monotone nondecreasing (or εn-far from it).
[RSA-04] 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 [CCC02]).
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.
[JCSS-04] 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 [FOCS02]).
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.
[JSym04] 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 proved 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 exists a satisfying graph with this many vertices is ultimately periodic. An extension to many-sorted logic is also presented.
[RSA-05] E. Fischer, Testing graphs for colorability properties, Random Structures and Algorithms 26 (2005), 289–309 (a preliminary version appeared as [SODA01]).
The positive part of [Comb00] was proved by showing the testability of a certain generalized notion of graph colorability. This paper proves the testability of two generalizations of this notion.
[SIComp05] 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 [STOC04]).
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 was used for proving the lower bound.
Several years later, in [CCC12], a simpler proof with much better parameters (and no regularity lemma) was found for this same result.
[ToC06] 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 [CCC05]).
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 [SIComp07].
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 with a constant number of queries but not tolerantly so. 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.
[Comb07] 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 [STOC01]. 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 exists a property with one quantifier alternation that is not testable.
[SIComp07a] E. Fischer and I. Newman, Testing versus estimation of graph properties, SIAM Journal on Computing37 (2007), 482–501 (a preliminary version appeared as [STOC05]).
From [SIComp05] one could garner hopes for finding a combinatorial characterization for the hardness of testing whole graph properties, not just single graphs, a hope which was realized later on. Here it is shown that there is a correlation between testability and having an approximation in terms of partitions having a strong regularity condition (also defined here).
Importantly this implies the following tolerant testing guarantee: If a graph property has a test with a constant number of queries for every ε, then it is also possible for every 0<ε1<ε2<1 to distinguish between graphs that are ε1-close to satisfying the property, and graphs that are ε2-far from satisfying it.
[SIComp07b] 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 [STOC01]. 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 [STOC01], or the tower function that was known from previous results.
[DiscAM08] 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, 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 (note that for a fixed k, a k-tree-decomposition can be found in polynomial time if one exists; also, an f(k)-clique decomposition can be found for a graph with clique-width k by the work of Oum and Seymour).
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.
[SIComp08] E. Fischer and A. Matsliah, Testing graph isomorphism, SIAM Journal on Computing 38 (2008), 207–225 (a preliminary version appeared as [SODA06]).
Testing for graph isomorphism is already known not to be possible with a constant number of queries from [Comb00], but how many queries are indeed required? Apart from the setting of two graphs that need to be queried, there is the setting of [SIComp05]: 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 settings. 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.
[SIComp09] 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 [STOC06]).
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.
[SIComp10a] 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 [LICS06]).
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 defines an approximate notion of language equivalence that is inspired by the property testing approximation. Here, 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 are shown to have far more efficient algorithms for a fixed approximation parameter ε. An extension to languages of trees is also discussed.
[SIComp10b] 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 [FOCS07]).
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 proved for hypergraphs? This paper provides a positive 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 algorithm for finding regular partitions (in Szemerédi’s sense) of graphs. Unlike previous algorithms concerning Szemerédi’s Regularity Lemma, here the algorithm can be guaranteed to find a small regular partition if one exists, rather than just finding some regular partition whose size is bounded by what the Regularity Lemma provides.
[JoCO11] 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 [STACS09]).
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 proved 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.
[CompComp11] I. Dinur, E. Fischer, G. Kindler, R. Raz and S. Safra, PCP characterizations of NP: Towards a polynomially-small error-probability, Computational Complexity 20 (2011), 413–504 (a preliminary version appeared as [STOC99]).
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 a single 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 (the variable range 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, then it is NP-hard to distinguish between the existence of an assignment satisfying every function and the nonexistence of an assignment satisfying an exponentially small fraction of the functions. This paper proves an asymptotic version of the conjecture, improving previously known results.
[Algo11] E. Fischer and Orly Yahalom, Testing convexity properties of tree colorings, Algorithmica 60 (2011), 766–805 (a preliminary version appeared as [STACS07]).
A coloring of the vertices of a tree is called convex, if the vertices colored with each color 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 of its variants (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 work can be done in a pre-processing stage, and then only an additional constant time is required to process the results of the queries.
[TALG-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 [RANDOM08]).
A problem which is about as old as the orientation model itself (see [RANDOM07a] for the orientation model) is that of testing whether a graph orientation is Eulerian, i.e. whether every vertex has its incoming and outgoing degrees equal. Despite the simple formulation, testing for this property is quite involved. For example, 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 with a sublinear number of queries, but not a a constant number, even if the underlying graph is guaranteed to be a toroidal grid. All this is proved here. In the most general case, the algorithm is adaptive and without a good running time (some better special cases are also presented), so the investigation of this problem may not be over yet.
[ToC14] S. Chakraborty, E. Fischer and A. Matsliah, Query complexity lower bounds for
reconstruction of codes, Theory of Computing 10 (2014), 551–569 (a preliminary version appeared as [ITCS11]).
Local reconstruction, as defined by Saks and Seshadhri, is similar to local decoding, but with one important difference: While in local decoding every bit has to be decoded correctly with some probability, in local reconstruction the random coins are treated globally, with the requirement that with high probability all relevant bits will be correctly decoded at once.
A simple way to create such a code is to start with a locally decodable code (for message reconstruction) or a self correctable code (for codeword reconstruction), and then amplify its decoding procedure so that a union bound ensures that with some probability all bits are correctly decoded in one go. This paper shows that, in some settings, there is no way to significantly outperform this method.
[ToCT16] E. Fischer, Y. Goldhirsh and O. Lachish, Testing formula satisfaction, ACM Transactions on Computation Theory 8 (2016), article 5 (a preliminary version appeared as [SWAT12]).
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. And/Or operations over {0,1} for Boolean formulas). This is given in advance, and an assignment to the variables is tested for the property that it will result with a given value (e.g. “1”) 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 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 arity-2 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.
[SIComp16] S. Chakraborty, E. Fischer, Y. Goldhirsh and A. Matsliah, On the power of conditional samples in distribution Testing, SIAM Journal on Computing 45 (2016), 1261–1296 (a preliminary version appeared as [ITCS13]).
Here a new model for distribution testing is introduced. Apart from the usual (and rather restricted) ability to receive samples chosen independently according to the distribution to be tested, under the new model 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 such as adaptivity (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, lower bounds are provided, showing that there are properties which resist testing also in this model. A very similar model was introduced independently by Cannone, Ron and Servedio, where they proved other results for it.
[DistComp19] K. Censor-Hillel, E. Fischer, G. Schwartzman and Y. Vasudev, Fast distributed algorithms for testing graph properties, Distributed Computing 32 (2019), 41–57 (a preliminary version appeared as [DISC16]).
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.
[Algo19] E. Fischer, O. Lachish and Y. Vasudev, Improving and extending the testing of distributions for shape-restricted properties, Algorithmica 81 (2019), 3765–3802 (a preliminary version appeared as [STACS17]).
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.
[JIntSeq23] Y. Filmus, E. Fischer, J. A. Makowsky and V. Rakita, MC-finiteness of restricted set partition functions, Journal of Integer Sequences 26 (2023), Article 23.7.4.
This paper investigate sequences of integers that result from counting the number of combinatorial objects satisfying given properties (for example, counting for every n the number of partitions of {1,…,n} with an odd number of elements in every part). Exact calculations of these sequences can be very hard, but this paper shows how to prove MC-finiteness for many of them. A sequence is MC-finite if it is ultimately periodic modulo every fixed integer m.
[JSL-24] E. Fischer and J.A. Makowsky, Extensions and limits of the Specker-Blatter theorem, Journal of Symbolic Logic 89 (2024), 1284–1312.
This paper investigates the Specker-Blatter theorem (see its description in the blurb for [JCTA-03]), essentially continuing my personal odyssey charted in [JCTA-03] and [JIntSeq23] and [2012].
As a positive result, this paper shows how “hard-coded” constants can be incorporated into use instances of the Specker-Blatter theorem. Starting with a similar reduction, a negative result provides closure to [JCTA-03], constructing an FOL sentence over a single ternary relation which is not MC-finite.
[ITrans24] S. Chakraborty, E. Fischer, A. Ghosh, G. Mishra and Sayantan Sen, Exploring the gap between tolerant and non-tolerant distribution testing, IEEE Transactions on Information Theory (2024), accepted (a preliminary version appeared as [RANDOM22]).
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.