Krishnendu Chatterjee

research

∙ 07/14/2023

Repeated Game Dynamics in Population Protocols

We initiate the study of repeated game dynamics in the population model,...

0 Dan Alistarh, et al. ∙

research

∙ 07/13/2023

Entropic Risk for Turn-Based Stochastic Games

Entropic risk (ERisk) is an established risk measure in finance, quantif...

0 Christel Baier, et al. ∙

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...

0 S. Akshay, et al. ∙

research

∙ 05/24/2023

Automated Tail Bound Analysis for Probabilistic Recurrence Relations

Probabilistic recurrence relations (PRRs) are a standard formalism for d...

0 Yican Sun, et al. ∙

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...

0 Mathias Lechner, et al. ∙

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...

0 Đorđe Žikelić, et al. ∙

research

∙ 10/11/2022

Learning Control Policies for Region Stabilization in Stochastic Systems

We consider the problem of learning control policies in stochastic syste...

0 Matin Ansaripour, et al. ∙

research

∙ 09/28/2022

Repeated Prophet Inequality with Near-optimal Bounds

In modern sample-driven Prophet Inequality, an adversary chooses a seque...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 09/24/2022

Online Admission Control and Rebalancing in Payment Channel Networks

Payment channel networks (PCNs) are a promising technology to improve th...

0 Mahsa Bastankhah, et al. ∙

research

∙ 05/24/2022

Learning Stabilizing Policies in Stochastic Control Systems

In this work, we address the problem of learning provably stable neural ...

0 Đorđe Žikelić, et al. ∙

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...

0 Mathias Lechner, et al. ∙

research

∙ 11/04/2021

Infinite Time Horizon Safety of Bayesian Neural Networks

Bayesian neural networks (BNNs) place distributions over the weights of ...

0 Mathias Lechner, et al. ∙

research

∙ 08/04/2021

On Lexicographic Proof Rules for Probabilistic Termination

We consider the almost-sure (a.s.) termination problem for probabilistic...

0 Krishnendu Chatterjee, et al. ∙

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 ...

0 Pratyush Agarwal, et al. ∙

research

∙ 04/15/2021

Symbolic Time and Space Tradeoffs for Probabilistic Verification

We present a faster symbolic algorithm for the following central problem...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 04/15/2021

Stochastic Processes with Expected Stopping Time

Markov chains are the de facto finite-state model for stochastic dynamic...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 04/02/2021

Proving Non-termination by Program Reversal

We present a new approach to proving non-termination of non-deterministi...

0 Krishnendu Chatterjee, et al. ∙

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 ...

0 Juho Hirvonen, et al. ∙

research

∙ 01/06/2021

On Satisficing in Quantitative Games

Several problems in planning and reactive synthesis can be reduced to th...

6 Suguman Bansal, et al. ∙

research

∙ 11/30/2020

Quantitative Analysis of Assertion Violations in Probabilistic Programs

In this work, we consider the fundamental problem of deriving quantitati...

0 Jinyi Wang, et al. ∙

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...

0 Truc Lam Bui, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 08/02/2020

Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations

Analyzing probabilistic programs and randomized algorithms are classical...

0 Jinyi Wang, et al. ∙

research

∙ 07/28/2020

Inductive Reachability Witnesses

In this work, we consider the fundamental problem of reachability analys...

0 Ali Asadi, et al. ∙

research

∙ 05/08/2020

Stochastic Games with Lexicographic Reachability-Safety Objectives

We study turn-based stochastic zero-sum games with lexicographic prefere...

0 Krishnendu Chatterjee, et al. ∙

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...

0 Ali Asadi, et al. ∙

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...

0 Tomáš Brázdil, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 09/11/2019

Quasipolynomial Set-Based Symbolic Algorithms for Parity Games

Solving parity games, which are equivalent to modal μ-calculus model che...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 09/03/2019

Value-centric Dynamic Partial Order Reduction

The verification of concurrent programs remains an open challenge, as th...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 07/25/2019

Deciding Fast Termination for Probabilistic VASS with Nondeterminism

A probabilistic vector addition system with states (pVASS) is a finite s...

0 Tomáš Brázdil, et al. ∙

research

∙ 06/19/2019

Strategy Representation by Decision Trees with Linear Classifiers

Graph games and Markov decision processes (MDPs) are standard models in ...

0 Pranav Ashok, et al. ∙

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 ...

0 Krishnendu Chatterjee, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 02/21/2019

Probabilistic Smart Contracts: Secure Randomness on the Blockchain

In today's programmable blockchains, smart contracts are limited to bein...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 02/13/2019

Proving Expected Sensitivity of Probabilistic Programs with Randomized Execution Time

The notion of program sensitivity (aka Lipschitz continuity) specifies t...

0 Peixin Wang, et al. ∙

research

∙ 02/12/2019

Cost Analysis of Nondeterministic Probabilistic Programs

We consider the problem of expected cost analysis over nondeterministic ...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 02/12/2019

Polynomial Invariant Generation for Non-deterministic Recursive Programs

We present a sound and complete method to generate inductive invariants ...

0 Krishnendu Chatterjee, et al. ∙

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...

0 Mingzhang Huang, et al. ∙

research

∙ 09/27/2018

Fixation probability and fixation time in structured populations

The rate of biological evolution depends on the fixation probability and...

0 Josef Tkadlec, et al. ∙

research

∙ 06/14/2018

New Approaches for Almost-Sure Termination of Probabilistic Programs

We study the almost-sure termination problem for probabilistic programs....

0 Mingzhang Huang, et al. ∙

research

∙ 06/13/2018

Parameter-Independent Strategies for pMDPs via POMDPs

Markov Decision Processes (MDPs) are a popular class of models suitable ...

0 Sebastian Arming, et al. ∙

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...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 05/23/2018

Secure Credit Reporting on the Blockchain

We present a secure approach for maintaining and reporting credit histor...

0 Amir Kafshdar Goharshady, et al. ∙

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...

0 Tomáš Brázdil, et al. ∙

research

∙ 04/27/2018

Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives

Partially-observable Markov decision processes (POMDPs) with discounted-...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 04/24/2018

Computational Approaches for Stochastic Shortest Path on Succinct MDPs

We consider the stochastic shortest path (SSP) problem for succinct Mark...

0 Krishnendu Chatterjee, et al. ∙

research

∙ 04/19/2018

Algorithms and Conditional Lower Bounds for Planning Problems

We consider planning problems for graphs, Markov decision processes (MDP...

0 Krishnendu Chatterjee, et al. ∙

Krishnendu Chatterjee

Featured Co-authors