Pith. sign in

REVIEW 4 major objections 5 minor 44 references

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the class of operations computable in constant time after O(N) preprocessing is invariant under changing preprocessing to any polynomial or to N^epsilon for any epsilon>0, and degenerates at N^{o(1)}.

desk verdict Solid, extensive theory with one genuinely broken inequality in the main robustness proof — fixable, but as written Theorem 5 doesn't go through. read the letter →

arxiv 2509.10188 v1 pith:G3TXGJSX submitted 2025-09-12 cs.DS cs.CC

Étienne Grandjean , Louis Jachiet This is my paper · ORCID
classification cs.DScs.CC MSC 68Q1568Q05
keywords CstPPconstanttimelinearpreprocessingRAMmodelrobustcomplexityclassinversefunctionsFibonaccifactorial
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies CstPP: operations on integers that can be answered in constant time by a RAM that first builds tables in O(N) time. It argues that the class is robust: the same operations are computed if preprocessing is reduced to N^epsilon (for any fixed epsilon>0) or increased to N^c (for any fixed c>1), provided the RAM has +, div, and mod as primitive operations. It also proves closure under composition and, for fast-growing functions, closure under inverse, so the inverses of Fibonacci and factorial are constant-time computable with linear preprocessing. If correct, CstPP is a stable, machine-independent notion of instant lookup after small preprocessing, and the same invariance carries over to linear-time and constant-delay enumeration classes.

What carries the argument

The Fundamental Lemma (Lemma 2) is the workhorse: if op is in CstPP(OP) and + is in OP, then any program over OP ∪ {op} can be faithfully simulated by a program over OP after a linear-time initialization. This makes every CstPP operation freely usable as a primitive. The preprocessing-time reductions rest on a radix (base) change trick: replace the reference integer N by its c-th root N_1 = floor(N^{1/c}), computed in O(N^{1/c}) time using only +, div, and mod; then operands < N^d are operands < N_1^{cd} for the original algorithm, so its O(N_1) preprocessing becomes O(N^{1/c}). The inverse-closure proof buckets candidates by floor(log_2 f(y)); for exponentially growing f each bucket has bou

What would settle it

Run Algorithm 3's computation of floor(N^{1/3}) for a large N (say 10^12) using only +, div, and mod, and check both the step count (about N^{1/3}) and the correctness of the translated loop condition; a failure there would undermine Theorem 5's claimed reduction of preprocessing time.

Watch

Extended reading notes

Core claim

The central claim is that the linear preprocessing bound in the definition of CstPP is not a delicate parameter. Theorems 5 and 6 show the class is unchanged when preprocessing is relaxed to N^c for any fixed c>1 or tightened to N^epsilon for any epsilon>0, as long as the primitive operations include +, div, and mod. By contrast, Theorem 8 shows that reducing preprocessing to N^{o(1)} collapses the class: even multiplication is no longer constant-time computable with addition only. The paper also shows that a constant-time procedure can be compressed to a single addition expression (a return instruction), and that an exponentially growing function and its inverse are in CstPP together (Theor

Load-bearing premise

The inverse-closure theorem leans on Proposition 1, imported from the companion paper [25], that floor(log_x y) and exponentiation are themselves in CstPP; if that membership result were flawed, the bucketing argument for inverse closure would need a replacement.

Editorial extensions

If this is right

  • CstPP can be defined with preprocessing time N^epsilon or N^c without changing the class, so the minimal preprocessing in the name is not a tight constraint.
  • The class is closed under composition and, for exponentially growing functions, under inverse, so complex operations like inverse factorial and inverse Fibonacci are constant-time computable after linear preprocessing.
  • The choice of primitive RAM operations, as long as addition is included (and for the preprocessing reductions also div and mod), does not affect the class, making it machine-independent.
  • The same invariance transfers to linear-time (LinTime) and constant-delay enumeration (CstDelay_lin) classes, so robustness arguments apply beyond the operation class itself.
  • Any constant-time computation in CstPP can be reduced to a single addition expression, meaning table lookups plus additions suffice as the on-line phase.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Proposition 1 (logarithm and exponentiation in CstPP) is verified, the inverse-closure theorem gives a general recipe: for any monotone exponentially growing f in CstPP, the inverse is also in CstPP, suggesting a broad symmetry between fast growth and fast lookup.
  • The degeneracy at N^{o(1)} preprocessing suggests a possible threshold effect: any positive polynomial preprocessing keeps CstPP stable, but sub-polynomial preprocessing breaks even multiplication; locating the exact threshold for other operation sets (e.g., +, div, mod) remains an open question.
  • The radix-change trick suggests a testable route to the open problem of whether the generalized root (x,y)->floor(x^{1/y}) is in CstPP, by iterating the same root computation with varying degrees.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the complexity class CstPP of operations computable in constant time after O(N) preprocessing on a RAM whose only primitive operation is addition, and shows that the class is robust: it is invariant under enlarging the primitive operation set, under increasing preprocessing time to any fixed polynomial, and under reducing preprocessing time to N^epsilon for any fixed positive epsilon < 1 (provided +, div, mod are available). The paper also proves closure under composition, closure under inverse for fast-growing functions, reductions of constant-time procedures to single addition expressions, and two minimality results showing that the class degenerates if preprocessing is subpolynomial or if addition is replaced by unary operations. The central claimed results are Theorems 5 and 6 on preprocessing-time robustness, Theorem 8 on minimality of linear preprocessing, and Theorem 11 on inverse closure.

Significance. If the results hold, they give a genuinely robust and extensive theory of constant-time computation with preprocessing. The paper is careful in several places: the cardinality argument in Theorem 8 is detailed and convincing, the use of lock-step simulation in Lemma 2 is principled, and the paper identifies precise open problems. The claim that the class is unchanged when preprocessing time is increased to N^c or reduced to N^epsilon, and that it degenerates at N^{o(1)}, is interesting and would substantially strengthen the framework initiated in the companion paper [25]. The proof of Theorem 8 in particular is a strong point: it is a rare lower-bound argument that does not rely on unproved assumptions about the RAM model. However, the main robustness theorem is not proven as written because of a false inequality in Section 5, and one load-bearing lemma is false as stated. These issues appear locally repairable, but they require a revised manuscript.

major comments (4)
  1. [Section 5.1, Lemma 4 and Theorem 5] The proof of Theorem 5 states that all operands x_i < N^d are less than (N_1)^{cd} with N_1 := floor(N^{1/c}). This inequality is false: floor(N^{1/c})^c <= N, so (N_1)^{cd} <= N^d. For c=2, d=1, N=15, we have N_1=3 and (N_1)^{cd}=9, while x=10 is a valid operand. Consequently Lemma 4(1), which claims that every X < N^d has a radix-N_1 representation in cd registers, is false as stated: 10 has base-3 representation 101, needing 3 digits, not cd=2. The operation phase of Theorem 5 overflows on operands in [N_1^{cd}, N^d). The proof can be repaired by taking N_1 := ceil(N^{1/c}), since then N <= N_1^c and hence N^d <= N_1^{cd}; the paper's own Algorithm 3 actually computes the ceiling, not the floor. But as written, the central preprocessing-time robustness theorem is not established.
  2. [Section 5.2, Theorem 6] The same floor/ceiling error appears in the proof of Theorem 6. The text sets N_1 := floor(N^{1/c}) and later asserts 'Noting that N^d <= (N_1)^{cd}', which is false for the same reason. The intended argument works with N_1 := ceil(N^{1/c}), since then (N_1)^{cd} >= N^d and, for fixed c, (N_1)^{cd} < (N^{1/c}+1)^{cd} <= N^{d+1} for N >= 2^{cd}. The proof should be corrected consistently in both directions of the robustness claim.
  3. [Lemma 4, Item 1] The proof of Lemma 4(1) is not justified within the RAM model. It says to set X_0 <- X and then repeatedly X_{i+1} <- X_i div N_1, as if X were a single integer variable. But operands X < N^d are represented in d base-N registers, and a register/variable may only contain O(N). The conversion from base N to base N_1 therefore requires a multi-register procedure, e.g. Horner's method in base N_1, and the constant-time nature of that procedure for fixed d and c is not proved. Since Theorem 5 depends on this conversion in its operation phase, this is a load-bearing gap. The intended construction is plausible, but it needs to be written out at the level of the multi-memory RAM conventions.
  4. [Section 8, Proposition 1] The forward direction of Theorem 11 uses floor(log_2 f(y)) to bucket the candidates for f^{-1}(x). This use is justified entirely by Proposition 1, which is stated as 'we admit here' with no proof in this manuscript. The paper claims to be readable independently, but Proposition 1 is load-bearing: if the logarithm membership result from [25] were unavailable, the inverse-closure theorem would not follow. The authors should either include a proof (or a precise pointer to the corresponding theorem of [25]) and state exactly which special case of Proposition 1 is needed. This is a dependency, not a circularity, but it is currently missing support within the manuscript.
minor comments (5)
  1. [Section 5.1, Algorithm 3] The comment in Algorithm 3 and the surrounding text say the algorithm computes x := floor(N^{1/3}). The loop invariant (x-1)^3 < N <= x^3 shows that it computes the ceiling, i.e. the least x with x^3 >= N. With the ceil correction to N_1 this is exactly what is needed, but the terminology should be fixed.
  2. [Section 4, one-digit division] The notation 'A_div[B^2-1]' and the description of the tables for (Br+x) div y and (Br+x) mod y are terse and ambiguous. The reader has to infer that these are one-dimensional arrays indexed by B*x+y. Please define the indexing convention explicitly, as is done for the multiplication table.
  3. [Abstract and throughout] The abstract uses the lower-case 'cstPP' while the body uses 'CstPP'. Please unify the notation.
  4. [Section 5.1, footnote] The footnote about avoiding circular dependencies in the comparison x^3 < N is unnecessarily contorted, since the theorem is stated for RAM(+,div,mod), where div and mod are primitive. Simplify or remove.
  5. [Section 8, proof of Theorem 11] The phrase 'there is an integer y satisfying the following inequalities' in the preprocessing part is not fully constructive as written: the completion of empty lists should specify how that y is found. The subsequent Claim 7 makes the size bound clear, but the construction of the completed lists should be made explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the CstPP robustness and closure results are derived from lemmas proved here and from independent companion-paper membership results, not from their own conclusions.

full rationale

The claimed derivation chain is not circular. CstPP is defined independently (Definition 5) and the key transfer theorem (Theorem 1) is proved in place via the Fundamental Lemma (Lemma 2), including the restoration argument that lets a constant-time subroutine be called repeatedly; it does not assume the class equality it establishes. The preprocessing-time robustness theorems (Theorems 5 and 6) use the standard root-replacement argument (replace reference integer N by N^{1/c}, converting operands between radices via Lemma 4); each direction constructs a machine for one side from a machine for the other rather than reusing the target equality. The inverse-closure theorem (Theorem 11) depends on Proposition 1, which is explicitly admitted from the companion paper [25] and states that exponentiation and logarithm belong to CstPP. This is a dependency on prior independent work by the same authors, not a reduction of Theorem 11 to its own statement; the paper does not define logarithm in terms of inverse closure or fit any parameter. The only passage that even names circular dependencies, the footnote to Algorithm 3, deliberately avoids them by using division rather than precomputed comparison tables before those tables exist, so it is evidence of non-circularity. Separately, the proof of Theorem 5 contains a numerical inequality error (N^d <= floor(N^{1/c})^{cd} is false and Lemma 4.1 overflows for operands between floor(N^{1/c})^{cd} and N^d); that is a correctness gap in the written proof, not a circularity, because the theorem's content is not encoded into its assumptions. No fitted value is relabeled a prediction, and no author-imported uniqueness theorem is used to force a choice.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper rests on its RAM model with O(N)-bounded registers, on the polynomial-restriction convention for operations, and on several background results: the Time Hierarchy Theorem (standard) and Proposition 1 (log and exponential in CstPP) admitted from the authors' companion work [25]. No free parameters or invented entities are introduced; all constants (d, c, B = floor(N^(1/2))) are universal or constructed, not fitted.

assumptions (4)
  • domain assumption The RAM model restricts register contents and addresses to O(N) (integers < cN) for a reference integer N, and inputs/outputs are read in base N with d digits.
    Section 2.1 defines the RAM with reference register N and registers < cN. All CstPP definitions and proofs operate in this bounded-register model; the paper shows O(log N)-bit registers are equivalent (Appendix 10.5).
  • domain assumption Operations are considered via polynomial restrictions op_{N,d,d'} with operands < N^d and outputs capped by N^{d'} with overflow.
    Definitions 1, 2, and 5 restrict attention to polynomial-size operands and outputs, a necessary condition for constant-time computation; all theorems are stated for this convention.
  • ad hoc to paper Proposition 1: the exponential function (x,y) -> x^y and its inverse (x,y) -> floor(log_x y) belong to CstPP, stated without proof (the paper says 'we admit here').
    Section 8, before Theorem 11, admits this result from the companion paper [25]. It is used in the forward direction of Theorem 11 to create lists indexed by floor(log_2 f(y)). If false, that implication fails.
  • standard math Time Hierarchy Theorem for RAMs (Cook-Reckhow) with time-constructible T(N) and decode-padding programs.
    Theorem 13 in Appendix 10.7 is stated with a sketch and used to prove Theorem 7 (non-polynomial preprocessing strictly expands CstPP).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class." pith.science (2026). https://pith.science/paper/G3TXGJSX

@misc{pith2026250910188,
  author       = {Pith},
  title        = {Pith review of: Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G3TXGJSX}},
  note         = {Machine review of arXiv:2509.10188}
}
abstract

In this paper, we study the class $\mathtt{cstPP}$ of operations $\mathtt{op}: \mathbb{N}^k\to\mathbb{N}$, of any fixed arity $k\ge 1$, satisfying the following property: for each fixed integer $d\ge 1$, there exists an algorithm for a RAM machine which, for any input integer $N\ge 2$, - pre-computes some tables in $O(N)$ time, - then reads $k$ operands $x_1,\ldots,x_k<N^d$ and computes $\mathtt{op}(x_1,\dots,x_k)$ in constant time. We show that the $\mathtt{cstPP}$ class is robust and extensive and satisfies several closure properties. It is invariant depending on whether the set of primitive operations of the RAM is $\{+\}$, or $\{+,-,\times,\mathtt{div},\mathtt{mod}\}$, or any set of operations in $\mathtt{cstPP}$ provided it includes $+$. We prove that the $\mathtt{cstPP}$ class is closed under composition and, for fast-growing functions, is closed under inverse. We also show that in the definition of $\mathtt{cstPP}$ the constant-time procedure can be reduced to a single return instruction. Finally, we establish that linear preprocessing time is not essential in the definition of the $\mathtt{cstPP}$ class: this class is not modified if the preprocessing time is increased to $O(N^c)$, for any fixed $c>1$, or conversely, is reduced to $N^{\varepsilon}$, for any positive $\varepsilon<1$ (provided the set of primitive operation includes $+$, $\mathtt{div}$ and $\mathtt{mod}$). To complete the picture, we demonstrate that the $\mathtt{cstPP}$ class degenerates if the preprocessing time reduces to $N^{o(1)}$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 4 linked inside Pith

  1. [25]

    Which arithmetic operations can be performed in constant time in the RAM model with addition?CoRR, abs/2206.13851, 2022

    Etienne Grandjean and Louis Jachiet. Which arithmetic operations can be performed in constant time in the RAM model with addition?CoRR, abs/2206.13851, 2022

    arXiv 2022

  2. [1]

    Aho, John E

    Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974

    1974

  3. [2]

    A circuit-based ap- proach to efficient enumeration

    Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based ap- proach to efficient enumeration. In44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 111:1–111:15, 2017

    2017

  4. [3]

    Dynamic membership for regular languages.CoRR, abs/2102.07728, 2021

    Antoine Amarilli, Louis Jachiet, and Charles Paperman. Dynamic membership for regular languages.CoRR, abs/2102.07728, 2021. 34

    arXiv 2021

  5. [4]

    Static dictionaries on ac 0 rams: Query time theta(sqrt(log n/log log n)) is necessary and sufficient

    Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup. Static dictionaries on ac 0 rams: Query time theta(sqrt(log n/log log n)) is necessary and sufficient. In37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 441–450. IEEE Computer Society, 1996

    1996

  6. [5]

    Fusion trees can be implemented with ac0 instructions only.Theor

    Arne Andersson, Peter Bro Miltersen, and Mikkel Thorup. Fusion trees can be implemented with ac0 instructions only.Theor. Comput. Sci., 215(1-2):337–344, 1999

    1999

  7. [6]

    On acyclic conjunctive queries and constant delay enumeration

    Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes...

    2007

  8. [7]

    Computing the jth solution of a first-order query.ITA, 42(1):147–164, 2008

    Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Fr´ ed´ eric Olive. Computing the jth solution of a first-order query.ITA, 42(1):147–164, 2008

    2008

Show all 44 references
  1. [8]

    Constant delay enumeration for conjunctive queries: a tutorial.ACM SIGLOG News, 7(1):4–33, 2020

    Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial.ACM SIGLOG News, 7(1):4–33, 2020

    2020

  2. [9]

    Answering conjunctive queries under updates.CoRR, abs/1702.06370, 2017

    Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates.CoRR, abs/1702.06370, 2017

    2017 arXiv

  3. [10]

    Answering FO+MOD queries under updates on bounded degree databases.ACM Trans

    Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering FO+MOD queries under updates on bounded degree databases.ACM Trans. Database Syst., 43(2):7:1–7:32, 2018

    2018

  4. [11]

    Tight fine-grained bounds for direct access on join queries

    Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. In Leonid Libkin and Pablo Barcel´ o, editors,PODS ’22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022, pages 427–

    2022

  5. [12]

    Tight fine-grained bounds for direct access on join queries.CoRR, abs/2201.02401, 2022

    Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries.CoRR, abs/2201.02401, 2022

    2022 arXiv

  6. [13]

    Enumeration complexity of conjunctive queries with func- tional dependencies

    Nofar Carmeli and Markus Kr¨ oll. Enumeration complexity of conjunctive queries with func- tional dependencies. In Benny Kimelfeld and Yael Amsterdamer, editors,21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, vol- ume 98 ofLIPIc...

    2018

  7. [14]

    Tractable orders for direct access to ranked answers of conjunctive queries

    Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. ACM Trans. Database Syst., 48(1):1:1–1:45, 2023

    2023

  8. [15]

    Cook and Robert A

    Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines.J. Comput. Syst. Sci., 7(4):354–375, 1973

    1973

  9. [16]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms, 3rd Edition. MIT Press, 2009

    2009

  10. [17]

    A knowledge compilation map.J

    Adnan Darwiche and Pierre Marquis. A knowledge compilation map.J. Artif. Intell. Res., 17:229–264, 2002

    2002

  11. [18]

    C. J. Date.An Introduction to Database Systems, 3rd Edition. Addison-Wesley, 1981

    1981

  12. [19]

    Dexter, Patrick Doyle, and Yuri Gurevich

    Scott D. Dexter, Patrick Doyle, and Yuri Gurevich. Gurevich abstract state machines and schoenhage storage modification machines.J. Univers. Comput. Sci., 3(4):279–303, 1997

    1997

  13. [20]

    Fine-grained complexity analysis of queries: From decision to counting and enumeration

    Arnaud Durand. Fine-grained complexity analysis of queries: From decision to counting and enumeration. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors,Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, Ju...

    2020

  14. [21]

    First-order queries on structures of bounded degree are computable with constant delay.ACM Trans

    Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay.ACM Trans. Comput. Log., 8(4):21, 2007. 35

    2007

  15. [22]

    Direct access for answers to conjunctive queries with aggregation

    Idan Eldar, Nofar Carmeli, and Benny Kimelfeld. Direct access for answers to conjunctive queries with aggregation. In Graham Cormode and Michael Shekelyan, editors,27th Inter- national Conference on Database Theory, ICDT 2024, March 25-28, 2024, Paestum, Italy, volume 290 ofLI...

    2024

  16. [23]

    Linear functional classes over cel- lular automata

    Ana¨ el Grandjean, Ga´ etan Richard, and V´ eronique Terrier. Linear functional classes over cel- lular automata. In Enrico Formenti, editor,Proceedings 18th international workshop on Cel- lular Automata and Discrete Complex Systems and 3rd international symposium Journ´ ees A...

    2012

  17. [24]

    Sorting, linear time and the satisfiability problem.Ann

    Etienne Grandjean. Sorting, linear time and the satisfiability problem.Ann. Math. Artif. Intell., 16:183–236, 1996

    1996

  18. [26]

    Machine-independent characterizations and complete problems for deterministic linear time.SIAM J

    Etienne Grandjean and Thomas Schwentick. Machine-independent characterizations and complete problems for deterministic linear time.SIAM J. Comput., 32(1):196–230, 2002

    2002

  19. [27]

    Evolving algebras: an attempt to discover semantics

    Yuri Gurevich. Evolving algebras: an attempt to discover semantics. In Grzegorz Rozenberg and Arto Salomaa, editors,Current Trends in Theoretical Computer Science - Essays and Tutorials, volume 40 ofWorld Scientific Series in Computer Science, pages 266–292. World Scientific, 1993

    1993

  20. [28]

    Pitman, 1984

    Ellis Horowitz and Sartaj Sahni.Fundamentals of data structures in Pascal. Pitman, 1984

    1984

  21. [29]

    Johnson, Christos H

    David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets.Inf. Process. Lett., 27(3):119–123, 1988

    1988

  22. [30]

    Knuth.The Art of Computer Programming, Volume II: Seminumerical Algo- rithms

    Donald E. Knuth.The Art of Computer Programming, Volume II: Seminumerical Algo- rithms. Addison-Wesley, 1969

    1969

  23. [31]

    Compile! In Blai Bonet and Sven Koenig, editors,Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 4112–4118

    Pierre Marquis. Compile! In Blai Bonet and Sven Koenig, editors,Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 4112–4118. AAAI Press, 2015

    2015

  24. [32]

    Papadimitriou.Computational complexity

    Christos H. Papadimitriou.Computational complexity. Addison-Wesley, 1994

    1994

  25. [33]

    Pope and Marvin L

    David A. Pope and Marvin L. Stein. Multiple precision arithmetic.Commun. ACM, 3(12):652–654, 1960

    1960

  26. [34]

    Springer, 2019

    Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, and Roman Dementiev.Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019

    2019

  27. [35]

    Algebraic and logical characterizations of deterministic linear time classes

    Thomas Schwentick. Algebraic and logical characterizations of deterministic linear time classes. In R¨ udiger Reischuk and Michel Morvan, editors,STACS 97, 14th Annual Sympo- sium on Theoretical Aspects of Computer Science, L¨ ubeck, Germany, February 27 - March 1, 1997, Proce...

    1997

  28. [36]

    A glimpse on constant delay enumeration (invited talk)

    Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In31st Inter- national Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, pages 13–27, 2014

    2014

  29. [37]

    Shepherdson and Howard E

    John C. Shepherdson and Howard E. Sturgis. Computability of recursive functions.J. ACM, 10(2):217–255, 1963

    1963

  30. [38]

    Enumeration complexity.Bull

    Yann Strozecki. Enumeration complexity.Bull. EATCS, 129, 2019

    2019

  31. [39]

    Language recognition by cellular automata

    V´ eronique Terrier. Language recognition by cellular automata. In Grzegorz Rozenberg, Thomas B¨ ack, and Joost N. Kok, editors,Handbook of Natural Computing, pages 123–158. Springer, 2012

    2012

  32. [40]

    On RAM priority queues.SIAM J

    Mikkel Thorup. On RAM priority queues.SIAM J. Comput., 30(1):86–109, 2000

    2000

  33. [41]

    Ullman and Jennifer Widom.A First Course in Database Systems

    Jeffrey D. Ullman and Jennifer Widom.A First Course in Database Systems. Prentice-Hall, 1997. 36

    1997

  34. [42]

    Constant time enumeration by amortization

    Takeaki Uno. Constant time enumeration by amortization. In Frank Dehne, J¨ org-R¨ udiger Sack, and Ulrike Stege, editors,Algorithms and Data Structures - 14th International Sym- posium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, volume 9214 ofLecture Notes...

    2015

  35. [43]

    Texts in Theoretical Computer Science

    Heribert Vollmer.Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999

    1999

  36. [44]

    Joachim von zur Gathen and J¨ urgen Gerhard.Modern Computer Algebra (3. ed.). Cam- bridge University Press, 2013

    2013

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.