research
∙
07/14/2023
Repeated Game Dynamics in Population Protocols
We initiate the study of repeated game dynamics in the population model,...
share
research
∙
07/13/2023
Entropic Risk for Turn-Based Stochastic Games
Entropic risk (ERisk) is an established risk measure in finance, quantif...
research
∙
05/26/2023
MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives
Markov decision processes can be viewed as transformers of probability d...
research
∙
05/24/2023
Automated Tail Bound Analysis for Probabilistic Recurrence Relations
Probabilistic recurrence relations (PRRs) are a standard formalism for d...
research
∙
11/29/2022
Quantization-aware Interval Bound Propagation for Training Certifiably Robust Quantized Neural Networks
We study the problem of training and certifying adversarially robust qua...
research
∙
10/11/2022
Learning Control Policies for Stochastic Systems with Reach-avoid Guarantees
We study the problem of learning controllers for discrete-time non-linea...
research
∙
10/11/2022
Learning Control Policies for Region Stabilization in Stochastic Systems
We consider the problem of learning control policies in stochastic syste...
research
∙
09/28/2022
Repeated Prophet Inequality with Near-optimal Bounds
In modern sample-driven Prophet Inequality, an adversary chooses a seque...
research
∙
09/24/2022
Online Admission Control and Rebalancing in Payment Channel Networks
Payment channel networks (PCNs) are a promising technology to improve th...
research
∙
05/24/2022
Learning Stabilizing Policies in Stochastic Control Systems
In this work, we address the problem of learning provably stable neural ...
research
∙
12/17/2021
Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
We consider the problem of formally verifying almost-sure (a.s.) asympto...
research
∙
11/04/2021
Infinite Time Horizon Safety of Bayesian Neural Networks
Bayesian neural networks (BNNs) place distributions over the weights of ...
research
∙
08/04/2021
On Lexicographic Proof Rules for Probabilistic Termination
We consider the almost-sure (a.s.) termination problem for probabilistic...
research
∙
05/13/2021
Stateless Model Checking under a Reads-Value-From Equivalence
Stateless model checking (SMC) is one of the standard approaches to the ...
research
∙
04/15/2021
Symbolic Time and Space Tradeoffs for Probabilistic Verification
We present a faster symbolic algorithm for the following central problem...
research
∙
04/15/2021
Stochastic Processes with Expected Stopping Time
Markov chains are the de facto finite-state model for stochastic dynamic...
research
∙
04/02/2021
Proving Non-termination by Program Reversal
We present a new approach to proving non-termination of non-deterministi...
research
∙
02/26/2021
Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory
Graphical games are a useful framework for modeling the interactions of ...
research
∙
01/06/2021
On Satisficing in Quantitative Games
Several problems in planning and reactive synthesis can be reduced to th...
research
∙
11/30/2020
Quantitative Analysis of Assertion Violations in Probabilistic Programs
In this work, we consider the fundamental problem of deriving quantitati...
research
∙
11/23/2020
The Reads-From Equivalence for the TSO and PSO Memory Models
The verification of concurrent programs remains an open challenge due to...
research
∙
08/14/2020
Proving Almost-Sure Termination of Probabilistic Programs via Incremental Pruning
The extension of classical imperative programs with real-valued random v...
research
∙
08/02/2020
Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations
Analyzing probabilistic programs and randomized algorithms are classical...
research
∙
07/28/2020
Inductive Reachability Witnesses
In this work, we consider the fundamental problem of reachability analys...
research
∙
05/08/2020
Stochastic Games with Lexicographic Reachability-Safety Objectives
We study turn-based stochastic zero-sum games with lexicographic prefere...
research
∙
04/19/2020
Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) a...
research
∙
02/27/2020
Reinforcement Learning of Risk-Constrained Policies in Markov Decision Processes
Markov decision processes (MDPs) are the defacto frame-work for sequenti...
research
∙
01/29/2020
Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis
Interprocedural data-flow analyses form an expressive and useful paradig...
research
∙
10/01/2019
Optimal Dyck Reachability for Data-Dependence and Alias Analysis
A fundamental algorithmic problem at the heart of static analysis is Dyc...
research
∙
09/12/2019
Near-Linear Time Algorithms for Streett Objectives in Graphs and MDPs
The fundamental model-checking problem, given as input a model and a spe...
research
∙
09/11/2019
Quasipolynomial Set-Based Symbolic Algorithms for Parity Games
Solving parity games, which are equivalent to modal μ-calculus model che...
research
∙
09/03/2019
Value-centric Dynamic Partial Order Reduction
The verification of concurrent programs remains an open challenge, as th...
research
∙
07/25/2019
Deciding Fast Termination for Probabilistic VASS with Nondeterminism
A probabilistic vector addition system with states (pVASS) is a finite s...
research
∙
06/19/2019
Strategy Representation by Decision Trees with Linear Classifiers
Graph games and Markov decision processes (MDPs) are standard models in ...
research
∙
05/31/2019
The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game
The Price of Anarchy (PoA) is a well-established game-theoretic concept ...
research
∙
04/30/2019
The Complexity of POMDPs with Long-run Average Objectives
We study the problem of approximation of optimal values in partially-obs...
research
∙
02/21/2019
Probabilistic Smart Contracts: Secure Randomness on the Blockchain
In today's programmable blockchains, smart contracts are limited to bein...
research
∙
02/13/2019
Proving Expected Sensitivity of Probabilistic Programs with Randomized Execution Time
The notion of program sensitivity (aka Lipschitz continuity) specifies t...
research
∙
02/12/2019
Cost Analysis of Nondeterministic Probabilistic Programs
We consider the problem of expected cost analysis over nondeterministic ...
research
∙
02/12/2019
Polynomial Invariant Generation for Non-deterministic Recursive Programs
We present a sound and complete method to generate inductive invariants ...
research
∙
01/18/2019
Compositional Analysis for Almost-Sure Termination of Probabilistic Programs
In this work, we consider the almost-sure termination problem for probab...
research
∙
09/27/2018
Fixation probability and fixation time in structured populations
The rate of biological evolution depends on the fixation probability and...
research
∙
06/14/2018
New Approaches for Almost-Sure Termination of Probabilistic Programs
We study the almost-sure termination problem for probabilistic programs....
research
∙
06/13/2018
Parameter-Independent Strategies for pMDPs via POMDPs
Markov Decision Processes (MDPs) are a popular class of models suitable ...
research
∙
06/08/2018
Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
Crypto-currencies are digital assets designed to work as a medium of exc...
research
∙
05/23/2018
Secure Credit Reporting on the Blockchain
We present a secure approach for maintaining and reporting credit histor...
research
∙
04/29/2018
Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Vector Addition Systems with States (VASS) provide a well-known and fund...
research
∙
04/27/2018
Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives
Partially-observable Markov decision processes (POMDPs) with discounted-...
research
∙
04/24/2018
Computational Approaches for Stochastic Shortest Path on Succinct MDPs
We consider the stochastic shortest path (SSP) problem for succinct Mark...
research
∙
04/19/2018
