Brahim Chaourar
2019-03-29
Given a graph
, a connected cut is the set of edges of E linking all vertices of U to all vertices of such that the induced subgraphs and are connected. Given a positive weight function defined on , the connected maximum cut problem (CMAX CUT) is to find a connected cut such that is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs. In this paper, we prove that CMAX CUT is polynomial for graphs without as a minor. We deduce a quadratic time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.
Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang
2018-11-12
Neural networks have great success in many machine learning applications, but the fundamental learning theory behind them remains largely unsolved. Learning neural networks is NP-hard, but in practice, simple algorithms like stochastic gradient descent (SGD) often produce good solutions. Moreover, it is observed that overparameterization (that is, designing networks whose number of parameters is larger than statistically needed to perfectly fit the training data) improves both optimization and generalization, appearing to contradict traditional learning theory. In this work, we prove that using overparameterized neural networks with rectified linear units, one can (improperly) learn some notable hypothesis classes, including two and three-layer neural networks with fewer parameters and smooth activations. Moreover, the learning process can be simply done by SGD or its variants in polynomial time using polynomially many samples. We also show that for a fixed sample size, the population risk of the solution found by some SGD variant can be made almost independent of the number of parameters in the overparameterized network.
Igor Nesiolovskiy, Artem Nesiolovskiy
2019-03-29
We offer multiplication method for factoring big natural numbers which extends the group of the Fermat's and Lehman's factorization algorithms and has run-time complexity
. This paper is argued the finiteness of proposed algorithm depending on the value of the factorizable number n. We provide here comparative tests results of related algorithms on a large amount of computational checks. We describe identified advantages of the proposed algorithm over others. The possibilities of algorithm optimization for reducing the complexity of factorization are also shown here.
Efstratios Rappos, Stephan Robert, Philippe Cudré-Mauroux
2019-03-29
We present a novel algorithm to match GPS trajectories onto maps offline (in batch mode) using techniques borrowed from the field of force-directed graph drawing. We consider a simulated physical system where each GPS trajectory is attracted or repelled by the underlying road network via electrical-like forces. We let the system evolve under the action of these physical forces such that individual trajectories are attracted towards candidate roads to obtain a map matching path. Our approach has several advantages compared to traditional, routing-based, algorithms for map matching, including the ability to account for noise and to avoid large detours due to outliers in the data whilst taking into account the underlying topological restrictions (such as one-way roads). Our empirical evaluation using real GPS traces shows that our method produces better map matching results compared to alternative offline map matching algorithms on average, especially for routes in dense, urban areas.
Rayan Chikhi, Jan Holub, Paul Medvedev
2019-03-29
The analysis of biological sequencing data has been one of the biggest applications of string algorithms. The approaches used in many such applications are based on the analysis of k-mers, which are short fixed-length strings present in a dataset. While these approaches are rather diverse, storing and querying k-mer sets has emerged as a shared underlying component. Sets of k-mers have unique features and applications that, over the last ten years, have resulted in many specialized approaches for their representation. In this survey, we give a unified presentation and comparison of the data structures that have been proposed to store and query k-mer sets. We hope this survey will not only serve as a resource for researchers in the field but also make the area more accessible to outsiders
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri
2019-03-28
Graph sketching has emerged as a powerful technique for processing massive graphs that change over time (i.e., are presented as a dynamic stream of edge updates) over the past few years, starting with the work of Ahn, Guha and McGregor (SODA'12) on graph connectivity via sketching. In this paper we consider the problem of designing spectral approximations to graphs, or spectral sparsifiers, using a small number of linear measurements, with the additional constraint that the sketches admit an efficient recovery scheme. Prior to our work, sketching algorithms were known with near optimal
space complexity, but time decoding (brute-force over all potential edges of the input graph), or with subquadratic time, but rather large space complexity (due to their reliance on a rather weak relation between connectivity and effective resistances). In this paper we first show how a simple relation between effective resistances and edge connectivity leads to an improved space and time algorithm, which we show is a natural barrier for connectivity based approaches. Our main result then gives the first algorithm that achieves subquadratic recovery time, i.e. avoids brute-force decoding, and at the same time nontrivially uses the effective resistance metric, achieving space and recovery time. Our main technical contribution is a novel method for `bucketing' vertices of the input graph into clusters that allows fast recovery of edges of high effective resistance: the buckets are formed by performing ball-carving on the input graph using (an approximation to) its effective resistance metric. We feel that this technique is likely to be of independent interest.
Michael Kapralov, Navid Nouri, Aaron Sidford, Jakab Tardos
2019-03-28
In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model. We provide a linear sketching based solution that given a stream of edge insertions and deletions to a
-node undirected graph, uses space, processes each update in time, and with high probability recovers a spectral sparsifier in time. Prior to our work, state of the art results either used near optimal space complexity, but brute-force recovery time [Kapralov et al.'14], or with subquadratic runtime, but polynomially suboptimal space complexity [Ahn et al.'14, Kapralov et al.'19]. Our main technical contribution is a novel method for `bucketing' vertices of the input graph into clusters that allows fast recovery of edges of sufficiently large effective resistance. Our algorithm first buckets vertices of the graph by performing ball-carving using (an approximation to) its effective resistance metric, and then recovers the high effective resistance edges from a sketched version of an electrical flow between vertices in a bucket, taking nearly linear time in the number of vertices overall. This process is performed at different geometric scales to recover a sample of edges with probabilities proportional to effective resistances and obtain an actual sparsifier of the input graph. This work provides both the first efficient -sparse recovery algorithm for graphs and new primitives for manipulating the effective resistance embedding of a graph, both of which we hope have further applications.
Shravas Rao
2019-03-28
Let
be an Fourier matrix over for some prime . We improve upon known lower bounds for the number of rows of that must be sampled so that the resulting matrix satisfies the restricted isometry property for -sparse vectors. This property states that is approximately for all -sparse vectors . In particular, if , we show that rows must be sampled to satisfy the restricted isometry property with constant probability.
Jarosław Błasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek
2019-03-28
We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that for a
Hadamard matrix, one cannot recover all -sparse vectors unless the number of subsampled rows is .
Ramin Yarinezhad, Seyed Naser Hashemi
2016-10-07
In this paper, we present two approximation algorithms for the directed multi-multiway cut and directed multicut problems. The so called region growing paradigm \cite{1} is modified and used for these two cut problems on directed graphs. By using this paradigm, we give for each problem an approximation algorithm such that both algorithms have the approximate factor
the same as the previous works done on these problems. However, the previous works need to solve linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.
