Complexity and Real Computation Laboratory

This shows you the differences between two versions of the page.

--- home [2026-08-10] – [Mission] Martin Ziegler
+++ home [2026-08-10] (current) – [Mission] Martin Ziegler
@@ Line 49: / Line 49: @@
   *  [[https://www.comp.nus.edu.sg/programmes/pg/phdcs/directory/|Ivan Koswara]] and [[http://www.lix.polytechnique.fr/Labo/Gleb.POGUDIN/|Gleb Pogudin]] and [[https://www.researchgate.net/profile/Svetlana-Selivanova|Svetlana Selivanova]] have [[http://cs4contidat.eu/yjcom101727.pdf|related the bit-complexity intrinsic to approximate solutions of linear partial differential equations]] to discrete complexity classes #P and PSPACE. This complements [[https://doi.org/10.1007/s00037-010-0286-0|investigations]] of ordinary but non-linear differential equations.
-  * Previous works [[http://doi.org/10.1137/S0097539794263452|doi:10.1137/S0097539794263452]] and [http://doi.org/10.1145/2189778.2189780|doi:10.1145/2189778.2189780] have generalized classical polynomials to higher types, such as operators in analysis, in terms of so-called second-order polynomials. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic etc. In order to similarly classify second-order polynomials, [[https://doi.org/10.4230/LIPIcs.FSTTCS.2025.42|doi:10.4230/LIPIcs.FSTTCS.2025.42]] defines their degree to be an 'arctic' first-order polynomial (namely a term/expression over variable D and operations + and × and max). This degree turns out to transform as nicely under (now two kinds of) polynomial composition as the ordinary one. We also establish a normal form and semantic uniqueness for second-order polynomials. Then we define the degree of a third-order polynomial to be an arctic second-order polynomial, and establish its transformation under three kinds of composition.
+  * Previous works [[http://doi.org/10.1137/S0097539794263452|doi:10.1137/S0097539794263452]] and [[http://doi.org/10.1145/2189778.2189780|doi:10.1145/2189778.2189780]] have generalized classical polynomials to higher types, such as operators in analysis, in terms of so-called second-order polynomials. The degree subclassifies ordinary polynomial growth into linear, quadratic, cubic etc. In order to similarly classify second-order polynomials, [[https://doi.org/10.4230/LIPIcs.FSTTCS.2025.42|doi:10.4230/LIPIcs.FSTTCS.2025.42]] defines their degree to be an 'arctic' first-order polynomial (namely a term/expression over variable D and operations + and × and max). This degree turns out to transform as nicely under (now two kinds of) polynomial composition as the ordinary one. We also establish a normal form and semantic uniqueness for second-order polynomials. Then we define the degree of a third-order polynomial to be an arctic second-order polynomial, and establish its transformation under three kinds of composition.
-  * [[http://informatik.uni-trier.de/~brausse/personal/index.xhtml|Franz Brauße]] and [[https://www.maastrichtuniversity.nl/pieter.collins|Pieter Collins]] envision a Computer <del>Algebra</del>//Analysis// System
+  *  [[https://doi.org/10.1007/978-3-032-31348-5_9|What is a polynomial-time computable L^2 (aka square-integrable) function?]] Finding a 'good' definition is prerequisite to complexity investigations of partial differential equations beyond classical solutions [[https://doi.org/10.23638/LMCS-13(3:21)2017|doi:10.23638/LMCS-13(3:21)2017]]; see also [[https://doi.org/10.1007/978-3-032-09645-6_2|doi:10.1007/978-3-032-09645-6_2]].
+  * [[http://informatik.uni-trier.de/~brausse/personal/index.xhtml|Franz Brauße]] and [[https://www.maastrichtuniversity.nl/pieter.collins|Pieter Collins]] envision a Computer <del>Algebra</del>//Analysis// [[https://doi.org/10.1007/978-3-031-14788-3_5|System]].
+  * [[https://www.b-tu.de/fg-theoretische-informatik/team/lehrstuhlinhaber|Klaus Meer]] initiates [[https://doi.org/10.1007/978-3-031-63742-1_5|Software Testing in Computable Analysis]].
 ===== References =====

Differences