Simon Apers
2019-04-25
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as
, with the number of edges and the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for -connectivity, and (iii) it allows to create a superposition over the isomorphisms of an -node graph in time , surpassing the barrier set by index erasure.
S. M. Dhannya, N. S. Narayanaswamy
2018-12-04
Given a hypergraph
, the conflict-free colouring problem is to colour vertices of using minimum colours so that each hyperedge in sees a unique colour. We present a polynomial time reduction from the conflict-free colouring problem in hypergraphs to the maximum independent set problem in a class of simple graphs, which we refer to as \textit{conflict graphs}. We also present another characterization of the conflict-free colouring number in terms of the chromatic number of graphs in an associated family of simple graphs, which we refer to as \textit{co-occurrence graphs}. We present perfectness results for co-occurrence graphs and a special case of conflict graphs. Based on these results and a linear program that returns an integer solution in polynomial time, we obtain a polynomial time algorithm to compute a minimum conflict-free colouring of interval hypergraphs, thus solving an open problem due to Cheilaris et al.\cite{CPLGARSS2014}. Finally, we use the co-occurrence graph characterization to prove that for an interval hypergraph, the conflict-free colouring number is the minimum partition of its intervals into sets such that each set has an exact hitting set (a hitting set in which each interval is hit exactly once).
Matthias Bonne, Keren Censor-Hillel
2019-04-25
This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: \begin{itemize} \item The bandwidth complexity of
-round dynamic triangle detection or listing is . \item The bandwidth complexity of -round dynamic triangle membership listing is for node/edge deletions, for edge insertions, and for node insertions. \item The bandwidth complexity of -round dynamic triangle membership detection is for node/edge deletions, for edge insertions, and for node insertions. \end{itemize} Most of our upper and lower bounds are \emph{tight}. Additionally, we provide almost always tight upper and lower bounds for larger cliques.
Markus Wilhelm Jahn, Patrick Erik Bradley
2019-04-16
In order to be able to process the increasing amount of spatial data, efficient methods for their handling need to be developed. One major challenge for big spatial data is access. This can be achieved through space-filling curves, as they have the property that nearby points on the curve are also nearby in space. They are able to handle higher dimensional data, too. Higher dimensional data is widely used e.g. in CityGML and is becoming more and more important. In a laboratory experiment on a tropical rain forest tree data set of 2.5 million points taken from an 18-dimensional space, it is demonstrated that the recently constructed scaled Gray-Hilbert curve index performs better than its standard static version, saving a significant amount of space for a projection of the data set onto 8 attributes. The implementation is based on a binary tree in a data-driven process, in a similar way as e.g. the R-tree. Its scalability allows the handling of different kinds of data distributions which are reflected in the tree structure of the index. The relative efficiency of the scaled Gray-Hilbert curve in comparison with the best static version is seen to depend on the distribution of the point cloud. A local sparsity measure derived from properties of the corresponding trees can distinguish point clouds with different tail distributions. The different resulting binary trees are visualised to illustrate the influences of the different tail distributions they have been built on.
Vitaly Aksenov Dan Alistarh Petr Kuznetsov
2019-04-25
A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected with locks. A lock can be viewed as a queue that arbitrates the order in which the critical sections are executed, and a natural question is whether we can use stochastic analysis to predict the resulting throughput. As a preliminary evidence to the affirmative, we describe a simple model that can be used to predict the throughput of coarse-grained lock-based algorithms. We show that our model works well for CLH lock, and we expect it to work for other popular lock designs such as TTAS, MCS, etc.
Markus Blumenstock, Frank Fischer
2018-11-16
The arboricity of a graph is the minimum number of forests it can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition, as they operate on the related pseudoforest partitions or the dual problem. We propose an algorithm for converting a partition of
pseudoforests into a partition of forests in time, where is the inverse Ackermann function, when expected time is allowed for pre-computation of a perfect hash function. Without perfect hashing, we obtain with a data structure by Brodal and Fagerberg that stores graphs of arboricity . For every fixed , the latter result implies a constructive -approximation algorithm with runtime by using Kowalik's approximation scheme for pseudoforest partitions. Our algorithm might help in designing a faster exact arboricity algorithm. We also make several remarks on approximation algorithms for the pseudoarboricity and the equivalent graph orientations with smallest maximum indegree, and correct some mistakes made in the literature.
Jesper Nederlof
2019-04-25
We present an algorithm that takes as input an
-vertex planar graph and a -vertex pattern graph , and computes the number of (induced) copies of in in time. If is a matching, independent set, or connected bounded maximum degree graph, the runtime reduces to . While our algorithm counts all copies of , it also improves the fastest algorithms that only detect copies of . Before our work, no time algorithms for detecting unrestricted patterns were known, and by a result of Bodlaender et al. [ICALP 2016] a time algorithm would violate the Exponential Time Hypothesis (ETH). Furthermore, it was only known how to detect copies of a fixed connected bounded maximum degree pattern in time probabilistically. For counting problems, it was a repeatedly asked open question whether time algorithms exist that count even special patterns such as independent sets, matchings and paths in planar graphs. The above results resolve this question in a strong sense by giving algorithms for counting versions of problems with running times equal to the ETH lower bounds for their decision versions. Generally speaking, our algorithm counts copies of in time proportional to its number of non-isomorphic separations of order . The algorithm introduces a new recursive approach to construct families of balanced cycle separators in planar graphs that have limited overlap inspired by methods from Fomin et al. [FOCS 2016], a new `efficient' inclusion-exclusion based argument and uses methods from Bodlaender et al. [ICALP 2016].
Michael Hopkins, Mantas Mikaitis, Dave R. Lester, Steve Furber
2019-04-25
Although double-precision floating-point arithmetic currently dominates high-performance computing, there is increasing interest in smaller and simpler arithmetic types. The main reasons are potential improvements in energy efficiency and memory footprint and bandwidth. However, simply switching to lower-precision types typically results in increased numerical errors. We investigate approaches to improving the accuracy of lower-precision arithmetic types, using examples in an important domain for numerical computation in neuroscience: the solution of Ordinary Differential Equations (ODEs). The Izhikevich neuron model is used to demonstrate that rounding has an important role in producing accurate spike timings from explicit ODE solution algorithms. In particular, stochastic rounding consistently results in smaller errors compared to single-precision floatingpoint and fixed-point arithmetic with round-tonearest across a range of neuron behaviours and ODE solvers. A computationally much cheaper alternative is also investigated, inspired by the concept of dither that is a widely understood mechanism for providing resolution below the LSB in digital signal processing. These results will have implications for the solution of ODEs in other subject areas, and should also be directly relevant to the huge range of practical problems that are represented by Partial Differential Equations (PDEs).
Falko Hegerfeld, Stefan Kratsch
2019-04-25
In the fundamental Maximum Matching problem the task is to find a maximum cardinality set of pairwise disjoint edges in a given undirected graph. The fastest algorithm for this problem, due to Micali and Vazirani, runs in time
and stands unbeaten since 1980. It is complemented by faster, often linear-time, algorithms for various special graph classes. Moreover, there are fast parameterized algorithms, e.g., time relative to tree-width , which outperform when the parameter is sufficiently small. We show that the Micali-Vazirani algorithm, and in fact any algorithm following the phase framework of Hopcroft and Karp, is adaptive to beneficial input structure. We exhibit several graph classes for which such algorithms run in linear time . More strongly, we show that they run in time for graphs that are vertex deletions away from any of several such classes, without explicitly computing an optimal or approximate deletion set; before, most such bounds were at least . Thus, any phase-based matching algorithm with linear-time phases obliviously interpolates between linear time for and the worst case of when . We complement our findings by proving that the phase framework by itself still allows phases, and hence time , even on paths, cographs, and bipartite chain graphs.
Leslie Ann Goldberg, Mark Jerrum
2018-10-13
In the Ising model, we consider the problem of estimating the covariance of the spins at two specified vertices. In the ferromagnetic case, it is easy to obtain an additive approximation to this covariance by repeatedly sampling from the relevant Gibbs distribution. However, we desire a multiplicative approximation, and it is not clear how to achieve this by sampling, given that the covariance can be exponentially small. Our main contribution is a fully polynomial time randomised approximation scheme (FPRAS) for the covariance. We also show that that the restriction to the ferromagnetic case is essential --- there is no FPRAS for multiplicatively estimating the covariance of an antiferromagnetic Ising model unless RP = #P. In fact, we show that even determining the sign of the covariance is #P-hard in the antiferromagnetic case.
