David Gamarnik, Ilias Zadik
2019-04-15
In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size
is planted in an Erdos Renyi graph resulting in a graph . The goal is to recover the planted clique vertices by observing . It is known that the clique can be recovered as long as for any , but no polynomial-time algorithm is known for this task unless . Following a statistical-physics inspired point of view as an attempt to understand this computational-statistical gap, we study the landscape of the "sufficiently dense" subgraphs of and their overlap with the planted clique. Using the first moment method, we study the densest subgraph problems for subgraphs with fixed, but arbitrary, overlap size with the planted clique, and provide evidence of a phase transition for the presence of Overlap Gap Property (OGP) at . OGP is a concept introduced originally in spin glass theory and known to suggest algorithmic hardness when it appears. We establish the presence of OGP when is a small positive power of by using a conditional second moment method. As our main technical tool, we establish the first, to the best of our knowledge, concentration results for the -densest subgraph problem for the Erdos-Renyi model when for arbitrary . Finally, to study the OGP we employ a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization.
Yossi Azar, Noam Touitou
2019-04-15
In this paper, we present a framework used to construct and analyze algorithms for online optimization problems with deadlines or with delay over a metric space. Using this framework, we present algorithms for several different problems. We present an
-competitive deterministic algorithm for online multilevel aggregation with delay on a tree of depth , an exponential improvement over the -competitive algorithm of Bienkowski et al. (ESA '16), where the only previously-known improvement was for the special case of deadlines by Buchbinder et al. (SODA '17). We also present an -competitive randomized algorithm for online service with delay over any general metric space of points, improving upon the -competitive algorithm by Azar et al. (STOC '17). In addition, we present the problem of online facility location with deadlines. In this problem, requests arrive over time in a metric space, and need to be served until their deadlines by facilities that are opened momentarily for some cost. We also consider the problem of facility location with delay, in which the deadlines are replaced with arbitrary delay functions. For those problems, we present -competitive algorithms, with the number of points in the metric space. The algorithmic framework we present includes techniques for the design of algorithms as well as techniques for their analysis.
Shunsuke Inenaga
2019-04-09
The suffix tree, DAWG, and CDAWG are fundamental indexing structures of a string, with a number of applications in bioinformatics, information retrieval, data mining, etc. An edge-labeled rooted tree (trie) is a natural generalization of a string. Breslauer [TCS 191(1-2): 131-144, 1998] proposed the suffix tree for a backward trie, where the strings in the trie are read in the leaf-to-root direction. In contrast to a backward trie, we call a usual trie as a forward trie. Despite a few follow-up works after Breslauer's paper, indexing forward/backward tries is not well understood yet. In this paper, we show a full perspective on the sizes of indexing structures such as suffix trees, DAWGs, and CDAWGs for forward and backward tries. In particular, we show that the size of the DAWG for a forward trie with
nodes is , where is the number of distinct characters in the trie. This becomes for a large alphabet. Still we show that there is a compact -space representation of the DAWG for a forward trie over any alphabet, and present an -time -space algorithm to construct such a representation of the DAWG for a growing forward trie.
Tomasz Krawczyk
2019-04-09
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in circular-arc graphs and can be seen as their canonical representations; in particular, every intersection model can be easily transformed into a normalized one. Our work adapts and appropriately extends the previous work on the similar topic done by Hsu [\emph{SIAM J. Comput. 24(3), 411--439, (1995)}]. In his work, Hsu developed decomposition trees representing all normalized models of circular-arc graphs. However due to the counterexample given in [\emph{Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013}], his decomposition trees can not be used by algorithms testing isomorphism of circular-arc graphs.
Jacob Holm, Eva Rotenberg
2018-08-07
We present a data structure that, given a graph
of vertices and edges, and a suitable pair of nested -divisions of , preprocesses in time and handles any series of edge-deletions in total time while answering queries to pairwise biconnectivity in worst-case time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs.
Ronitt Rubinfeld, Arsen Vasilyan
2019-04-14
The noise sensitivity of a Boolean function
is one of its fundamental properties. A function of a positive noise parameter , it is denoted as . Here we study the algorithmic problem of approximating it for monotone , such that for constant , and where satisfies . For such and , we give a randomized algorithm performing queries and approximating to within a multiplicative factor of . Given the same constraints on and , we also prove a lower bound of on the query complexity of any algorithm that approximates to within any constant factor, where can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on . We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.
Chiranjib Bhattacharyya, Ravindran Kannan
2019-04-14
The core problem in many Latent Variable Models, widely used in Unsupervised Learning is to find a latent k-simplex K in Rd given perturbed points from it, many of which lie far outside the simplex. This problem was stated in [2] as an open problem. We address this problem under two deterministic assumptions which replace varied stochastic assumptions specific to relevant individual models. Our first contribution is to show that the convex hull K' of the averages of all delta n sized subsets of data points is close to K. We call this subset-smoothing. While K' can have exponentially many vertices, it is easily seen to have a polynomial time Optimization Oracle which in fact runs in time O(nnz(data)). This is the starting point for our algorithm. The algorithm is simple: it has k stages in each of which we use the oracle to find maximum of a carefully chosen linear function over K'; the optimal x is an approximation to a new vertex of K. The simplicity does not carry over to the proof of correctness. The proof is involved and uses existing and new tools from Numerical Analysis, especially angles between singular spaces of close-by matrices. However, the simplicity of the algorithm, especially the fact the only way we use the data is to do matrix-vector products leads to the claimed time bound. This matches the best known algorithms in the special cases and is better when the input is sparse as indeed is the case in many applications. Our algorithm applies to many special cases, including Topic Models, Approximate Non-negative Matrix factorization, Overlapping community Detection and Clustering.
Tingran Gao, Zhizhen Zhao
2019-01-24
We propose a novel formulation for phase synchronization -- the statistical problem of jointly estimating alignment angles from noisy pairwise comparisons -- as a nonconvex optimization problem that enforces consistency among the pairwise comparisons in multiple frequency channels. Inspired by harmonic retrieval in signal processing, we develop a simple yet efficient two-stage algorithm that leverages the multi-frequency information. We demonstrate in theory and practice that the proposed algorithm significantly outperforms state-of-the-art phase synchronization algorithms, at a mild computational costs incurred by using the extra frequency channels. We also extend our algorithmic framework to general synchronization problems over compact Lie groups.
Hans-Peter Deifel, Stefan Milius, Lutz Schröder, Thorsten Wißmann
2018-11-21
Partition refinement is a method for minimizing automata and transition systems of various types. Recently, we have developed a partition refinement algorithm that is generic in the transition type of the given system and matches the runtime of the best known algorithms for many concrete types of systems, e.g. deterministic automata as well as ordinary, weighted, and probabilistic (labelled) transition systems. Genericity is achieved by modelling transition types as endofunctors on sets, and systems as coalgebras. In the present work, we refine the runtime analysis of our algorithm to cover additional instances, notably weighted automata and, more generally, weighted tree automata. For weights in a cancellative monoid we match, and for non-cancellative monoids such as (the additive monoid of) the tropical semiring even substantially improve, the asymptotic runtime of the best known algorithms. We have implemented our algorithm in a generic tool that is easily instantiated to concrete system types by implementing a simple refinement interface. Moreover, the algorithm and the tool are modular, and partition refiners for new types of systems are obtained easily by composing pre-implemented basic functors. Experiments show that even for complex system types, the tool is able to handle systems with millions of transitions.
Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, Lars Rohwedder
2019-04-13
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor
: When an object of size arrives, the decisions for objects of total size at most may be revoked. Usually should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small ). We therefore resolve the competitiveness of the bin covering problem with migration.
