3 citations · 8 across the 14 of their papers we have counts for
15 papers
Liquid democracy under vote correlation: On the fallacies of averaging and the excluded middle
Seth Gilbert, Stefan Schmid, Santiago Schnell +2
Liquid democracy permits voters to vote directly or delegate their votes to others. Existing algorithmic analyses assign each voter a single scalar parameter, interpreted as an ind…
Replacers and their evolutionary stability in the Moran process on graphs
Michal Pecho, Jakub Svoboda, Lenka Kopfová +2
Evolutionary dynamics in finite structured populations are commonly modeled by the Moran Birth-death process. A key quantity is the fixation probability of a single invader attempt…
Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality
Amogh Palasamudram, Jakub Svoboda, Suguman Bansal +1
Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves as…
Genotype specificity and spatial arrangement govern the direction and magnitude of selection in variable environments
Hossein Nemati, Kamran Kaveh, Jakub Svoboda +2
Spatial environmental variation can either amplify or suppress the fixation of beneficial mutants in structured populations, yet the interplay of ecological factors and spatial str…
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection
Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid +2
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the…
Value Iteration with Guessing for Markov Chains and Markov Decision Processes
Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona +1
Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and plannin…
Maintaining diversity in structured populations
David A. Brewster, Jakub Svoboda, Dylan Roscow +3
We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth-death (b…
Linear Equations with Min and Max Operators: Computational Complexity
Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona +1
We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrict…
Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are i…
Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously an…
Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating
Jakub Svoboda, Soham Joshi, Josef Tkadlec +1
Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the…
Shortest Dominating Set Reconfiguration under Token Sliding
Jan Matyáš Křišťan, Jakub Svoboda
In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Tok…
Social Balance on Networks: Local Minima and Best Edge Dynamics
Krishnendu Chatterjee, Jakub Svoboda, Ðorđe Žikelić +2
Structural balance theory is an established framework for studying social relationships of friendship and enmity. These relationships are modeled by a signed network whose energy p…
Online Admission Control and Rebalancing in Payment Channel Networks
Mahsa Bastankhah, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali +3
Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain rout…
Weighted Packet Selection for Rechargeable Links: Complexity and Approximation
Stefan Schmid, Jakub Svoboda, Michelle Yeo
We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link $…