The localcomputation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of ...
详细信息
ISBN:
(纸本)9781450385480
The localcomputation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node's output. In this paper we show that the randomized LCA complexity of the Lovasz local Lemma (LLL) on constant degree graphs is Omega(log n). The lower bound follows by proving an Q (log n) lower bound for the Sinkless Orientation problem introduced in [Brandt et al. STOC 2016]. This answers a question of [Rosenbaum, Suomela PODC 2020]. Additionally, we show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of o (root log n) can be turned into a deterministic LCA algorithm with a probe complexity of O(log* n). This improves exponentially upon the currently best known speed-up result from o (log log n) to O (log* n) implied by the result of [Chang, Pettie FOCS 2017] in the local model. Finally, we show that for every fixed constant c >= 2, the deterministic VOLUME complexity of c-coloring a bounded degree tree is Theta (n), where the VOLUME model is a close relative of the LCA model that was recently introduced by [Rosenbaum, Suomela PODC 2020].
We give a 2((O) over bar) (root n/epsilon)-time algorithm for properly learning monotone Boolean functions under the uniform distribution over {0, 1}(n). Our algorithm is robust to adversarial label noise and has a ru...
详细信息
ISBN:
(纸本)9781665455190
We give a 2((O) over bar) (root n/epsilon)-time algorithm for properly learning monotone Boolean functions under the uniform distribution over {0, 1}(n). Our algorithm is robust to adversarial label noise and has a running time nearly matching that of the state-of-the-art improper learning algorithm of Bshouty and Tamon (JACM '96) and an information-theoretic lower bound of Blais et al (RANDOM '15). Prior to this work, no proper learning algorithm with running time smaller than 2(Omega(n)) was known to exist. The core of our proper learner is a localcomputation algorithm for sorting binary labels on a poset. Our algorithm is built on a body of work on distributed greedy graph algorithms;specifically we rely on a recent work of Ghaffari (FOCS'22), which gives an efficient algorithm for computing maximal matchings in a graph in the LCA model of Rubinfeld et al and Alon et al (ICS'11, SODA'12). The applications of our local sorting algorithm extend beyond learning on the Boolean cube: we also give a tolerant tester for Boolean functions over general posets that distinguishes functions that are epsilon/3-close to monotone from those that are e-far. Previous tolerant testers for the Boolean cube only distinguished between epsilon/Omega(root n)-close and epsilon-far.
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. ...
详细信息
We consider the problem of sampling from a distribution on graphs, specifically when the distribution is defined by an evolving graph model, and consider the time, space, and randomness complexities of such samplers. In the standard approach, the whole graph is chosen randomly according to the randomized evolving process, stored in full, and then queries on the sampled graph are answered by simply accessing the stored graph. This may require prohibitive amounts of time, space, and random bits, especially when only a small number of queries are actually issued. Instead, we propose a setting where one generates parts of the sampled graph on-the-fly, in response to queries, and therefore requires amounts of time, space, and random bits that are a function of the actual number of queries. Yet, the responses to the queries correspond to a graph sampled from the distribution in question. Within this framework, we focus on two random graph models: the Barabasi-Albert Preferential Attachment model (BA-graphs) (Science, 286 (5439):509-512) (for the special case of out-degree 1) and the random recursive tree model (Theory of Probability and Mathematical Statistics, (51):1-28). We give on-the-fly generation algorithms for both models. With probability 1 - 1/poly(n), each and every query is answered in polylog(n) time, and the increase in space and the number of random bits consumed by any single query are both polylog(n), where n denotes the number of vertices in the graph. Our work thus proposes a new approach for the access to huge graphs sampled from a given distribution, and our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph's nodes is possible. In addition to the conceptual contribution, efficient on-the-fly generation of random graphs can serve as a tool for the efficient simulation of sublinear algorithms over large BA-graphs, and the efficient estimation of their on such graphs.
We introduce the problem of augmenting graphs with sublinear memory in order to speed up replies to queries. As a concrete example, we focus on the following problem: the input is an (unpartitioned) bipartite graph G ...
详细信息
ISBN:
(纸本)9783030046934;9783030046927
We introduce the problem of augmenting graphs with sublinear memory in order to speed up replies to queries. As a concrete example, we focus on the following problem: the input is an (unpartitioned) bipartite graph G = (V, E). Given a query q is an element of V, the algorithm's goal is to output q's color in some legal 2-coloring of G, using few probes to the graph. All replies have to be consistent with the same 2-coloring. We show that if a linear amount of preprocessing is allowed, there is a randomized algorithm that, for any alpha, uses (m/alpha) probes and (O) over tilde(alpha) memory, where m is the number of edges in the graph. On the negative side, we show that for a natural family of algorithms that we call probe-first local computation algorithms, this trade-off is optimal even with unbounded preprocessing. We describe a randomized algorithm that replies to queries using (O) over tilde (root n/Phi(2)) probes with no additional memory on regular graphs with conductance Phi (n is the number of vertices in G). In contrast, we show that any deterministic algorithm for regular graphs that uses no memory augmentation requires a linear (in n) number of probes, even if the conductance is the largest possible. We give an algorithm for grids and tori that uses a sublinear number of probes and no memory. Last, we give an algorithm for trees that errs on a sublinear number of edges (i.e., a sublinear number of edges are monochromatic under this coloring) that uses sublinear preprocessing, memory and probes per query.
We introduce the notion of localcomputation mechanism design—designing game-theoretic mechanisms that run in polylogarithmic time and space. localcomputation mechanisms reply to each query in polylogarithmic time a...
详细信息
We introduce the notion of localcomputation mechanism design—designing game-theoretic mechanisms that run in polylogarithmic time and space. localcomputation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and *** present localcomputation mechanisms for two classical game-theoretical problems: stable matching and job scheduling. For stable matching, some of our techniques may have implications to the global (non-LCA (localcomputation Algorithm)) setting. Specifically, we show that when the men’s preference lists are bounded, we can achieve an arbitrarily good approximation to the stable matching within a fixed number of iterations of the Gale-Shapley algorithm.
Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particul...
详细信息
Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.
暂无评论