We study online embeddings of metric spaces into Euclidean spaces of a constant dimension d > 1, against an adaptive adversary. While the case of d = 1 is well understood, for higher dimensions little is known. In particular, even for d = 2 it remains unknown whether the worst-case distortion grows exponentially with the number of exposed points, as it does in the case for the line, or whether it is polynomial, as in the case for unbounded d. Our first result is about fixed solid graphs, i.e., K₅, whose edges are solid intervals, equipped with the shortest-path metric. We show that if the input points arrive from such a metric space, they can indeed be online-embedded into ℝ² with a polynomial distortion. This refutes the previously believed conjecture that the topological non-embeddability of K₅ into the plane could be exploited for establishing exponential lower bounds. The second results is about online embeddings of tree metrics of a certain type, including, e.g., ultrametrics and HST’s. Somewhat surprisingly, we show that for metrics from this class the worst-case online embedding into ℝ^d is not much worse that the offline embedding, both being n^Θ(1/d), and this holds even when d = Θ(log n). This is in a stark contrast to the more common situation where the online-offline gap is typically huge, and even exponential. This result allows us to transfer results about probabilistic embeddings of metrics into HST’s to low-dimensional Euclidean spaces, in an almost optimal possible manner.

Given a permutation \(\pi:[k]\to[k]\), a function \(f:[n]^{d}\to\mathbb{R}\) is said to be \(\pi\)-free if there are no \(k\) indices \(x_{1}\prec\cdots\prec x_{k}\in[n]^{d}\) such that \(f(x_{i})\lt f(x_{j})\) and \(\pi(i)\lt \pi(j)\) for all \(i,j\in[k]\), where \(\prec\) is the natural partial order over \([n]^{d}\). For a fixed \(\pi\) and \(\epsilon\in(0,1)\), the problem of \(\epsilon\)-testing \(\pi\)-freeness is to distinguish the case that \(f\) is \(\pi\)-free from the case that at least \(\epsilon n^{d}\) values of \(f\) need to be modified in order to make it \(\pi\)-free. When \(k=2\), the problem is identical to monotonicity testing, which is extensively studied in property testing. The case of \(k>2\) has also received significant attention for functions \(f:[n]\to\mathbb{R}\).

Can every n-bit boolean function with deterministic query complexity k≪ n be restricted to O(k) variables such that the query complexity remains Ω(k)? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results. Negative: Query complexity cannot be condensed in general: There is a function f with query complexity k such that any restriction of f to O(k) variables has query complexity O(k3/4). Positive: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021). Along the way we show the existence of Shearer extractors — a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.

Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the amount of attention it has received, there are important aspects of the problem that are not yet fully understood. There are no better lower bounds for LIS estimation than the obvious bounds implied by testing monotonicity (for adaptive or nonadaptive algorithms). In this paper, we give the first nontrivial lower bound on the complexity of LIS estimation, and also provide novel algorithms that complement our lower bound. Specifically, for every constant $ε\in (0,1)$, every nonadaptive algorithm that outputs an estimate of the length of the LIS in an array of length $n$ to within an additive error of $ε\cdot n$ has to make $\log^{Ω(\log (1/ε))} n)$ queries. Next, we design nonadaptive LIS estimation algorithms whose complexity decreases as the the number of distinct values, $r$, in the array decreases. We first present a simple algorithm that makes $\tilde{O}(r/ε^3)$ queries and approximates the LIS length with an additive error bounded by $εn$. We then use it to construct a nonadaptive algorithm with query complexity $\tilde{O}(\sqrt{r} \cdot \text{poly}(1/λ))$ that, for an array with LIS length at least $λn$, outputs a multiplicative $Ω(λ)$-approximation to the LIS length. Finally, we describe a nonadaptive erasure-resilient tester for sortedness, with query complexity $O(\log n)$. Our result implies that nonadaptive tolerant testing is strictly harder than nonadaptive erasure-resilient testing for the natural property of monotonicity.

A $k$-decision tree $t$ (or $k$-tree) is a recursive partition of a matrix (2D-signal) into $k\geq 1$ block matrices (axis-parallel rectangles, leaves) where each rectangle is assigned a real label. Its regression or classification loss to a given matrix $D$ of $N$ entries (labels) is the sum of squared differences over every label in $D$ and its assigned label by $t$.Given an error parameter $\varepsilon\in(0,1)$, a $(k,\varepsilon)$-coreset $C$ of $D$ is a small summarization that provably approximates this loss to \emph{every} such tree, up to a multiplicative factor of $1\pm\varepsilon$. In particular, the optimal $k$-tree of $C$ is a $(1+\varepsilon)$-approximation to the optimal $k$-tree of $D$.We provide the first algorithm that outputs such a $(k,\varepsilon)$-coreset for \emph{every} such matrix $D$. The size $|C|$ of the coreset is polynomial in $k\log(N)/\varepsilon$, and its construction takes $O(Nk)$ time.This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry. Experimental results on \texttt{sklearn} and \texttt{lightGBM} show that applying our coresets on real-world data-sets boosts the computation time of random forests and their parameter tuning by up to x$10$, while keeping similar accuracy. Full open source code is provided.

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f : {1,…, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i1 < i2 < · · · < ik, such that f (ix) > f (iy) whenever π(χ) > π(y). If f does not contain π, we say f is π-free. For example, for π = (2,1), the property of being π-free is equivalent to being non-decreasing, i.e. monotone. The property of being (k,k — 1,…, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidden) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i.e., (k,k - 1,…, 1) and (1, 2,…, k), we design non-adaptive one-sided error ε-tests of (∊−1 log n)O(k2) query complexity. For non-monotone patterns, we show that for any size-k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ/η) queries. This general lower bound can be further strengthened for specific non-monotone k-length patterns to Ω(n1–2/(k+1)). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e−1/kn1–1/k) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E.g., for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊−1 logn)O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

A D-disc around a vertex v of a graph G=(V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most epsilon n edges, by a set of D-discs around the vertices, for D=D(epsilon) that is independent of the size of the graph. Such a result was already known for planar graphs (and any hyperfinite graph class), in the limited case of bounded degree graphs (that is, their maximum degree is bounded by some fixed constant, independent of |V|). We prove this result with no assumption on the degree of the graph. A pure combinatorial consequence of this result is that two outerplanar graphs that share the same local views are close to be isomorphic. We also obtain the following property testing results in the sparse graph model: * graph isomorphism is testable for outerplanar graphs by poly(log n) queries. * every graph property is testable for outerplanar graphs by poly(log n) queries. We note that we can replace outerplanar graphs by a slightly more general family of k-edge-outerplanar graphs. The only previous general testing results, as above, where known for forests (Kusumoto and Yoshida), and for some power-law graphs that are extremely close to be bounded degree hyperfinite (by Ito).

Let $\mathcal{F}$ be a set system over an underlying finite set $X$, and let $\mu$ be a nonnegative measure over $X$; i.e., for every $S \subseteq X$, $\mu(S)=\sum_{x\in S} \mu(x)$. A measure $\mu^*$ on $X$ is called a multiplicative ${\lambda}$-approximation of $\mu$ on $(\mathcal{F},X)$ if for every $S\in \mathcal{F}$ it holds that $a\mu(S) \leq \mu^*(S) \leq b \mu(S)$, and $b/a = \lambda \geq 1$. The central question raised and partially answered in the present paper is about the existence of meaningful structural properties of $\mathcal{F}$ implying that for any $\mu$ on $X$ there exists an ${{1+\epsilon} \over {1-\epsilon}}$-approximation $\mu^*$ supported on a small subset of $X$. It turns out that the parameter that governs the support size of a multiplicative approximation is the triangular rank of $\mathcal{F}$, ${\rm trk}(\mathcal{F})$. It is defined as the maximal length of a sequence of sets $\{S_i\}_{i=1}^t $ in $\mathcal{F}$ such that for all $1

A $k$-disc around a vertex $v$ of a graph $G=(V,E)$ is the subgraph induced by all vertices of distance at most $k$ from $v$. We show that the structure of a planar graph on $n$ vertices, and with constant maximum degree $d$, is determined, up to the modification (insertion or deletion) of at most $\epsilon d n$ edges, by the frequency of $k$-discs for certain $k=k(\epsilon,d)$ that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two $d$-bounded degree graphs that have similar frequency vectors (that is, the $\ell_1$ difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.

Let F be a set system over an underlying finite set X, and let μ be a nonnegative measure over X. I.e., for every S ⊆ X, μ(S) = σx ∊ S μ(x). A measure μ* on X is called a multiplicative λ-approximation of μ on (F, X) if for every S ∊ F it holds that aμ(S) ≤ μ*(S) ≤ bμ(S), and b/a = λ ≥ 1. The central question raised and partially answered in the present paper is about the existence of meaningful structural properties of F implying that for any μ on X there exists an -approximation μ* supported on a small subset of X. It turns out that the parameter that governs the support size of a multiplicative approximation is the triangular rank of F, trk(F). It is defined as the maximal length of a sequence of sets {Si}ti = 1 in F such that for all 1 < i ≤ t, Si ⊊ ∪j < i Sj. We show that for any μ on X and 0 < ∊ < 1, there is measure μ* that -approximates μ on (X, F), and has support of size O(trk(F)2 log(trk(F))/poly(∊)). We also present two alternative constructions which in some cases improve upon this bound. Conversely, we show that for any 0 ≤ ∊ < 1 there exists a μ on X that cannot be -approximated on (F, X) by any μ* with support of size < trk(F). For special families F this bound can be improved to Ω(trk(F)/∊). As an application we show a new dimension-reduction result for ℓ1 metrics: Any ℓ1-metric on n points can be (efficiently) embedded with -distortion into ℝO(n/∊2) equipped with the ℓ1 norm. This improves over the best previously known bound of O(n log n/poly(∊)) on dimension, due to Schechtman. We obtain also some new results on efficient sampling of Euclidean volumes. In order to make the general framework applicable to this setting, we develop the basic theory of finite volumes, analogous to the theory of finite metrics, and get results of independent interest in this direction. To do so, we use basic combinatorial/topological facts about simplicial complexes, and study the naturally arising questions.

Motivated by applications in combinatorial optimization, we study the extent to which the global properties of a metric space, and especially its embeddability into $\ell_1$ with low distortion, are determined by the properties of its small subspaces. We establish both upper and lower bounds on the distortion of embedding locally constrained metrics into various target spaces. Other aspects of locally constrained metrics are studied as well, in particular, how far are those metrics from general metrics.

We consider testing directed graphs Eulerianity in the orientation model introduced in Halevy et al. [2005]. Despite the local nature of the Eulerian property, it turns out to be significantly harder to test than other properties studied in the orientation model. We show a nonconstant lower bound on the query complexity of 2-sided tests and a linear lower bound on the query complexity of 1-sided tests for this property. On the positive side, we give several 1-sided and 2-sided tests, including a sublinear query complexity 2-sided test, for general graphs. For special classes of graphs, including bounded-degree graphs and expander graphs, we provide improved results. In particular, we give a 2-sided test with constant query complexity for dense graphs, as well as for expander graphs with a constant expansion parameter.

A property testing algorithm for a property Π in the bounded degree graph model[7] is an algorithm that, given access to the adjacency list representation of a graph G=(V,E) with maximum degree at most d, accepts G with probability at least 2/3 if G has property Π, and rejects G with probability at least 2/3, if it differs on more than ε dn edges from every d-degree bounded graph with property Π. A property is testable, if for every ε,d and n, there is a property testing algorithm Aε,n,d that makes at most q(ε,d) queries to an input graph of n vertices, that is, a non-uniform algorithm that makes a number of queries that is independent of the graph size.

Property testing is a rapidly growing field of research. Typically, a property testing algorithm proceeds by quickly determining whether an input can satisfy some condition, under the assumption that most inputs do not satisfy it. If the input is "far" from satisfying the condition, the algorithm is guaranteed to reject it with high probability. Applying this paradigm to image detection is desirable since images are large objects and a lot of time can be saved by quickly rejecting images which are "far" from satisfying a certain condition the user is interested in. Further, typically most inputs are, indeed, "far" from the sought images. We demonstrate this by analyzing the problem of deciding whether a binary image can be partitioned according to a template represented by a rectangular grid, and introduce a quick "rejector," which tests an image extracted from the input image, but whose size, as well as the time required to construct it, are constants which are independent of the input image size. With high probability, the rejector dismisses the inputs which are "far" from the template.

The Target Set Selection problem proposed by Kempe, Kleinberg, and Tardos, gives a nice clean combinatorial formulation for many problems arising in economy, sociology, and medicine. Its input is a graph with vertex thresholds, the social network, and the goal is to find a subset of vertices, the target set, that "activates" a prespecified number of vertices in the graph. Activation of a vertex is defined via a so-called activation process as follows: Initially, all vertices in the target set become active. Then at each step i of the process, each vertex gets activated if the number of its active neighbors at iteration i -- 1 exceeds its threshold. The activation process is "monotone" in the sense that once a vertex is activated, it remains active for the entire process.

A common thread in all of the 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 ${\cal P}$ can be tested with a constant number of queries if and only if testing ${\cal 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 first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653–750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

A language L has a property tester if there exists a probabilistic algorithm that given an input x queries only a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.

We study a model of graph related formulae that we call the constraint-graph model. A constraint-graph is a labeled multi-graph (a graph where loops and parallel edges are allowed), where each edge e is labeled by a distinct Boolean variable and every vertex is associated with a Boolean function over the variables that label its adjacent edges. A Boolean assignment to the variables satisfies the constraint graph if it satisfies every vertex function. We associate with a constraint-graph G the property that consists of all assignments satisfying G, denoted SAT(G). We show that the above model is quite general. That is, for every property of strings P there exists a property of constraint-graphs PGsuch that P is testable using q queries if and only if PGis thus testable. In addition, we present a large family of constraint-graphs for which SAT(G) is testable with constant number of queries. As an implication of this, we infer the testability of some edge coloring problems (e.g. the property of two coloring of the edges in which every node is adjacent to at least one vertex of each color). Another implication is that every property of Boolean strings that can be represented by a read-twice CNF formula is testable. We note that this is the best possible in terms of the number of occurrences of every variable in a formula.

Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451–476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is $\epsilon$-testable. However, the complexity of the test is double-tower with respect to $1/\epsilon$, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is $\epsilon$-testable, with a number of queries that is polynomial in $1/\epsilon$. Our main tool is a new “conditional” version of the regularity lemma for binary matrices, which may be interesting on its own.

Tolerant testing is an emerging topic in the field of property testing, which was defined in [M. Parnas, D. Ron, and R. Rubinfeld, J. Comput. System Sci., 72 (2006), pp. 1012–1042] and has recently become a very active topic of research. In the general setting, there exist properties that are testable but are not tolerantly testable [E. Fischer and L. Fortnow, Proceedings of the $20$th IEEE Conference on Computational Complexity, 2005, pp. 135–140]. On the other hand, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable (which was already implicitly proved in [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451–476] and [O. Goldreich and L. Trevisan, Random Structures Algorithms, 23 (2003), pp. 23–57]), 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 proof 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. In particular, we construct a probabilistic algorithm that finds the parameters of a regular partition of an input graph using a constant number of queries, and an algorithm to find a regular partition of a graph using a $\mathrm{TC}_0$ circuit. This, in some ways, strengthens the results of [N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, J. Algorithms, 16 (1994), pp. 80–109].

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.

We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\ell_1$ with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs and include the family of weighted $k\times n$ planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24(2004), pp. 233-269] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We conjecture that these embeddings for k-outerplanar graphs may serve as building blocks for $\ell_1$ embeddings of more general metrics.

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 Szemeredi'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.

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

We consider a fault tolerance broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broadcasted with error probability bounded by a fixed constant /spl epsi/. The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivious protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. The primal complexity measure in this model is the total number of broadcasts that is performed by the protocol. We present here the first linear complexity protocols for several classes of Boolean functions, including the OR function, functions that have O(l)-minterm (maxterm) size, functions that have linear size AC/sub 0/ formulae and some other functions. This answer an open question of Yao (1997), considering this fault tolerance model of El-Gamal (1984) and Gallager (1988).

We construct a property on 0/1-strings that has a representation by a collection of width 3, read-twice oblivious branching programs, but for which any 2-sided /spl epsi/-testing algorithm must make at least /spl Omega/(n/sup 1/10/) many queries for some fixed small enough /spl epsi/. This shows that Newman's result (2000) cannot be generalized to read-k-times functions for k > 1.

(MATH) We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than $\Omega(\sqrt\log n\,)$. This matches Rao's general upper bound for metric embedding of planar graphs into Euclidean space, [14], thus resolving the question of how well do planar metrics embed in Euclidean spaces.

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.

Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750] and inspired by Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271], deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x has the property or is "far" from having the property. The main result here is that, if ${\cal G}= \{ g_n:\{0,1\}^n \rightarrow \{0,1\} \}$ is a family of Boolean functions which have oblivious read-once branching programs of width w, then, for every n and $\epsilon > 0$, there is a randomized algorithm that always accepts every $x \in \{0,1\}^n$ if $g_n(x)=1$ and rejects it with high probability if at least $\epsilon n$ bits of x should be modified in order for it to be in g n -1 (1). The algorithm makes $(\frac{2^{w}}{\epsilon})^{O(w)}$ queries. In particular, for constant $\epsilon$ and w, the query complexity is O(1). This generalizes the results of Alon et al.\ [Proceedings of the40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1999, pp. 645--655] asserting that regular languages are $\epsilon$-testable for every $\epsilon > 0$.

Both collections above are variants of properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations (and some additional relations for the bipartite graph properties). We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n 1=10) (for a small enough fixed ffl) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. \\Lambda

Combinatorial property testing, initiated formally by (Goldreich et al., 1996) and inspired by (Rubinfeld and Sudan, 1996), deals with the following relaxation of decision problems: given a fixed property and an input x, one wants to decide whether x has the property or is being far from having the property. The main result here is that if G={g:{0,1}/sup n//spl rarr/{0,1}} is a family of Boolean functions that have read-once branching programs of width w, then for every n and /spl epsiv/>0 there is a randomized algorithm that always accepts every x/spl isin/{0,1}/sup n/ if g(x)=1, and rejects it with height probability if at least /spl epsiv/n bits of x should be modified in order for it to be in g/sup -1/(1). The algorithm queries (2w//spl epsiv/)/sup 0(w)/ many queries. In particular, for constant /spl epsiv/ and w, the query complexity is 0(1). This generalizes the results of (Alon et al., 1999) asserting that regular languages are efficiently (/spl epsiv/,O(1))-testable.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language $L\in \{0,1\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\in L$ and rejects it with high probability if w has to be modified in at least $\epsilon n$ positions to create a word in L. The algorithm queries $\tilde{O}(1/\epsilon)$ bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in $1/\epsilon$. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of $\epsilon$. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Motivated by many recent algorithmic applications, the paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred where the graph is embedded into l/sub 1/ space. The main results are: 1. Explicit constant-distortion embeddings of all series parallel graphs, and all graphs with bounded Euler number. These are thus the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, we obtain algorithms to approximate the sparsest cut in such graphs to within a constant factor. 2) A constant-distortion embedding of outerplanar graphs into the restricted class of l/sub 1/-metrics known as "dominating tree metrics". We also show a lower bound of /spl Omega/(log n) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low tree width, and excludes the possibility of using them to explore the finer structure of l/sub 1/-embeddability.

Article Free Access Share on Communication-processor tradeoffs in limited resources PRAM Authors: Adnan Agbaria Technion, Haifa Technion, HaifaView Profile , Yosi Ben-Asher Haifa University Haifa UniversityView Profile , Ilan Newman Haifa University Haifa UniversityView Profile Authors Info & Claims SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architecturesJune 1999 Pages 74–82https://doi.org/10.1145/305619.305628Published:01 June 1999Publication History 2citation240DownloadsMetricsTotal Citations2Total Downloads240Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

It is well known that the optimal solution for searching in a finite total order set is binary search. In binary search we divide the set into two "halves" by querying the middle element and continue the search on the suitable half. What is the equivalent of binary search when the set P is partially ordered? A query in this case is to a point $x\in P$, with two possible answers: "yes" indicates that the required element is "below" x or "no" if the element is not below x. We show that the problem of computing an optimal strategy for search in posets that are tree-like (or forests) is polynomial in the size of the tree and requires at most O(n 4 log 3 n ) steps. Optimal solutions of such search problems are often needed in program testing and debugging, where a given program is represented as a tree and a bug should be found using a minimal set of queries. This type of search is also applicable in searching classified large tree-like databases (e.g., the Internet).

In this paper we introduce the MULTI_SERVICE model of network communication. This model attempts to capture recent communication technology trends, such as aspects of quality-of-service and their relation to the emerging technology of automatic pricing, e.g. for Internet services. The MULTI_SERVICE model differs from related models by taking communication and service activation time into account, thus restricting parallelism to better fit reality. Thus, our model extends and refines previous successful models for network communication. We consider the application of this model to communication problems, where the services are certain communication media or connection providers, with respective pricing policies. We give some insights and an algorithm for optimal dissemination of information in this model when given a fixed, limited budget.

) Ilan Newman and Mario Szegedy y Abstract We study 1-round two parties communication complexity games, where private random bits are used. We observe that the existence of good protocols for such games is related to a notion of approximating the matrix that represents the function by a certain low rank matrix. This gives rise to a new notion of rank, analogous of positive rank for 1-round communication complexity. We prove that the identity matrix is non approximable by low rank matrices in this sense. As a corollary we prove that any randomized protocol for the equality function requires \\Omega\\Gamma p n) complexity in the 1-round, private bits model, answering an open question raised by Yao [8]. A corollary is an answer to the following graph theoretic question: Assume a graph on n vertices has a set of N = N (n) cliques and so that for each two different cliques of this set, the number of edges between them is at most 0.1 of the product of their sizes. How large can N be ? ...

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the gaffs between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. An interesting connection of this model to the complexity of resolution proofs is also mentioned.

Körner defined the notion of graph entropy. He used it to simplify the proof of the Fredman–Komlos lower bound for the family size of perfect hash functions. We use this information-theoretic notion to obtain a general method for formula size lower bounds. This method can be applied to low-complexity functions for which the other known general methods do not apply.

We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n/spl times/n Mesh: 7n+o(n) steps; 2/sup n/ hypercube: O(n/sup 2/) steps; n/spl times/n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2/sup n/-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2/sup n/) steps.

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the CNF search problem is complete for all the variants of decision trees. It is then shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. The special case of nondeterministic complexity is discussed. >

Abstract We consider the problem of covering a weighted graph G = (V, E) by a set of vertex‐disjoint paths, such that the total weight of these paths is maximized. This problem is clearly NP‐complete, since it contains the Hamiltonian path problem as a special case. Three approximation algorithms for this problem are presented, exhibiting a complexity‐performance trade‐off. First, we develop an algorithm for covering undirected graphs. The time complexity of this algorithm is O(|E|log|E|), and its performance‐ratio is ½. Second, we present an algorithm for covering undirected graphs, whose performance‐ratio is ⅔. This algorithm uses a maximum weight matching algorithm as a subroutine, which dominates the overall complexity of our algorithm. Finally, we develop an algorithm for covering directed graphs, whose performanceratio is ⅔. This algorithm uses a maximum weight bipartite matching algorithm as a subroutine, which dominates the overall complexity of the algorithm.