More Like this

1. Set Cover in Sub-linear Time

   Indyk, Piotr; Mahabadi, Sepideh; Rubinfeld, Ronitt; Vakilian, Ali; Yodpinyanee, Anak (January 2018, Annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in [17] to the sub-linear query model, that returns an α-approximate cover using Õ(m(n/k)^1/(α–1) + nk) queries to the input, where k denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of k, the required number of queries is , even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require Ω(nk) queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter k. On the other hand, we show that this bound is not optimal for larger values of the parameter k, as there exists a (1 + ε)-approximation algorithm with Õ(mn/kε^2) queries. We show that this bound is essentially tight for sufficiently small constant ε, by establishing a lower bound of query complexity. Our lower-bound results follow by carefully designing two distributions of instances that are hard to distinguish. In particular, our first lower bound involves a probabilistic construction of a certain set system with a minimum set cover of size αk, with the key property that a small number of “almost uniformly distributed” modifications can reduce the minimum set cover size down to k. Thus, these modifications are not detectable unless a large number of queries are asked. We believe that our probabilistic construction technique might find applications to lower bounds for other combinatorial optimization problems. 

   more » « less
2. Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

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

   Li, Xin (November 2023, IEEE)

   A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show that an asymptotically optimal construction of one central object will lead to asymptotically optimal solutions to all the others. However, despite considerable effort, previous works can get close but still lack one final step to achieve truly asymptotically optimal constructions. In this paper we provide the last missing link, thus simultaneously achieving explicit, asymptotically optimal constructions and solutions for various well studied extractors and applications, that have been the subjects of long lines of research. Our results include: 1. Asymptotically optimal seeded non-malleable extractors, which in turn give two source extractors for asymptotically optimal min-entropy of $$O(\log n)$$, explicit constructions of $$K$$-Ramsey graphs on $$N$$ vertices with $$K=\log^{O(1)} N$$, and truly optimal privacy amplification protocols with an active adversary. 2. Two source non-malleable extractors and affine non-malleable extractors for some linear min-entropy with exponentially small error, which in turn give the first explicit construction of non-malleable codes against $$2$$-split state tampering and affine tampering with constant rate and \emph{exponentially} small error. 3. Explicit extractors for affine sources, sumset sources, interleaved sources, and small space sources that achieve asymptotically optimal min-entropy of $$O(\log n)$ or $$2s+O(\log n)$$ (for space $$s$$ sources). 4. An explicit function that requires strongly linear read once branching programs of size $$2^{n-O(\log n)}$$, which is optimal up to the constant in $$O(\cdot)$$. Previously, even for standard read once branching programs, the best known size lower bound for an explicit function is $$2^{n-O(\log^2 n)}$$. 

   more » « less
3. On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols

   https://doi.org/10.1007/978-3-031-74580-5_8  

   Kuschner, Jordan; Shashwat, Yugarshi; Yadav, Sarthak; Chrobak, Marek (December 2024, Springer Nature Switzerland)

   Bramas, Quentin; Casteigts, Arnaud; Meeks, Kitty (Ed.)

   Selective families of sets, or selectors, are combinatorial tools used to “isolate” individual members of sets from some set family. Given a set X and an element x ∈ X, to isolate x from X, at least one of the sets in the selector must intersect X on exactly x. We study (k,N)-permutation selectors which have the property that they can isolate each element of each k-element subset of {0, 1, ..., N − 1} in each possible order. These selectors can be used in protocols for ad-hoc radio networks to more efficiently disseminate informa- tion along multiple hops. In 2004, Gasieniec, Radzik and Xin gave a construc- tion of a (k, N )-permutation selector of size O(k2 log3 N ). This paper improves this by providing a probabilistic construction of a (k, N )-permutation selector of size O(k2 log N ). Remarkably, this matches the asymptotic bound for standard strong (k,N)-selectors, that isolate each element of each set of size k, but with no restriction on the order. We then show that the use of our (k, N )-permutation selector improves the best running time for gossiping in ad-hoc radio networks by a poly-logarithmic factor. 

   more » « less
4. Explicit Time and Space Efficient Encoders Exist Only with Random Access

   https://doi.org/10.4230/LIPIcs.CCC.2024.5  

   Cook, Joshua; Moshkovitz, Dana (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time n^{1 + o(1)} and space polylog(n) provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [Divsalar et al., 1998] and the codes described in [Gál et al., 2013]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length. In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access. 

   more » « less
5. Global Transition-based Non-projective Dependency Parsing

   Gómez-Rodríguez, Carlos; Shi, Tianze; Lee, Lillian (July 2018, Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics)

   Shi, Huang, and Lee (2017) obtained state-of-the-art results for English and Chinese dependency parsing by combining dynamic-programming implementations of transition-based dependency parsers with a minimal set of bidirectional LSTM features. However, their results were limited to projective parsing. In this paper, we extend their approach to support non-projectivity by providing the first practical implementation of the MH4 algorithm, an O(n^4) mildly nonprojective dynamic-programming parser with very high coverage on non-projective treebanks. To make MH4 compatible with minimal transition-based feature sets, we introduce a transition-based interpretation of it in which parser items are mapped to sequences of transitions. We thus obtain the first implementation of global decoding for non-projective transition-based parsing, and demonstrate empirically that it is more effective than its projective counterpart in parsing a number of highly non-projective languages. 

   more » « less