Nikolaj Tatti
2019-02-05
Interactions in many real-world phenomena can be explained by a strong hierarchical structure. Typically, this structure or ranking is not known; instead we only have observed outcomes of the interactions, and the goal is to infer the hierarchy from these observations. Discovering a hierarchy in the context of directed networks can be formulated as follows: given a graph, partition vertices into levels such that, ideally, there are only edges from upper levels to lower levels. The ideal case can only happen if the graph is acyclic. Consequently, in practice we have to introduce a penalty function that penalizes edges violating the hierarchy. A practical variant for such penalty is agony, where each violating edge is penalized based on the severity of the violation. Hierarchy minimizing agony can be discovered in
time, and much faster in practice. In this paper we introduce several extensions to agony. We extend the definition for weighted graphs and allow a cardinality constraint that limits the number of levels. While, these are conceptually trivial extensions, current algorithms cannot handle them, nor they can be easily extended. We solve the problem by showing the connection to the capacitated circulation problem, and we demonstrate that we can compute the exact solution fast in practice for large datasets. We also introduce a provably fast heuristic algorithm that produces rankings with competitive scores. In addition, we show that we can compute agony in polynomial time for any convex penalty, and, to complete the picture, we show that minimizing hierarchy with any concave penalty is an NP-hard problem.
Jakub Radoszewski, Tatiana Starikovskaya
2016-07-19
We present a new streaming algorithm for the
-Mismatch problem, one of the most basic problems in pattern matching. Given a pattern and a text, the task is to find all substrings of the text that are at the Hamming distance at most from the pattern. Our algorithm is enhanced with an important new feature called Error Correcting, and its complexities for and for a general are comparable to those of the solutions for the -Mismatch problem by Porat and Porat (FOCS 2009) and Clifford et al. (SODA 2016). In parallel to our research, a yet more efficient algorithm for the -Mismatch problem with the Error Correcting feature was developed by Clifford et al. (SODA 2019). Using the new feature and recent work on streaming Multiple Pattern Matching we develop a series of streaming algorithms for pattern matching on weighted strings, which are a commonly used representation of uncertain sequences in molecular biology. We also show that these algorithms are space-optimal up to polylog factors. A preliminary version of this work was published at DCC 2017 conference.
Yuval Emek, Fanica Gavril, Shay Kutten, Mordechai Shalom, Shmuel Zaks
2019-04-23
A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be concurrently scheduled, provided that there are at most
requests that pass through any given edge of the network. In this work we consider the problem of finding the largest number of given subtrees of a tree that satisfy given load constraints. This is an extension of the problem of finding a largest induced -colorable subgraph of a chordal graph (which is the intersection graph of subtrees of a tree). We extend a greedy algorithm that solves the latter problem for interval graphs, and obtain an -approximation for chordal graphs where is the maximum number of leaves of the subtrees in the representation of the chordal graph. This implies a 2-approximation for \textsc{Vpt}} graphs (vertex-intersection graphs of paths in a tree), and an optimal algorithm for the class of directed path graphs (vertex-intersection graphs of paths in a directed tree) which in turn extends the class of interval graphs. In fact, we consider a more general problem that is defined on the subtrees of the representation of chordal graphs, in which we allow any set of different bounds on the vertices and edges. Thus our algorithm generalizes the known one in two directions: first, it applies to more general graph classes, and second, it does not require the same bound for all the edges (of the representation). Last, we present a polynomial-time algorithm for the general problem where instances are restricted to paths in a star.
Yuval Emek, Shay Kutten, Mordechai Shalom, Shmuel Zaks
2019-04-23
A matching of a graph is a subset of edges no two of which share a common vertex, and a maximum matching is a matching of maximum cardinality. In a
-matching every vertex has an associated bound , and a maximum -matching is a maximum set of edges, such that every vertex appears in at most of them. We study an extension of this problem, termed {\em Hierarchical b-Matching}. In this extension, the vertices are arranged in a hierarchical manner. At the first level the vertices are partitioned into disjoint subsets, with a given bound for each subset. At the second level the set of these subsets is again partitioned into disjoint subsets, with a given bound for each subset, and so on. In an {\em Hierarchical b-matching} we look for a maximum set of edges, that will obey all bounds (that is, no vertex participates in more than edges, then all the vertices in one subset do not participate in more that that subset's bound of edges, and so on hierarchically). We propose a polynomial-time algorithm for this new problem, that works for any number of levels of this hierarchical structure.
Adil Erzin, Natalya Lagutkina
2018-11-26
In this paper, we consider a problem of covering a straight line segment by equal circles that are initially arbitrarily placed on a plane by moving their centers on a segment or on a straight line containing a segment so that the segment is completely covered, the neighboring circles in the cover are touching each other and the total length of the paths traveled by circles is minimal. The complexity status of the problem is not known. We propose a
--time FPTAS for this problem, where is the number of circles and is arbitrarily small real.
Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu
2017-10-06
We give two quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with
constraint matrices, each of dimension , rank at most , and sparsity . The first algorithm assumes access to an oracle to the matrices at unit cost. We show that it has run time , with the error of the solution. This gives an optimal dependence in terms of and quadratic improvement over previous quantum algorithms when . The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is , with an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in and polynomially in . We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given measurements and a supply of copies of an unknown state with rank at most , we show we can find in time a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as on the measurements, up to error . The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest.
Cícero A. de Lima
2019-02-18
A hamiltonian sequence is a path walk
that can be a hamiltonian path or hamiltonian circuit. Determining whether such hamiltonian sequence exists in a given graph \G is a NP-Complete problem. In this paper, a novel algorithm for hamiltonian sequence problem is proposed. The proposed algorithm assumes that has potential forbidden minors that prevent a potential hamiltonian sequence from being a hamiltonian sequence. The algorithm's goal is to degenerate such potential forbidden minors in a two-phrase process. In first phrase, the algorithm passes through in order to construct a potential hamiltonian sequence with the aim of degenerating these potential forbidden minors. The algorithm, in turn, tries to reconstruct in second phrase by using a goal-oriented approach.
Nader H. Bshouty
2019-04-22
We give improved and almost optimal testers for several classes of Boolean functions on
inputs that have concise representation in the uniform and distribution-free model. Classes, such as -junta, -linear functions, -term DNF, -term monotone DNF, -DNF, decision list, -decision list, size- decision tree, size- Boolean formula, size- branching programs, -sparse polynomials over the binary field and function with Fourier degree at most . The method can be extended to several other classes of functions over any domain that can be approximated by functions that have a small number of relevant variables.
Cameron Musco, Christopher Musco, David P. Woodruff
2019-04-22
In low-rank approximation with missing entries, given
and binary , the goal is to find a rank- matrix for which: cost(L)=\sum_{i=1}^{n} \sum_{j=1}^{n}W_{i,j}\cdot (A_{i,j} - L_{i,j})^2\le OPT+\epsilon |A|_F^2, where . This problem is also known as matrix completion and, depending on the choice of , captures low-rank plus diagonal decomposition, robust PCA, low-rank recovery from monotone missing data, and a number of other important problems. Many of these problems are NP-hard, and while algorithms with provable guarantees are known in some cases, they either 1) run in time , or 2) make strong assumptions, e.g., that is incoherent or that is random. In this work, we consider , which output with rank . We prove that a common heuristic, which simply sets to where is , and then computes a standard low-rank approximation, achieves the above approximation bound with rank depending on the of . Namely, interpreting as the communication matrix of a Boolean function with , it suffices to set , where is the randomized communication complexity of with -sided error probability . For many problems, this yields bicriteria algorithms with . We prove a similar bound using the randomized communication complexity with -sided error. Further, we show that different models of communication yield algorithms for natural variants of the problem. E.g., multi-player communication complexity connects to tensor decomposition and non-deterministic communication complexity to Boolean low-rank factorization.
Penghui Yao
2019-04-18
This paper initiates the study of a class of entangled-games, mono-state games, denoted by
, where is a two-player one-round game and is a bipartite state independent of the game . In the mono-state game , the players are only allowed to share arbitrary copies of . This paper provides a doubly exponential upper bound on the copies of for the players to approximate the value of the game to an arbitrarily small constant precision for any mono-state binary game , if is a noisy EPR state, which is a two-qubit state with completely mixed states as marginals and maximal correlation less than . In particular, it includes , an EPR state with an arbitrary depolarizing noise . This paper develops a series of new techniques about the Fourier analysis on matrix spaces and proves a quantum invariance principle and a hypercontractive inequality of random operators. The structure of the proofs is built the recent framework about the decidability of the non-interactive simulation of joint distributions, which is completely different from all previous optimization-based approaches or "Tsirelson's problem"-based approaches. This novel approach provides a new angle to study the decidability of the complexity class MIP , a longstanding open problem in quantum complexity theory.
