The proceedings contain 134 papers. The topics discussed include: nonlocal games, compression theorems, and the arithmetical hierarchy;an area law for 2D frustration-free spin systems;dequantizing the quantum singular...
ISBN:
(纸本)9781450392648
The proceedings contain 134 papers. The topics discussed include: nonlocal games, compression theorems, and the arithmetical hierarchy;an area law for 2D frustration-free spin systems;dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture;near-optimal quantum algorithms for multivariate mean estimation;distributed quantum inner product estimation;the power of two choices in graphical allocation;expanders via local edge flips in quasilinear time;(fractional) online stochastic matching via fine-grained offline statistics;the power of multiple choices in online stochastic matching;online edge coloring via tree recurrences and correlation decay;breaking the n k barrier for minimum k-cut on simple graphs;and learning low-degree functions from a logarithmic number of random queries.
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to implement this approach is through sepa...
详细信息
ISBN:
(纸本)9798400718854
One of the most basic techniques in algorithm design consists of breaking a problem into subproblems and then proceeding recursively. In the case of graph algorithms, one way to implement this approach is through separator sets. Given a graph G = (V, E), a subset of nodes S ⊆ V is called a separator set of G if the size of each connected component of G - S is at most 2/3 · |V|. The most useful separator sets are those that satisfy certain restrictions of cardinality or *** this work, we present the first deterministic algorithm in the distributed CONGEST model that recursively computes a cycle separator over planar graphs in Õ(D) rounds. This result, as in the centralized setting, has significant implications in the area of distributed planar algorithms. In fact, from this result, we can construct a deterministic algorithm that computes a DFS tree in Õ(D) rounds. This matches both the best-known randomized algorithm of Ghaffari and Parter (DISC, 2017) and, up to polylogarithmic factors, the trivial lower bound of Ω(D) rounds.
The tutorial will include an introduction to (i) distributed optimization and distributed machine learning, (ii) security or fault-tolerance for distributed optimization and learning, and (iii) privacy in distributed ...
详细信息
ISBN:
(纸本)9781450385480
The tutorial will include an introduction to (i) distributed optimization and distributed machine learning, (ii) security or fault-tolerance for distributed optimization and learning, and (iii) privacy in distributed optimization and learning. The presentation will cover the basic principles, and some representative solutions. Server-based and peer-to-peer solutions will be discussed. In particular, Byzantine fault-tolerant algorithms for distributed optimization and learning will be discussed. Privacy mechanisms to be discussed include differential privacy and its variations for systems based on multiple servers.
Collaborating across dissimilar, distributed spaces presents numerous challenges for computer-aided spatial communication. Mixed reality (MR) can blend selected surfaces, allowing collaborators to work in blended f-fo...
详细信息
Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of real-world graphs has a severe effect on TC performance. This paper studies the TC algorithm from the persp...
详细信息
ISBN:
(纸本)9781450392044
Triangle Counting (TC) is a basic graph mining problem with numerous applications. However, the large size of real-world graphs has a severe effect on TC performance. This paper studies the TC algorithm from the perspective of memory utilization. We investigate the implications of the skewed degree distribution of real-world graphs on TC and make novel observations on how memory locality is negatively affected. Based on this, we introduce the LOTUS algorithm as a structure-aware TC that optimizes locality. The evaluation on 14 real-world graphs with up to 162 billion edges and on 3 different processor architectures of up to 128 cores shows that Lotus is 2.2-5.5x faster than previous works.
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary m-facet polytopes in.. variables with seed length poly-logarithmic in m,n, concluding a sequence...
详细信息
ISBN:
(纸本)9781450392648
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary m-facet polytopes in.. variables with seed length poly-logarithmic in m,n, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, Zuckerman (SICOMP 2013) for fooling linear and polynomial threshold functions, respectively. In this work, we consider a natural extension of PRGs for intersections of positive spectrahedra. A positive spectrahedron is a Boolean function f(x) = [x(1)A(1) + center dot center dot center dot+x(n)A(n) <= B] where the A(1)s are kxk positive semidefinite matrices. We construct explicit PRGs that delta-fool "regular" width-M positive spectrahedra (i.e., when none of the A(1)s are dominant) over the Boolean space with seed length poly(logk, logn,M, 1/delta). Our main technical contributions are the following: We first prove an invariance principle for positive spectrahedra via the well-known Lindeberg method. As far as we are aware such a generalization of the Lindeberg method was unknown. Second, we prove an upper bound on noise sensitivity and a LittlewoodOfford theorem for positive spectrahedra. Using these results, we give applications for constructing PRGs for positive spectrahedra, learning theory, discrepancy sets for positive spectrahedra (over the Boolean cube) and PRGs for intersections of structured polynomial threshold functions.
The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributedcomputing. Since Lamport's pioneering work [14], this problem has been extensively studied in...
详细信息
Consensus is one of the most thoroughly studied problems in distributedcomputing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting wi...
详细信息
ISBN:
(纸本)9781450392648
Consensus is one of the most thoroughly studied problems in distributedcomputing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting with processes' crashes, since the seminal works of Bar-Joseph and Ben-Or [PODC 1998] and Aspnes and Waarts [SICOMP 1996, Jacm 1998] in the previous century, there is still a fundamental unresolved question about communication complexity of fast randomized Consensus against a (strong) adaptive adversary crashing processes arbitrarily online. The best known upper bound on the number of communication bits is Theta(n(3/2)/root log n) per process, while the best lower bound is Omega(1). This is in contrast to randomized Consensus against a (weak) oblivious adversary, for which time-almost-optimal algorithms guarantee amortized O (1) communication bits per process. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to O ( root n center dot polylog n) bits per process, while keeping almostoptimal (up to factor O ( log(3) n)) time complexity O (root n center dot log(5/2)n). More surprisingly, we show this complexity indeed can be lowered further, but at the expense of increasing time complexity, i.e., there is a trade-off between communication complexity and time complexity. More specifically, our main Consensus algorithm allows to reduce communication complexity per process to any value from polylog n to O ( root n center dot polylog n), as long as Time x Communication = O (n center dot polylog n ). Similarly, reducing time complexity requires more random bits per process, i.e., Time x Randomness =O (n center dot polylog n). Our parameterized consensus solutions are based on a few newly developed paradigms and algorithms for crash-resilient computing, interesting on their own. The first one, called a Fuzzy Counting, provides for each process a number which is in-between the numbers of alive processes at
Cloud applications are increasingly moving away from monolithic services to agile microservices-based deployments. However, efficient resource management for microservices poses a significant hurdle due to the sheer n...
详细信息
ISBN:
(纸本)9781450391993
Cloud applications are increasingly moving away from monolithic services to agile microservices-based deployments. However, efficient resource management for microservices poses a significant hurdle due to the sheer number of loosely coupled and interacting components. The interdependencies between various microservices make existing cloud resource autoscaling techniques ineffective. Meanwhile, machine learning (ML) based approaches that try to capture the complex relationships in microservices require extensive training data and cause intentional SLO violations. Moreover, these ML-heavy approaches are slow in adapting to dynamically changing microservice operating environments. In this paper, we propose PEMA (Practical EfficientMicroservice Autoscaling), a lightweight microservice resource manager that finds efficient resource allocation through opportunistic resource reduction. PEMA's lightweight design enables novel workload-aware and adaptive resource management. Using three prototype microservice implementations, we show that PEMA can find efficient resource allocation and save up to 33% resource compared to the commercial rule-based resource allocations.
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributedcomputing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is sti...
详细信息
暂无评论