---
res:
  bibo_abstract:
  - "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 tail probability Pr[T≥κ], i.e., the probability that the randomized runtime
    T of the PRR exceeds κ. Our focus is the formal analysis of tail bounds that aims
    at finding a tight asymptotic upper bound u≥Pr[T≥κ]. To address this problem,
    the classical and most well-known approach is the cookbook method by Karp (JACM
    1994), while other approaches are mostly limited to deriving tail bounds of specific
    PRRs via involved custom analysis.\r\nIn this work, we propose a novel approach
    for deriving the common exponentially-decreasing tail bounds for PRRs whose preprocessing
    time and random passed sizes observe discrete or (piecewise) uniform distribution
    and whose recursive call is either a single procedure call or a divide-and-conquer.
    We first establish a theoretical approach via Markov’s inequality, and then instantiate
    the theoretical approach with a template-based algorithmic approach via a refined
    treatment of exponentiation. Experimental evaluation shows that our algorithmic
    approach is capable of deriving tail bounds that are (i) asymptotically tighter
    than Karp’s method, (ii) match the best-known manually-derived asymptotic tail
    bound for QuickSelect, and (iii) is only slightly worse (with a loglogn factor)
    than the manually-proven optimal asymptotic tail bound for QuickSort. Moreover,
    our algorithmic approach handles all examples (including realistic PRRs such as
    QuickSort, QuickSelect, DiameterComputation, etc.) in less than 0.1 s, showing
    that our approach is efficient in practice.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Yican
      foaf_name: Sun, Yican
      foaf_surname: Sun
  - foaf_Person:
      foaf_givenName: Hongfei
      foaf_name: Fu, Hongfei
      foaf_surname: Fu
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Amir Kafshdar
      foaf_name: Goharshady, Amir Kafshdar
      foaf_surname: Goharshady
      foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-1702-6584
  bibo_doi: 10.1007/978-3-031-37709-9_2
  bibo_volume: 13966
  dct_date: 2023^xs_gYear
  dct_identifier:
  - UT:001310805600002
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9783031377082
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: Automated tail bound analysis for probabilistic recurrence relations@
...
