More Like this

1. Testing Intersecting and Union-Closed Families

   https://doi.org/10.4230/LIPICS.ITCS.2024.33  

   Chen, Xi; De, Anindya; Li, Yuhao; Nadimpalli, Shivam; Servedio, Rocco A (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically intersecting families and union-closed families. A function f: {0,1}ⁿ → {0,1} is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed family) of subsets of [n]. Our main results are that - in sharp contrast with the property of being a monotone set system - the property of being an intersecting set system, and the property of being a union-closed set system, both turn out to be information-theoretically difficult to test. We show that: - For ε ≥ Ω(1/√n), any non-adaptive two-sided ε-tester for intersectingness must make 2^{Ω(n^{1/4}/√{ε})} queries. We also give a 2^{Ω(√{n log(1/ε)})}-query lower bound for non-adaptive one-sided ε-testers for intersectingness. - For ε ≥ 1/2^{Ω(n^{0.49})}, any non-adaptive two-sided ε-tester for union-closedness must make n^{Ω(log(1/ε))} queries. Thus, neither intersectingness nor union-closedness shares the poly(n,1/ε)-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple poly(n^{√{nlog(1/ε)}},1/ε)-query, one-sided, non-adaptive algorithm for ε-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when ε = Θ(1/√n), and for one-sided testing of intersectingness when ε = Θ(1). 

   more » « less
2. Approximating the Distance to Monotonicity of Boolean Functions

   https://doi.org/10.1137/1.9781611975994.123  

   Pallavoor, Ramesh Krishnan; Raskhodnikova, Sofya; Waingarten, Erik (January 2020, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020)

   We design a nonadaptive algorithm that, given a Boolean function f: {0, 1}^n → {0, 1} which is α-far from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an O-tilde(\sqrt{n})-approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n^(1/2−k)-factor requires 2^{n^k} nonadaptive queries, thereby ruling out a poly(n, 1/α)-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with O-tilde(n/ε^2) queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is ε-far from having the property. Our method yields the same lower bounds for unateness and being a k-junta. These lower bounds improve exponentially on the existing lower bounds for these properties. 

   more » « less
3. Search-To-Decision Reductions for Kolmogorov Complexity

   https://doi.org/10.4230/lipics.ccc.2024.34  

   Mazor, Noam; Pass, Rafael (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   {"Abstract":["A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-t program generating a given string x is at most s.\r\nIn this work, we consider the more "robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound s and a running time bound t, the goal is to determine whether there exists a poly(t,|x|)-time program of length s+O(log |x|) that generates x. We present the first non-trivial search-to-decision reduction R for the GapMINKT problem; R has a running-time bound of 2^{ε n} for any ε > 0 and additionally only queries its oracle on "thresholds" s of size s+O(log |x|). As such, we get that any algorithm with running-time (resp. circuit size) 2^{α s} poly(|x|,t,s) for solving GapMINKT (given an instance (x,t,s), yields an algorithm for finding a witness with running-time (resp. circuit size) 2^{(α+ε) s} poly(|x|,t,s).\r\nOur second result is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.\r\nA central component in both of these results is the use of Kolmogorov and Levin’s Symmetry of Information Theorem."]} 

   more » « less
4. Agnostic Proper Learning of Monotone Functions: Beyond the Black-box Correction Barrier

   https://doi.org/10.1109/FOCS57990.2023.00068  

   Lange, Jane; Vasilyan, Arsen (November 2023, 64th IEEE Symposium on Foundations of Computer Science, FOCS 2023)

   We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given 2O~(n√/ε) uniformly random examples of an unknown function f:{±1}n→{±1}, our algorithm outputs a hypothesis g:{±1}n→{±1} that is monotone and (opt +ε)-close to f, where opt is the distance from f to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also 2O~(n√/ε), nearly matching the lower bound of [13]. We also give an algorithm for estimating up to additive error ε the distance of an unknown function f to monotone using a run-time of 2O~(n√/ε). Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity.This work builds upon the improper learning algorithm of [17] and the proper semiagnostic learning algorithm of [40], which obtains a non-monotone Boolean-valued hypothesis, then “corrects” it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than 2 opt +ε information-theoretically; we bypass this barrier bya)augmenting the improper learner with a convex optimization step, andb)learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the “poset sorting” problem of [40] for functions over general posets with non-Boolean labels. 

   more » « less
5. Fully Functional Parameterized Suffix Trees in Compact Space

   Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V. (June 2022, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022))

   Mikolaj Bojanczyk; Emanuela Merelli; David P. Woodruff (Ed.)

   Two equal length strings are a parameterized match (p-match) iff there exists a one-to-one function that renames the symbols in one string to those in the other. The Parameterized Suffix Tree (PST) [Baker, STOC' 93] is a fundamental data structure that handles various string matching problems under this setting. The PST of a text T[1,n] over an alphabet Σ of size σ takes O(nlog n) bits of space. It can report any entry in (parameterized) (i) suffix array, (ii) inverse suffix array, and (iii) longest common prefix (LCP) array in O(1) time. Given any pattern P as a query, a position i in T is an occurrence iff T[i,i+|P|-1] and P are a p-match. The PST can count the number of occurrences of P in T in time O(|P|log σ) and then report each occurrence in time proportional to that of accessing a suffix array entry. An important question is, can we obtain a compressed version of PST that takes space close to the text’s size of nlogσ bits and still support all three functionalities mentioned earlier? In SODA' 17, Ganguly et al. answered this question partially by presenting an O(nlogσ) bit index that can support (parameterized) suffix array and inverse suffix array operations in O(log n) time. However, the compression of the (parameterized) LCP array and the possibility of faster suffix array and inverse suffix array queries in compact space were left open. In this work, we obtain a compact representation of the (parameterized) LCP array. With this result, in conjunction with three new (parameterized) suffix array representations, we obtain the first set of PST representations in o(nlog n) bits (when logσ = o(log n)) as follows. Here ε > 0 is an arbitrarily small constant. - Space O(n logσ) bits and query time O(log_σ^ε n); - Space O(n logσlog log_σ n) bits and query time O(log log_σ n); and - Space O(n logσ log^ε_σ n) bits and query time O(1). The first trade-off is an improvement over Ganguly et al.’s result, whereas our third trade-off matches the optimal time performance of Baker’s PST while squeezing the space by a factor roughly log_σ n. We highlight that our trade-offs match the space-and-time bounds of the best-known compressed text indexes for exact pattern matching and further improvement is highly unlikely. 

   more » « less