2026-08-16T05:00:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25122 2026-02-09T08:06:28Z ddc:004 open_access

Degrees of Second and Higher-Order Polynomials Lim, Donghyun Ziegler, Martin Logic in Computer Science Higher Order Program Analysis Asymptotic Type Theory Second-order polynomials generalize classical (=first-order) ones in allowing for additional variables that range over functions rather than values. We are motivated by their applications in higher-order computational complexity theory, extending for instance discrete classes (like P/FP or PSPACE/FPSPACE) to operators in Analysis [http://doi.org/10.1137/S0097539794263452], [http://doi.org/10.1145/2189778.2189780]. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic, etc. To similarly classify second-order polynomials, we (well-)define their degree by structural induction as an "arctic" first-order polynomial: a term/expression over integer variable D and operations + and ⋅ and binary max(). This generalized degree turns out to transform nicely under (now two kinds of) polynomial composition. As examples, we collect and determine the degrees of previous and new asymptotic analyses of algorithms and operators receiving function/oracle arguments. Then we motivate and introduce third-order polynomials and their degrees as arctic second-order polynomials, along with their transformations under three kinds of composition. Proceeding to fourth order and beyond yields a hierarchy, with characterization in Simply Typed Lambda Calculus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Donghyun Lim and Martin Ziegler 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.42 urn:nbn:de:0030-drops-251225 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.42 eng https://creativecommons.org/licenses/by/4.0/legalcode