Automated tail bound analysis for probabilistic recurrence relations

DOI10.1007/978-3-031-37709-9_2MaRDI QIDQ6535678zbMATH OpenFDO

Authors Yican Sun, Hongfei Fu, Krishnendu Chatterjee, Amir Kafshdar Goharshady

Publication date 1 February 2024

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-031-37709-9_2

Mathematics Subject Classification ID

Searching and sorting (68P10) Randomized algorithms (68W20)

Recommendations

• Probabilistic recurrence relations revisited
• (Probabilistic) recurrence relations revisited
• Automated recurrence analysis for almost-linear expected-runtime bounds
• Probabilistic recurrence relations
• Verified tail bounds for randomized programs

Cites work

• Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
• Automated recurrence analysis for almost-linear expected-runtime bounds
• Deciding polynomial-exponential problems
• Hoare's Selection Algorithm: A Markov Chain Approach
• scientific article; zbMATH DE number 1022658 (Why is no real title available?)
• scientific article; zbMATH DE number 1064597 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• scientific article; zbMATH DE number 2343061 (Why is no real title available?)
• Interactive theorem proving and program development. Coq'Art: the calculus of inductive constructions. Foreword by Gérard Huet and Christine Paulin-Mohring.
• Large Deviations for Quicksort
• New approaches for almost-sure termination of probabilistic programs
• Probabilistic recurrence relations
• Probabilistic recurrence relations revisited
• Probability Inequalities for Sums of Bounded Random Variables
• Probability with Martingales
• Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
• Stochastic invariants for probabilistic termination
• Tail probabilities for randomized program runtimes via martingales for higher moments
• Termination of nondeterministic probabilistic programs
• Verified tail bounds for randomized programs
• Weakest precondition reasoning for expected runtimes of randomized algorithms

Cited in

(4)

• Tail probabilities for randomized program runtimes via martingales for higher moments
• Derandomization with pseudorandomness
• Automating approximation analysis for Nash equilibria algorithms in two-player games
• Automated synthesis of decision lists for polynomial specifications over integers

This page was built for publication: Automated tail bound analysis for probabilistic recurrence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535678)