Complexity and Real Computation Laboratory

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

--- home [2023-03-17] – [Mission] Martin Ziegler
+++ home [2026-08-10] (current) – [Mission] Martin Ziegler
@@ Line 2: / Line 2: @@
 ===== Motivation =====
-Digital Computers naturally process discrete data, such as bits or integers or strings or graphs. From bits to advanced data structures, from a first semi-conducting transistor to billions in wafer-scale integration, from individual Boolean connectives to entire CPU circuits, from kB to TB memories, from 10^2 to 10^9 instructions per second, from assembly code to high-level programming languages: \\
+Digital Computers naturally process discrete data, such as bits or integers or strings or graphs. From bits to advanced data structures, from a first semi-conducting transistor to billions in wafer-scale integration, from individual Boolean connectives to entire CPU circuits, from kB to TB memories, from 10<sup>2</sup> to 10<sup>9</sup> instructions per second, from assembly code to high-level programming languages: \\
 the success story of digital computing arguably is due to (1) hierarchical layers of abstraction and (2) the ultimate reliability of each layer for the next one to build on ― for processing discrete data.
@@ Line 17: / Line 17: @@
 Deviations between mathematical structures and their hardware counterparts are common also in the discrete realm,
-such as the “integer” wraparound 255+1=0 occurring in bytes that led to the ”Nuclear Gandhi'' programming bug.
+such as the “integer” wraparound 255+1=0 occurring in bytes that led to the //[[https://en.wikipedia.org/wiki/Nuclear_Gandhi|Nuclear Gandhi]]// programming bug.
-Similarly, deviations between exact and approximate continuous data underlie infamous failures such as the Ariane 501 flight V88 or the Sleipner-A oil platform.
+Similarly, deviations between exact and approximate continuous data underlie infamous failures such as the  [[https://en.wikipedia.org/wiki/Ariane_flight_V88|Ariane 501 flight V88]] or the [[https://en.wikipedia.org/wiki/Sleipner_A|Sleipner-A oil platform]].
-Nowadays high-level programming languages (such as Java or Python) provide a user data type (called for example BigInt or mpz_t) that fully agrees with mathematical integers, simulated in software using a variable number of hardware bytes.
+Nowadays high-level programming languages (such as Java or Python) provide a user data type (called for example ''BigInt'' or ''mpz_t'') that fully agrees with mathematical integers, simulated in software using a variable number of hardware bytes.
 This additional layer of abstraction provides the reliability for advanced discrete data types (such as weighted or labelled graphs) to build on, as mentioned above.
@@ Line 37: / Line 37: @@
 [[https://slee3379.math.gatech.edu/|Seokbin Lee]] has designed and analyzed and implemented a [[https://github.com/realcomputation/irramplus/tree/master/GRASSMANN|reliable variant of the Grassmannian]], i.e., the orthomodular lattice of subspaces of some fixed finite-dimensional Euclidean or unitary vector space.
-  * Infinite sequences of real numbers arise as elements of ℓp spaces; and as coefficients to analytic function germs.
+  * Infinite sequences of real numbers arise as elements of ℓ<sup>p</sup> spaces; and as coefficients to analytic function germs.
 [[http://www.holgerthies.com/|Holger Thies]] has implemented [[https://github.com/holgerthies|analytic functions for reliably solving ODEs and PDEs]].
@@ Line 45: / Line 45: @@
 Coding theory of discrete data is well-established since Claude Shannon’s famous work.
 Encoding real numbers as infinite sequences of bits is non-trivial: the binary expansion for example renders addition uncomputable.
-  *  [[https://www.donghyunlim.com/|Donghyun Lim]] in [[http://realcomputation.asia/THESES/19Donghyun.pdf|his MSc Thesis]] has investigated encoding more advanced (such as function) spaces;
+  *  Matthias Schröder has made [[https://dblp.org/pid/12/7010.html|important contributions]] to the qualitative coding theory of continuous data. [[https://www.donghyunlim.com/|Donghyun Lim]] in [[https://library.kaist.ac.kr/search/ctlgSearch/posesn/view.do?bibctrlno=875473|his MSc Thesis]] has investigated quantitative properties of encoding abstract (such as function) spaces; see also the preprint [[https://arxiv.org/abs/2002.04005|arXiv:2002.04005]] and the journal version [[https://doi.org/10.1145/3705609|doi:10.1145/3705609]].
-see also the [[https://arxiv.org/abs/2002.04005|preprint arXiv:2002.04005]].
+  *  [[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.
+  *  [[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