Suche
Ergebnisse

Stabilization Time in Weighted Minority Processes
(2019)Leibniz International Proceedings in Informatics ~ 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)A minority process in a weighted graph is a dynamically changing coloring. Each node repeatedly changes its color in order to minimize the sum of weighted conflicts with its neighbors. We study the number of steps until such a process stabilizes. Our main contribution is an exponential lower bound on stabilization time. We first present a construction showing this bound in the adversarial sequential model, and then we show how to extend ...Conference Paper 
MIDIVAE: Modeling Dynamics and Instrumentation of Music with Applications to Style Transfer
(2018)Proceedings of the 19th International Society for Music Information Retrieval Conference (ISMIR 2018)We introduce MIDIVAE, a neural network model basedon Variational Autoencoders that is capable of handlingpolyphonic music with multiple instrument tracks, as wellas modeling the dynamics of music by incorporating notedurations and velocities. We show that MIDIVAE can perform style transfer on symbolic music by automaticallychanging pitches, dynamics and instruments of a musicpiece from, e.g., a Classical to a ...Conference Paper 
piChain: When a Blockchain Meets Paxos
(2018)Leibniz International Proceedings in Informatics ~ 21st International Conference on Principles of Distributed Systems (OPODIS 2017)We present a new faulttolerant distributed state machine to inherit the best features of its “parents in spirit”: Paxos, providing strong consistency, and a blockchain, providing simplicity and availability. Our proposal is simple as it does not include any heavy weight distributed failure handling protocols such as leader election. In addition, our proposal has a few other valuable features, e.g., it is responsive, it scales well, and ...Conference Paper 
A Tight Lower Bound for SemiSynchronous Collaborative Grid Exploration
(2018)Leibniz International Proceedings in Informatics ~ 32nd International Symposium on Distributed Computing (DISC 2018)Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semisynchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one lookcomputemove cycle. The agents operate ...Conference Paper 
Impatient Online Matching
(2018)Leibniz International Proceedings in Informatics ~ 29th International Symposium on Algorithms and Computation (ISAAC 2018)We investigate the problem of Mincost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linearMPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convexMPMD where time cost functions are convex, ...Conference Paper 
Algorithmic Channel Design
(2018)Leibniz International Proceedings in Informatics ~ 29th International Symposium on Algorithms and Computation (ISAAC 2018)Payment networks, also known as channels, are a most promising solution to the throughput problem of cryptocurrencies. In this paper we study the design of capitalefficient payment networks, offline as well as online variants. We want to know how to compute an efficient payment network topology, how capital should be assigned to the individual edges, and how to decide which transactions to accept. Towards this end, we present a flurry ...Conference Paper 
MinCost Bipartite Perfect Matching with Delays
(2017)Leibniz International Proceedings in Informatics ~ Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)In the mincost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances ...Conference Paper 
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
(2017)Leibniz International Proceedings in Informatics ~ 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)For the game of Cops and Robbers, it is known that in 1copwin graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in kcopwin graphs, the capture time is at most O(n^{k + 1}), however, no nontrivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be ...Conference Paper 
Brief Announcement: Towards Reduced Instruction Sets for Synchronization
(2017)Leibniz International Proceedings in Informatics ~ 31st International Symposium on Distributed Computing (DISC 2017)Contrary to common belief, a recent work by Ellen, Gelashvili, Shavit, and Zhu has shown that computability does not require multicore architectures to support "strong" synchronization instructions like compareandswap, as opposed to combinations of "weaker" instructions like decrement and multiply. However, this is the status quo, and in turn, most efficient concurrent datastructures heavily rely on compareandswap (e.g. for swinging ...Conference Paper 
Distributed stable matching with similar preference lists
(2017)Leibniz International Proceedings in Informatics ~ 20th International Conference on Principles of Distributed Systems (OPODIS 2016)Consider a complete bipartite graph of 2n nodes with n nodes on each side. In a round, each node can either send at most one message to a neighbor or receive at most one message from a neighbor. Each node has a preference list that ranks all its neighbors in a strict order from 1 to n. We introduce a nonnegative similarity parameter D < n for the preference lists of nodes on one side only. For D = 0, these preference lists are same and ...Conference Paper