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 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.
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.
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.
暂无评论