15 citations · 66 across the 23 of their papers we have counts for
4 papers · 1 filter
Automated Tail Bound Analysis for Probabilistic Recurrence Relations
Yican Sun, Hongfei Fu, Krishnendu Chatterjee +1
Probabilistic recurrence relations (PRRs) are a standard formalism for describing the runtime of a randomized algorithm. Given a PRR and a time limit , we consider the classical…
Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
Giovanna K. Conrado, Amir K. Goharshady, Harshit J. Motwani +1
We present efficient combinatorial parameterized algorithms for several classical graph-based counting problems in computational chemistry, including (i) Kekule structures, (ii) th…
Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
Ali Asadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady +2
Discrete-time Markov Chains (MCs) and Markov Decision Processes (MDPs) are two standard formalisms in system analysis. Their main associated quantitative objectives are hitting pro…
Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen +1
Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointer…