---
res:
  bibo_abstract:
  - "We study the problem of developing efficient approaches for proving\r\nworst-case
    bounds of non-deterministic recursive programs. Ranking functions\r\nare sound
    and complete for proving termination and worst-case bounds of\r\nnonrecursive
    programs. First, we apply ranking functions to recursion,\r\nresulting in measure
    functions. We show that measure functions provide a sound\r\nand complete approach
    to prove worst-case bounds of non-deterministic recursive\r\nprograms. Our second
    contribution is the synthesis of measure functions in\r\nnonpolynomial forms.
    We show that non-polynomial measure functions with\r\nlogarithm and exponentiation
    can be synthesized through abstraction of\r\nlogarithmic or exponentiation terms,
    Farkas' Lemma, and Handelman's Theorem\r\nusing linear programming. While previous
    methods obtain worst-case polynomial\r\nbounds, our approach can synthesize bounds
    of the form $\\mathcal{O}(n\\log n)$\r\nas well as $\\mathcal{O}(n^r)$ where $r$
    is not an integer. We present\r\nexperimental results to demonstrate that our
    approach can obtain efficiently\r\nworst-case bounds of classical recursive algorithms
    such as (i) Merge-Sort, the\r\ndivide-and-conquer algorithm for the Closest-Pair
    problem, where we obtain\r\n$\\mathcal{O}(n \\log n)$ worst-case bound, and (ii)
    Karatsuba's algorithm for\r\npolynomial multiplication and Strassen's algorithm
    for matrix multiplication,\r\nwhere we obtain $\\mathcal{O}(n^r)$ bound such that
    $r$ is not an integer and\r\nclose to the best-known bounds for the respective
    algorithms.@eng"
  bibo_authorlist:
  - 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: Hongfei
      foaf_name: Fu, Hongfei
      foaf_surname: Fu
  - 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.1145/3339984
  bibo_issue: '4'
  bibo_volume: 41
  dct_date: 2019^xs_gYear
  dct_identifier:
  - UT:000564108400001
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Non-polynomial worst-case analysis of recursive programs@
...