223 research outputs found
Improved Distributed Algorithms for Coloring and Network Decomposition Problems
No full textACM Danny Lewin Award 199
Quantifiers and approximation
No full textSpecial issue for the best papers of Structure in Complexity Theory 1990. Extended abstract also in Proceedings of the 22nd ACM-SIGACT Symposium on Theory of Computing, May 1990 (STOC 90
Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds
No full textSIAM Journal on Computing262350-368SMJC
OLIVAW: Mastering Othello without Human Knowledge, nor a Penny
No full textWe introduce OLIVAW, an AI Othello player adopting the design principles of the famous AlphaGo programs. The main motivation behind OLIVAW was to attain exceptional competence in a non-trivial board game at a tiny fraction of the cost of its illustrious predecessors. In this paper, we show how the AlphaGo Zero's paradigm can be successfully applied to the popular game of Othello using only commodity hardware and free cloud services. While being simpler than Chess or Go, Othello maintains a considerable search space and difficulty in evaluating board positions. To achieve this result, OLIVAW implements some improvements inspired by recent works to accelerate the standard AlphaGo Zero learning process. The main modification implies doubling the positions collected per game during the training phase, by including also positions not played but largely explored by the agent. We tested the strength of OLIVAW in three different ways: by pitting it against Edax, the strongest open-source Othello engine, by playing anonymous games on the web platform OthelloQuest, and finally in two in-person matches against top-notch human players: a national champion and a former world champion
Fast distributed algorithms for brooks-vizing colorings
No full textSpecial issue for the best papers of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98)
Almost tight bounds for rumour spreading with conductance
No full textWe show that if a connected graph with n nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within Õ(φ-1·log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The Õ(⋯) notation hides a polylog φ-1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ-1·log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds. © 2010 ACM
Milgram-routing in social networks
No full textWe demonstrate how a recent model of social networks (Affiliation Networks", [21]) offers powerful cues in local routing within social networks, a theme made famous by sociologist Milgram's six degrees of separation" experiments. This model posits the existence of an interest space" that underlies a social network; we prove that in networks produced by this model, not only do short paths exist among all pairs of nodes but natural local routing algorithms can discover them effectively. Specifically, we show that local routing can discover paths of length O(log2 n) to targets chosen uniformly at random, and paths of length O(1) to targets chosen with probability proportional to their degrees. Experiments on the co-authorship graph derived from DBLP data confirm our theoretical results, and shed light into the power of one step of lookahead in routing algorithms for social networks. Copyright © 2011 by the Association for Computing Machinery, Inc. (ACM)
How to schedule a cascade in an arbitrary graph
No full textWhen individuals in a social network make decisions that depend on what others have done earlier, there is the potential for a cascade to form - - a run of behaviors that are highly correlated. In an arbitrary network, the outcome of such a cascade can depend sensitively on the order in which nodes make their decisions, but to do date there has been very little investigation of how this dependence works, or how to choose an order to optimize various parameters of the cascade. Here we formulate the problem of ordering the nodes in a cascade to maximize the expected number of "favorable" decisions - those that support a given option. We provide an algorithm that ensures an expected linear number of favorable decisions in any graph, and we show that the performance bounds for our algorithm are essentially the best achievable assuming P ≠ NP. © 2012 ACM
Some Simple Distributed Algorithms for Sparse Networks
No full textWe give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2D-1 colours, and maximal matchings can be computed within O(log^* n + D) deterministic rounds, where D is the maximum degree of the network. We also show how to find maximal independent sets and (D+1)-vertex colourings within O(log^* n + D^2) deterministic rounds. All hidden constants are very small and the algorithms are very simple
- …
