Kevin Pratt
2018-07-17
Given nonnegative integers
and , where , what is the minimum number such that there exist linear forms so that is supported exactly on the set of all degree- multilinear monomials in ? We show that this and related questions have surprising and intimate connections to the areas of parameterized and exact algorithms, generalizing several well-known methods and providing a concrete approach to obtain faster approximate counting and deterministic decision algorithms. This gives a new application of Waring rank, a classical topic in algebraic geometry with connections to algebraic complexity theory, to computer science. To illustrate the amenability and utility of this approach, we give a randomized -time algorithm for computing a approximation of the sum of the coefficients of the multilinear monomials in a degree- homogeneous -variate polynomial with nonnegative coefficients. As an application of this we give a faster algorithm for approximately counting subgraphs of bounded treewidth, improving on earlier work of Alon et al. Along the way we give an exact answer to an open problem of Koutis and Williams and sharpen a lower bound on the size of perfectly balanced hash families given by Alon and Gutner.
Khaled Elbassioni
2019-04-04
A hypergraph
on vertices and edges is said to be {\it nearly-intersecting} if every edge of intersects all but at most polylogarthmically many (in and ) other edges. Given lists of colors , for each vertex , is said to be -(list) colorable, if each vertex can be assigned a color from its list such that no edge in is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in and .
Gautam Goel, Adam Wierman
2018-10-23
We consider Online Convex Optimization (OCO) in the setting where the costs are
-strongly convex and the online learner pays a switching cost for changing decisions between rounds. We show that the recently proposed Online Balanced Descent (OBD) algorithm is constant competitive in this setting, with competitive ratio , irrespective of the ambient dimension. Additionally, we show that when the sequence of cost functions is -smooth, OBD has near-optimal dynamic regret and maintains strong per-round accuracy. We demonstrate the generality of our approach by showing that the OBD framework can be used to construct competitive algorithms for a variety of online problems across learning and control, including online variants of ridge regression, logistic regression, maximum likelihood estimation, and LQR control.
Yan-Chao Wang, Feng Lin, Hock-Soon Seah
2019-04-04
In this paper, we propose a novel space partitioning strategy for implicit hierarchy visualization such that the new plot not only has a tidy layout similar to the treemap, but also is flexible to data changes similar to the Voronoi treemap. To achieve this, we define a new distance function and neighborhood relationship between sites so that space will be divided by axis-aligned segments. Then a sweepline+skyline based heuristic algorithm is proposed to allocate the partitioned spaces to form an orthogonal Voronoi diagram with orthogonal rectangles. To the best of our knowledge, it is the first time to use a sweepline-based strategy for the Voronoi treemap. Moreover, we design a novel strategy to initialize the diagram status and modify the status update procedure so that the generation of our plot is more effective and efficient. We show that the proposed algorithm has an O(nlog(n)) complexity which is the same as the state-of-the-art Voronoi treemap. To this end, we show via experiments on the artificial dataset and real-world dataset the performance of our algorithm in terms of computation time, converge rate, and aspect ratio. Finally, we discuss the pros and cons of our method and make a conclusion.
Tongyang Li, Shouvanik Chakrabarti, Xiaodi Wu
2019-04-04
We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given
-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in time. We design sublinear quantum algorithms for the same task running in time, a quadratic improvement in both and . Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of -dimensional matrix zero-sum games with optimal complexity .
Maria Chiara Angelini, Federico Ricci-Tersenghi
2019-04-03
The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical phase transition the ergodicity breaks and a Monte Carlo dynamics cannot sample correctly the probability distribution in times linear in the system size, there are almost no predictions nor intuitions on the behavior of this class of stochastic dynamics. The situation is particularly intricate because, when using a Monte Carlo based algorithm as an optimization algorithm, one is usually interested in the out of equilibrium behavior which is very hard to analyse. Here we focus on the use of Parallel Tempering in the search for the largest independent set in a sparse random graph, showing that it can find solutions well beyond the dynamical threshold. Comparison with state-of-the-art message passing algorithms reveals that parallel tempering is definitely the algorithm performing best, although a theory explaining its behavior is still lacking.
Karl Däubel
2019-04-03
The Ring Loading Problem emerged in the 1990s to model an important special case of telecommunication networks (SONET rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on
nodes together with non-negative demands between any pair of nodes, the Ring Loading Problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counter-clockwise. Denote with the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour and Winkler [SSW98] showed that , where is the maximum demand value. They also found (implicitly) an instance of the Ring Loading Problem with . Recently, Skutella [Sku16] improved these bounds by showing that , and there exists an instance with . We contribute to this line of research by showing that . We also take a first step towards lower and upper bounds for small instances.
Peng-Cheng Lin, Wan-Lei Zhao
2019-04-03
Hierarchical navigable small world (HNSW) graphs get more and more popular on large-scale nearest neighbor search tasks since the source codes were released two years ago. The attractiveness of this approach lies in its superior performance over most of the nearest neighbor search approaches as well as its genericness to various distance measures. In this paper, several comparative studies have been conducted on this search approach. The role of hierarchical structure in HNSW and the function of HNSW graph itself are investigated. We find that the hierarchical structure in HNSW could not achieve "a much better logarithmic complexity scaling" as it was claimed in the paper, particularly on high dimensional data. Moreover, we find that similar high search speed efficiency as HNSW could be achieved with the support of flat k-NN graph after graph diversification. Finally, we point out the difficulty, faced by most of the graph based search approaches, is directly linked to "curse of dimensionality". HNSW, like other graph based approaches, is unable to address such difficulty.
Hanna Geppert, Martin Wilhelm
2019-04-03
Number types for exact computation are usually based on directed acyclic graphs. A poor graph structure can impair the efficency of their evaluation. In such cases the performance of a number type can be drastically improved by restructuring the graph or by internally balancing error bounds with respect to the graph's structure. We compare advantages and disadvantages of these two concepts both theoretically and experimentally.
Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn, M. Sadegh Riazi
2019-04-03
We present new secure protocols for approximate
-nearest neighbor search ( -NNS) over the Euclidean distance in the semi-honest model. Our implementation is able to handle massive datasets efficiently. On the algorithmic front, we show a new circuit for the approximate top- selection from numbers that is built from merely comparators. Using this circuit as a subroutine, we design new approximate -NNS algorithms and two corresponding secure protocols: 1) optimized linear scan; 2) clustering-based sublinear time algorithm. Our secure protocols utilize a combination of additively-homomorphic encryption, garbled circuit and Oblivious RAM. Along the way, we introduce various optimizations to these primitives, which drastically improve concrete efficiency. We evaluate the new protocols empirically and show that they are able to handle datasets that are significantly larger than in the prior work. For instance, running on two standard Azure instances within the same availability zone, for a dataset of -dimensional descriptors of images, we can find nearest neighbors with average accuracy in under seconds improving upon prior work by at least two orders of magnitude.
