
Stateless Model Checking under a ReadsValueFrom Equivalence
Stateless model checking (SMC) is one of the standard approaches to the ...
read it

Symbolic Time and Space Tradeoffs for Probabilistic Verification
We present a faster symbolic algorithm for the following central problem...
read it

Stochastic Processes with Expected Stopping Time
Markov chains are the de facto finitestate model for stochastic dynamic...
read it

Proving Nontermination by Program Reversal
We present a new approach to proving nontermination of nondeterministi...
read it

Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory
Graphical games are a useful framework for modeling the interactions of ...
read it

On Satisficing in Quantitative Games
Several problems in planning and reactive synthesis can be reduced to th...
read it

Quantitative Analysis of Assertion Violations in Probabilistic Programs
In this work, we consider the fundamental problem of deriving quantitati...
read it

The ReadsFrom Equivalence for the TSO and PSO Memory Models
The verification of concurrent programs remains an open challenge due to...
read it

Proving AlmostSure Termination of Probabilistic Programs via Incremental Pruning
The extension of classical imperative programs with realvalued random v...
read it

ConcentrationBound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations
Analyzing probabilistic programs and randomized algorithms are classical...
read it

Inductive Reachability Witnesses
In this work, we consider the fundamental problem of reachability analys...
read it

Stochastic Games with Lexicographic ReachabilitySafety Objectives
We study turnbased stochastic zerosum games with lexicographic prefere...
read it

Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
Discretetime Markov Chains (MCs) and Markov Decision Processes (MDPs) a...
read it

Reinforcement Learning of RiskConstrained Policies in Markov Decision Processes
Markov decision processes (MDPs) are the defacto framework for sequenti...
read it

Optimal and Perfectly Parallel Algorithms for Ondemand Dataflow Analysis
Interprocedural dataflow analyses form an expressive and useful paradig...
read it

Optimal Dyck Reachability for DataDependence and Alias Analysis
A fundamental algorithmic problem at the heart of static analysis is Dyc...
read it

NearLinear Time Algorithms for Streett Objectives in Graphs and MDPs
The fundamental modelchecking problem, given as input a model and a spe...
read it

Quasipolynomial SetBased Symbolic Algorithms for Parity Games
Solving parity games, which are equivalent to modal μcalculus model che...
read it

Valuecentric Dynamic Partial Order Reduction
The verification of concurrent programs remains an open challenge, as th...
read it

Deciding Fast Termination for Probabilistic VASS with Nondeterminism
A probabilistic vector addition system with states (pVASS) is a finite s...
read it

Strategy Representation by Decision Trees with Linear Classifiers
Graph games and Markov decision processes (MDPs) are standard models in ...
read it

The Evolutionary Price of Anarchy: Locally Bounded Agents in a Dynamic Virus Game
The Price of Anarchy (PoA) is a wellestablished gametheoretic concept ...
read it

The Complexity of POMDPs with Longrun Average Objectives
We study the problem of approximation of optimal values in partiallyobs...
read it

Probabilistic Smart Contracts: Secure Randomness on the Blockchain
In today's programmable blockchains, smart contracts are limited to bein...
read it

Proving Expected Sensitivity of Probabilistic Programs with Randomized Execution Time
The notion of program sensitivity (aka Lipschitz continuity) specifies t...
read it

Cost Analysis of Nondeterministic Probabilistic Programs
We consider the problem of expected cost analysis over nondeterministic ...
read it

Polynomial Invariant Generation for Nondeterministic Recursive Programs
We present a sound and complete method to generate inductive invariants ...
read it

Compositional Analysis for AlmostSure Termination of Probabilistic Programs
In this work, we consider the almostsure termination problem for probab...
read it

Fixation probability and fixation time in structured populations
The rate of biological evolution depends on the fixation probability and...
read it

New Approaches for AlmostSure Termination of Probabilistic Programs
We study the almostsure termination problem for probabilistic programs....
read it

ParameterIndependent Strategies for pMDPs via POMDPs
Markov Decision Processes (MDPs) are a popular class of models suitable ...
read it

Ergodic MeanPayoff Games for the Analysis of Attacks in CryptoCurrencies
Cryptocurrencies are digital assets designed to work as a medium of exc...
read it

Secure Credit Reporting on the Blockchain
We present a secure approach for maintaining and reporting credit histor...
read it

Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Vector Addition Systems with States (VASS) provide a wellknown and fund...
read it

Expectation Optimization with Probabilistic Guarantees in POMDPs with Discountedsum Objectives
Partiallyobservable Markov decision processes (POMDPs) with discounted...
read it

Computational Approaches for Stochastic Shortest Path on Succinct MDPs
We consider the stochastic shortest path (SSP) problem for succinct Mark...
read it

Algorithms and Conditional Lower Bounds for Planning Problems
We consider planning problems for graphs, Markov decision processes (MDP...
read it

Coverability: Realizability Lower Bounds
We introduce the problem of temporal coverability for realizability and ...
read it

Combinations of Qualitative Winning for Stochastic Parity Games
We study Markov decision processes and turnbased stochastic games with ...
read it

Symbolic Algorithms for Graphs and Markov Decision Processes with Fairness Objectives
Given a model and a specification, the fundamental modelchecking proble...
read it

Graph Planning with Expected Finite Horizon
Graph planning gives rise to fundamental algorithmic questions such as s...
read it

Strong Amplifiers of Natural Selection: Proofs
We consider the modified Moran process on graphs to study the spread of ...
read it

Strategy Representation by Decision Trees in Reactive Synthesis
Graph games played by two players over finitestate graphs are central i...
read it

Quantitative Analysis of Smart Contracts
Smart contracts are computer programs that are executed by a network of ...
read it

Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter
A model of computation that is widely used in the formal analysis of rea...
read it

Sensor Synthesis for POMDPs with Reachability Objectives
Partially observable Markov decision processes (POMDPs) are widely used ...
read it

Lexicographic Ranking Supermartingales: An Efficient Approach to Termination of Probabilistic Programs
Probabilistic programs extend classical imperative programs with realva...
read it

Efficient Algorithms for Checking Fast Termination in VASS
Vector Addition Systems with States (VASS) consists of a finite state sp...
read it

Faster MonteCarlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Evolutionary graph theory studies the evolutionary dynamics in a populat...
read it

Optimizing Expectation with Guarantees in POMDPs (Technical Report)
A standard objective in partiallyobservable Markov decision processes (...
read it
Krishnendu Chatterjee
is this you? claim profile
Professor at Institute of Science and Technology Austria (IST Austria