1,721,217 research outputs found
Finding Monotone Patterns in Sublinear Time, Adaptively
Get PDFWe investigate adaptive sublinear algorithms for finding monotone patterns in sequential data. Given fixed 2 ≤ k ∈ m N and ε > 0, consider the problem of finding a length-k increasing subsequence in a sequence f : [n] → ℝ, provided that f is ε-far from free of such subsequences. It was shown by Ben-Eliezer et al. [FOCS 2019] that the non-adaptive query complexity of the above task is Θ((log n)^⌊log₂ k⌋). In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes O(log n) queries. This is optimal, matching the classical Ω(log n) adaptive lower bound by Fischer [Inf. Comp. 2004] for monotonicity testing (which corresponds to the case k = 2). Equivalently, our result implies that testing whether a sequence decomposes into k monotone subsequences can be done with O(log n) queries
Guardians or Oppressors: the Israeli and Turkish Armies in neoliberal contexts
No full textIn this essay, Uri Ben-Eliezer recalls the centrality of the army in the Israeli state and offers two divergent interpretations of such a place in a neoliberal context. He draws a comparison with the role and place of the army in Turkey.Dans cet essai, Uri Ben-Eliezer rappelle le caractère central de l’institution militaire au sein de l’État d’Israël et apporte deux interprétations possibles d’une telle importance dans un contexte néolibéral. Il esquisse au passage une comparaison avec le rôle et la place de l’armée en Turquie
Testing Local Properties of Arrays
Get PDFWe study testing of local properties in one-dimensional and multi-dimensional arrays. A property of d-dimensional arrays f:[n]^d -> Sigma is k-local if it can be defined by a family of k x ... x k forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and submodularity are 2-local; convexity is (usually) 3-local; and many typical problems in computational biology and computer vision involve o(n)-local properties.
In this work, we present a generic approach to test all local properties of arrays over any finite (and not necessarily bounded size) alphabet. We show that any k-local property of d-dimensional arrays is testable by a simple canonical one-sided error non-adaptive epsilon-test, whose query complexity is O(epsilon^{-1}k log{(epsilon n)/k}) for d = 1 and O(c_d epsilon^{-1/d} k * n^{d-1}) for d > 1. The queries made by the canonical test constitute sphere-like structures of varying sizes, and are completely independent of the property and the alphabet Sigma. The query complexity is optimal for a wide range of parameters: For d=1, this matches the query complexity of many previously investigated local properties, while for d > 1 we design and analyze new constructions of k-local properties whose one-sided non-adaptive query complexity matches our upper bounds. For some previously studied properties, our method provides the first known sublinear upper bound on the query complexity
Weisheit von Sirach
No full text"Ben Sira, wisdom of (also called Ecclesiasticus), a work of the Apocrypha, which, though usually known by this name, may have been called by its author, "The Words of Simeon b. Jeshua," the title found on the Hebrew fragments" (Encyc. Judaica, CD-Rom Ed., 1997)Erscheinungsjahr nach Vorlage: 279 [i.e. 1519]Ben Sira folgen noch eine Reihe anderer Abhandlungen cf. Steinschneider p. 203 No. 1363. Die wichtigsten NZ!Siehe auch Karl Heinz Burmeister, Sebastian Münster, in: Basler Beiträge zur Geschichtswissenschaft, Bd. 91, 1963, S. 8
Efficient Removal Lemmas for Matrices
No full textThe authors and Fischer recently proved that any hereditary property of two-dimensional matrices (where the row and column order is not ignored) over a finite alphabet is testable with a constant number of queries, by establishing an (ordered) matrix removal lemma, which states the following: If a matrix is far from satisfying some hereditary property, then a large enough constant-size random submatrix of it does not satisfy the property with probability at least 9/10. Here being far from the property means that one needs to modify a constant fraction of the entries of the matrix to make it satisfy the property.
However, in the above general removal lemma, the required size of the random submatrix grows very fast as a function of the distance of the matrix from satisfying the property. In this work we establish much more efficient removal lemmas for several special cases of the above problem. In particular, we show the following: If an epsilon-fraction of the entries of a binary matrix M can be covered by pairwise-disjoint copies of some (s x t) matrix A, then a delta-fraction of the (s x t)-submatrices of M are equal to A, where delta is polynomial in epsilon.
We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make progress towards proving one of their conjectures. The proofs combine their efficient conditional regularity lemma for matrices with additional combinatorial and probabilistic ideas
Earthmover Resilience and Testing in Ordered Structures
Get PDFOne of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem seems very difficult in general.
In this paper, we identify a wide class of properties of ordered structures - the earthmover resilient (ER) properties - and show that the "good behavior" of such properties allows us to obtain general testability results that are similar to (and more general than) those of unordered graphs. A property P is ER if, roughly speaking, slight changes in the order of the elements in an object satisfying P cannot make this object far from P. The class of ER properties includes, e.g., all unordered graph properties, many natural visual properties of images, such as convexity, and all hereditary properties of ordered graphs and images.
A special case of our results implies, building on a recent result of Alon and the authors, that the distance of a given image or ordered graph from any hereditary property can be estimated (with good probability) up to a constant additive error, using a constant number of queries
On the Instance Optimality of Detecting Collisions and Subgraphs
Get PDFSuppose you are given a function f: [n] → [n] via (black-box) query access to the function. You are looking to find something local, like a collision (a pair x ≠ y s.t. f(x) = f(y)). The question is whether knowing the "shape" of the function helps you or not (by shape we mean that some permutation of the function is known). Formally, we investigate the unlabeled instance optimality of substructure detection problems in graphs and functions. A problem is g(n)-instance optimal if it admits an algorithm A satisfying that for any possible input, the (randomized) query complexity of A is at most g(n) times larger than the query complexity of any algorithm A' which solves the same problem while holding an unlabeled copy of the input (i.e., any A' that "knows the structure of the input"). Our results point to a trichotomy of unlabeled instance optimality among substructure detection problems in graphs and functions:
- A few very simple properties have an O(1)-instance optimal algorithm.
- Most properties of graphs and functions, with examples such as containing a fixed point or a 3-collision in functions, or a triangle in graphs, are n^{c}-far from instance optimal for some constant c > 0.
- The problems of collision detection in functions and finding a claw in a graph serve as a middle ground between the two regimes. We show that these two properties are not Ω(log n)-instance optimal, and conjecture that this bound is tight. We provide evidence towards this conjecture, by proving that finding a claw in a graph is O(log(n))-instance optimal among all input graphs for which the query complexity of an algorithm holding an unlabeled certificate is O(√{n/(log n)})
Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
No full textAnalyzing multi-dimensional data is a fundamental problem in various areas of computer science. As the amount of data is often huge, it is desirable to obtain sublinear time algorithms to understand local properties of the data.
We focus on the natural problem of testing pattern freeness: given a large d-dimensional array A and a fixed d-dimensional pattern P over a finite alphabet Gamma, we say that A is P-free if it does not contain a copy of the forbidden pattern P as a consecutive subarray. The distance of A to P-freeness is the fraction of the entries of A that need to be modified to make it P-free.
For any epsilon > 0 and any large enough pattern P over any alphabet - other than a very small set of exceptional patterns - we design a tolerant tester that distinguishes between the case that the distance is at least epsilon and the case that the distance is at most a_d epsilon, with query complexity and running time c_d epsilon^{-1}, where a_d < 1 and c_d depend only on the dimension d. These testers only need to access uniformly random blocks of samples from the input A.
To analyze the testers we establish several combinatorial results, including the following d-dimensional modification lemma, which might be of independent interest: For any large enough d-dimensional pattern P over any alphabet (excluding a small set of exceptional patterns for the binary case), and any d-dimensional array A containing a copy of P, one can delete this copy by modifying one of its locations without creating new P-copies in A.
Our results address an open question of Fischer and Newman, who asked whether there exist efficient testers for properties related to tight substructures in multi-dimensional structured data
Mardoché ben Eliezer Comtiano. Éxplication des tables de Jezdedjerd.
No full textNumérisation effectuée à partir d'un document original.Mécénat : Numérisé en coopération avec la Bibliothèque nationale d'Israël et la Friedberg Jewish Manuscript Society dans le cadre du projet Ktiv.Colophon : נשלם פרוש ... מרדכי בכ"ר אליעזר כומטיינו נב"ת ע"י משה בכ"ר יוסף רביצי נ"ע בזמן שנת הרצ"
- …
