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 .
Ortho Flint, Asanka Wickramasinghe, Jason Brasse, Christopher Fowler
2019-03-24
In this paper, we provide a polynomial time (and space), algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies.
Miklós Z. Rácz, Benjamin Schiffer
2019-03-28
We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let
be a random graph on vertices with a planted clique of size . We show that no algorithm that makes at most adaptive queries to the adjacency matrix of is likely to find the planted clique. On the other hand, when there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making adaptive queries. For detection, the additive term is not necessary: the number of queries needed to detect the presence of a planted clique is (up to logarithmic factors).
Stefan Klootwijk, Bodo Manthey
2019-03-28
The facility location problem is an NP-hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. Such algorithms often perform much better than worst-case analysis suggests. Therefore, probabilistic analysis is a widely used tool to analyze such algorithms. Most research on probabilistic analysis of NP-hard optimization problems involving metric spaces, such as the facility location problem, has been focused on Euclidean instances, and also instances with independent (random) edge lengths, which are non-metric, have been researched. We would like to extend this knowledge to other, more general, metrics. We investigate the facility location problem using random shortest path metrics. We analyze some probabilistic properties for a simple greedy heuristic which gives a solution to the facility location problem: opening the
cheapest facilities (with only depending on the facility opening costs). If the facility opening costs are such that is not too large, then we show that this heuristic is asymptotically optimal. On the other hand, for large values of , the analysis becomes more difficult, and we provide a closed-form expression as upper bound for the expected approximation ratio. In the special case where all facility opening costs are equal this closed-form expression reduces to or or even if the opening costs are sufficiently small.
Zeke Wang, Kaan Kara, Hantian Zhang, Gustavo Alonso, Onur Mutlu, Ce Zhang
2019-03-08
Learning from the data stored in a database is an important function increasingly available in relational engines. Methods using lower precision input data are of special interest given their overall higher efficiency but, in databases, these methods have a hidden cost: the quantization of the real value into a smaller number is an expensive step. To address the issue, in this paper we present MLWeaving, a data structure and hardware acceleration technique intended to speed up learning of generalized linear models in databases. ML-Weaving provides a compact, in-memory representation enabling the retrieval of data at any level of precision. MLWeaving also takes advantage of the increasing availability of FPGA-based accelerators to provide a highly efficient implementation of stochastic gradient descent. The solution adopted in MLWeaving is more efficient than existing designs in terms of space (since it can process any resolution on the same design) and resources (via the use of bit-serial multipliers). MLWeaving also enables the runtime tuning of precision, instead of a fixed precision level during the training. We illustrate this using a simple, dynamic precision schedule. Experimental results show MLWeaving achieves up to16 performance improvement over low-precision CPU implementations of first-order methods.
Surender Baswana, Shiv Kumar Gupta, Ayush Tulsyan
2018-10-03
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time, and still achieves better time complexity. This algorithm also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.
Adrien Chan-Hon-Tong
2019-01-22
This short paper presents an algorithm which aims to solve generic linear program (
or ) using simple projections and call to a sub solver dedicated to linear feasibility ( ), recently, proven to be a strongly polynomial problem thank to Chubanov algorithm. Then, a complexity analysis states that this algorithm is strongly polynomial in not degenerated cases. Despite surely containing faults, this complexity analysis and this linear feasibility based algorithm call for a discussion.
