Jeremy F Alm
2019-02-26
In this paper, we give an algorithm for detecting non-trivial 3-APs in multiplicative subgroups of
that is substantially more efficient than the naive approach. It follows that certain Var der Waerden-like numbers can be computed in polynomial time.
Marco Canini, Iosif Salem, Liron Schiff, Elad Michael Schiller, Stefan Schmid
2017-12-20
By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization - a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerate a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can reach any switch (or another controller) in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one controller (as long as at least one controller is not faulty). We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.
Ryan Spring, Anastasios Kyrillidis, Vijai Mohan, Anshumali Shrivastava
2019-02-01
Many popular first-order optimization methods (e.g., Momentum, AdaGrad, Adam) accelerate the convergence rate of deep learning models. However, these algorithms require auxiliary parameters, which cost additional memory proportional to the number of parameters in the model. The problem is becoming more severe as deep learning models continue to grow larger in order to learn from complex, large-scale datasets. Our proposed solution is to maintain a linear sketch to compress the auxiliary variables. We demonstrate that our technique has the same performance as the full-sized baseline, while using significantly less space for the auxiliary variables. Theoretically, we prove that count-sketch optimization maintains the SGD convergence rate, while gracefully reducing memory usage for large-models. On the large-scale 1-Billion Word dataset, we save 25% of the memory used during training (8.6 GB instead of 11.7 GB) by compressing the Adam optimizer in the Embedding and Softmax layers with negligible accuracy and performance loss. For an Amazon extreme classification task with over 49.5 million classes, we also reduce the training time by 38%, by increasing the mini-batch size 3.5x using our count-sketch optimizer.
Sebastian Brandt
2019-02-26
Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lov'asz Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least
, transforms any -round algorithm for one specific LLL problem into a -round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem , with the difference that the problem the inferred -round algorithm solves is not (necessarily) the same problem as . Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for into a description for and reversible in the sense that any -round algorithm for can be transformed into a -round algorithm for . In particular, for any locally checkable problem with exact deterministic time complexity on graphs with nodes, maximum node degree , and girth at least , there is a sequence of problems with time complexities , that can be inferred from . As a first application of our generalized speedup, we solve a long-standing open problem of Naor and Stockmeyer [STOC'93]: we show that weak -coloring in odd-degree graphs cannot be solved in rounds, thereby providing a matching lower bound to their upper bound.
Lingxiao Huang, Nisheeth K. Vishnoi
2019-02-21
Fair classification has been a topic of intense study in machine learning, and several algorithms have been proposed towards this important task. However, in a recent study, Friedler et al. observed that fair classification algorithms may not be stable with respect to variations in the training dataset -- a crucial consideration in several real-world applications. Motivated by their work, we study the problem of designing classification algorithms that are both fair and stable. We propose an extended framework based on fair classification algorithms that are formulated as optimization problems, by introducing a stability-focused regularization term. Theoretically, we prove a stability guarantee, that was lacking in fair classification algorithms, and also provide an accuracy guarantee for our extended framework. Our accuracy guarantee can be used to inform the selection of the regularization parameter in our framework. To the best of our knowledge, this is the first work that combines stability and fairness in automated decision-making tasks. We assess the benefits of our approach empirically by extending several fair classification algorithms that are shown to achieve the best balance between fairness and accuracy over the Adult dataset. Our empirical results show that our framework indeed improves the stability at only a slight sacrifice in accuracy.
Amit Deshpande, Anand Louis, Apoorv Vikram Singh
2018-04-28
-means clustering is NP-hard in the worst case but previous work has shown efficient algorithms assuming the optimal -means clusters are \emph{stable} under additive or multiplicative perturbation of data. This has two caveats. First, we do not know how to efficiently verify this property of optimal solutions that are NP-hard to compute in the first place. Second, the stability assumptions required for polynomial time -means algorithms are often unreasonable when compared to the ground-truth clusters in real-world data. A consequence of multiplicative perturbation resilience is \emph{center proximity}, that is, every point is closer to the center of its own cluster than the center of any other cluster, by some multiplicative factor . We study the problem of minimizing the Euclidean -means objective only over clusterings that satisfy -center proximity. We give a simple algorithm to find the optimal -center-proximal -means clustering in running time exponential in and but linear in the number of points and the dimension. We define an analogous -center proximity condition for outliers, and give similar algorithmic guarantees for -means with outliers and -center proximity. On the hardness side we show that for any , there exists an , , and an such that minimizing the -means objective over clusterings that satisfy -center proximity is NP-hard to approximate within a multiplicative factor.
Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos
2018-05-11
We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula \phi for the problem to be fixed-parameter tractable or to admit a polynomial kernel.
Zonglei Bai, Yongzhi Cao, Hanpin Wang
2019-02-25
In this paper, we give a sampling algorithm for the Potts model using Markov chains. Based on the sampling algorithm, we give \emph{FPRAS}es for the Potts model and the number of
-colorings of the graph.
Gecia Bravo Hermsdorff, Lee M. Gunderson
2019-02-26
How might one "reduce" a graph? That is, generate a smaller graph that preserves the global structure at the expense of discarding local details? There has been extensive work on both graph sparsification (removing edges) and graph coarsening (merging nodes, often by edge contraction); however, these operations are currently treated separately. Interestingly, for a planar graph, edge deletion corresponds to edge contraction in its planar dual (and more generally, for a graphical matroid and its dual). Moreover, with respect to the dynamics induced by the graph Laplacian (e.g., diffusion), deletion and contraction are physical manifestations of two reciprocal limits: edge weights of
and , respectively. In this work, we provide a unifying framework that captures both of these operations, allowing one to simultaneously coarsen and sparsify a graph, while preserving its large-scale structure. Using synthetic models and real-world datasets, we validate our algorithm and compare it with existing methods for graph coarsening and sparsification. While modern spectral schemes focus on the Laplacian (indeed, an important operator), our framework preserves its inverse, allowing one to quantitatively compare the effect of edge deletion with the (now finite) effect of edge contraction.
Sarah Cannon, Joshua J. Daymude, Dana Randall, Andréa W. Richa
2016-03-25
In systems of programmable matter, we are given a collection of simple computation elements (or particles) with limited (constant-size) memory. We are interested in when they can self-organize to solve system-wide problems of movement, configuration and coordination. Here, we initiate a stochastic approach to developing robust distributed algorithms for programmable matter systems using Markov chains. We are able to leverage the wealth of prior work in Markov chains and related areas to design and rigorously analyze our distributed algorithms and show that they have several desirable properties. We study the compression problem, in which a particle system must gather as tightly together as possible, as in a sphere or its equivalent in the presence of some underlying geometry. More specifically, we seek fully distributed, local, and asynchronous algorithms that lead the system to converge to a configuration with small boundary. We present a Markov chain-based algorithm that solves the compression problem under the geometric amoebot model, for particle systems that begin in a connected configuration. The algorithm takes as input a bias parameter
, where corresponds to particles favoring having more neighbors. We show that for all , there is a constant such that eventually with all but exponentially small probability the particles are -compressed, meaning the perimeter of the system configuration is at most , where is the minimum possible perimeter of the particle system. Surprisingly, the same algorithm can also be used for expansion when , and we prove similar results about expansion for values of in this range. This is counterintuitive as it shows that particles preferring to be next to each other ( ) is not sufficient to guarantee compression.
