Eldar Fischer

STOC Conference 2025 Conference Paper

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

• Sourav Chakraborty 0001
• Eldar Fischer
• Arijit Ghosh
• Amit Levi
• Gopinath Mishra
• Sayantan Sen

The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on {0,1} n , where n is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by the total number of queries that were made to them. Index-invariant properties under this model were defined in [Chakraborty et al., COLT 23], as a compromise between enduring the full intricacies of string testing when considering unconstrained properties, and giving up completely on the string structure when considering label-invariant properties. Index-invariant properties are those that are invariant through a consistent reordering of the bits of the involved strings. Here we provide an adaptation of Szemerédi’s regularity method for this setting, and in particular show that if an index-invariant property admits an є-test with a number of queries depending only on the proximity parameter є, then it also admits a distance estimation algorithm whose number of queries depends only on the approximation parameter.

CSL Conference 2024 Conference Paper

Extensions and Limits of the Specker-Blatter Theorem

• Eldar Fischer
• Johann A. Makowsky

The original Specker-Blatter Theorem (1983) was formulated for classes of structures 𝒞 of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set [n] is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol c, there are n possible interpretations on [n] for c. We say that a constant c is hard-wired if c is always interpreted by the same element j ∈ [n]. In this paper we show: (i) The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. (ii) The Specker-Blatter Theorem does not hold already for 𝒞 with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers B_{r, A}, restricted Stirling numbers of the second kind S_{r, A} or restricted Lah-numbers L_{r, A}. Here r is an non-negative integer and A is an ultimately periodic set of non-negative integers.

SODA Conference 2018 Conference Paper

Improved bounds for testing Dyck languages

• Eldar Fischer
• Frédéric Magniez
• Tatiana Starikovskaya

In this paper we consider the problem of deciding membership in Dyck languages, a fundamental family of context-free languages, comprised of well-balanced strings of parentheses. In this problem we are given a string of length n in the alphabet of parentheses of m types and must decide if it is well-balanced. We consider this problem in the property testing setting, where one would like to make the decision while querying as few characters of the input as possible. Property testing of strings for Dyck language membership for m = 1, with a number of queries independent of the input size n, was provided in [Alon, Krivelevich, Newman and Szegedy, SICOMP 2001]. Property testing of strings for Dyck language membership for m ≥ 2 was first investigated in [Parnas, Ron and Rubinfeld, RSA 2003]. They showed an upper bound and a lower bound for distinguishing strings belonging to the language from strings that are far (in terms of the Hamming distance) from the language, which are respectively (up to polylogarithmic factors) the 2/3 power and the 1/11 power of the input size n. Here we improve the power of n in both bounds. For the upper bound, we introduce a recursion technique, that together with a refinement of the methods in the original work provides a test for any power of n larger than 2/5. For the lower bound, we introduce a new problem called Truestring Equivalence, which is easily reducible to the 2-type Dyck language property testing problem. For this new problem, we show a lower bound of n to the power of 1/5.

FOCS Conference 2017 Conference Paper

Testing Hereditary Properties of Ordered Graphs and Matrices

• Noga Alon
• Omri Ben-Eliezer
• Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs - graphs with a totally ordered vertex set and a finite set of possible edge colors - showing that any hereditary property of such graphs is strongly testable, i. e. , testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of two-dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05; SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that if such a graph is far enough from satisfying a certain hereditary property, then most of its induced vertex-ordered subgraphs on a certain (large enough) constant number of vertices do not satisfy the property as well. The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for multipartite graphs with “undesirable” edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph.

FOCS Conference 2015 Conference Paper

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

• Eldar Fischer
• Oded Lachish
• Yadu Vasudev

We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Gold Reich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm. The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hyper graphs that may be of independent interest. When analyzing a hyper graph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.

STOC Conference 2013 Conference Paper

Every locally characterized affine-invariant property is testable

• Arnab Bhattacharyya 0001
• Eldar Fischer
• Hamed Hatami
• Pooya Hatami
• Shachar Lovett

SODA Conference 2013 Conference Paper

Testing Low Complexity Affine-Invariant Properties

• Arnab Bhattacharyya 0001
• Eldar Fischer
• Shachar Lovett

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, for instance, that the Reed-Muller code over F p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials, except that having low degree is preserved by composition with affine maps. The complexity of an affine-invariant property refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize. A more precise statement of our main result is that for any fixed prime p ≥ 2 and fixed integer R ≥ 2, any affine-invariant property of functions f: F n p → [ R ] is testable, if the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.

FOCS Conference 2007 Conference Paper

Approximate Hypergraph Partitioning and Applications

• Eldar Fischer
• Arie Matsliah
• Asaf Shapira

We show that any partition-problem of hypergraphs has an O(n) time approximate partitioning algorithm and an efficient property tester. This extends the results of Goldreich, Goldwasser and Ron who obtained similar algorithms for the special case of graph partition problems in their seminal paper (1998). The partitioning algorithm is used to obtain the following results: ldr We derive a surprisingly simple O(n) time algorithmic version of Szemeredi's regularity lemma. Unlike all the previous approaches for this problem which only guaranteed to find partitions of tower-size, our algorithm will find a small regular partition in the case that one exists; ldr For any r ges 3, we give an O(n) time randomized algorithm for constructing regular partitions of r-uniform hypergraphs, thus improving the previous O(n 2r-1 ) time (deterministic) algorithms. The property testing algorithm is used to unify several previous results, and to obtain the partition densities for the above problems (rather than the partitions themselves) using only poly(1/isin) queries and constant running time.

STOC Conference 2006 Conference Paper

A combinatorial characterization of the testable graph properties: it's all about regularity

• Noga Alon
• Eldar Fischer
• Ilan Newman
• Asaf Shapira

A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was raised in the 1996 paper of Goldreich, Goldwasser and Ron [25] that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

SODA Conference 2006 Conference Paper

Testing graph isomorphism

• Eldar Fischer
• Arie Matsliah

STOC Conference 2005 Conference Paper

Testing versus estimation of graph properties

• Eldar Fischer
• Ilan Newman

The topic of tolerant property testing, that of distinguishing input instances that are far from satisfying a property from those that are close enough to satisfying it (as opposed to distinguishing the far instances only from the satisfying instances), has recently become an active topic of research in the field of combinatorial property testing [13]. In the general setting, there exist properties that are testable but not tolerantly testable [10]. However, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable, but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant.In the course of the construction of this algorithm we develop a framework for extending Szemerédi's Regularity Lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. This work is also connected to the question of finding a combinatorial characterization of the testable graph properties, and to the question of efficiently finding a regular partition.

I&C Journal 2004 Journal Article

On the strength of comparisons in property testing

• Eldar Fischer

An ϵ-test for a property P of functions from D={1, …, d} to the positive integers is a randomized algorithm, which makes queries on the value of an input function at specified locations, and distinguishes with high probability between the case of the function satisfying P, and the case that it has to be modified in more than ϵd places to make it satisfy P. We prove that an ϵ-test for a property of integer sequences, such as the property of the sequence being a monotone nondecreasing sequence, that depends (in a strict sense) only on the order relations between the sequence members, cannot perform less queries (in the worst case) than the best ϵ-test which uses only comparisons between the queried values. In addition, we show that an adaptive algorithm for testing that a sequence is monotone non-decreasing performs no better than the best non-adaptive one, with respect to query complexity. From this follows a tight lower bound on tests for this property.

STOC Conference 2004 Conference Paper

The difficulty of testing for isomorphism against a graph that is given in advance

• Eldar Fischer

Motivated by a question from [6], we investigate the number of queries required for testing that an input graph G is isomorphic to a graph H that is given in advance. Our main result is that the more "complex" H is, the more queries it takes to test an input graph G for the property of being isomorphic to H . This is provided in terms of an upper bound and a lower bound on the number of queries, giving a relation between this number and a natural measure of the complexity of H .

STOC Conference 2002 Conference Paper

Monotonicity testing over general poset domains

• Eldar Fischer
• Eric Lehman
• Ilan Newman
• Sofya Raskhodnikova
• Ronitt Rubinfeld
• Alex Samorodnitsky

The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are 'far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n -dimensional hypercube {1,…, m } n . These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2 -CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.

FOCS Conference 2002 Conference Paper

Testing Juntas

• Eldar Fischer
• Guy Kindler
• Dana Ron
• Muli Safra
• Alex Samorodnitsky

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

SODA Conference 2001 Conference Paper

Testing graphs for colorable properties

• Eldar Fischer

STOC Conference 2001 Conference Paper

Testing of matrix properties

• Eldar Fischer
• Ilan Newman

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property P and an input f , distinguish between the case that f satisfies P , and the case that no input that differs from f in less than some fixed fraction of the places satisfies P . An (ε,q) -test for P is a randomized algorithm that queries at most q places of an input x and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε -fraction of the places of f need to be changed in order for it to have the property.

FOCS Conference 2001 Conference Paper

Testing Random Variables for Independence and Identity

• Tugkan Batu
• Lance Fortnow
• Eldar Fischer
• Ravi Kumar 0001
• Ronitt Rubinfeld
• Patrick White

Given access to independent samples of a distribution A over [n] /spl times/ [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i. e. , whether A is /spl epsi/-close in the L/sub 1/ norm to the product distribution A/sub 1//spl times/A/sub 2/ for some distributions A/sub 1/ over [n] and A/sub 2/ over [m]. The sample complexity of our test is O/spl tilde/(n/sup 2/3/m/sup 1/3/poly(/spl epsi//sup -1/)), assuming without loss of generality that m/spl les/n. We also give a matching lower bound, up to poly (log n, /spl epsi//sup -1/) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is /spl epsi/-close in L/sub 1/ norm to an explicitly specified distribution Y. Our test uses O/spl tilde/(n/sup 1/2/poly(/spl epsi//sup -1/)) samples, which nearly matches the known tight bounds for the case when Y is uniform.

FOCS Conference 1999 Conference Paper

Efficient Testing of Large Graphs

• Noga Alon
• Eldar Fischer
• Michael Krivelevich
• Mario Szegedy

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

STOC Conference 1999 Conference Paper

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

• Irit Dinur
• Eldar Fischer
• Guy Kindler
• Ran Raz
• Muli Safra