Pith. sign in

REVIEW 2 minor 54 references

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?

T0 review · 0 major / 2 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Fitting finite input-output samples to logic-defined function classes over infinite structures has decidable complexity in common cases.

desk verdict The paper isolates complexities for exact/approximate fitting of logic-defined classes over decidable infinite structures like the reals and Presburger arithmetic, with a focus on query-based fittability checks. read the letter →

arxiv 2606.01107 v1 pith:IJLAUWJW submitted 2026-05-31 cs.LO cs.LGmath.LO

Michael Benedikt , Alessio Mansutti This is my paper · ORCID
classification cs.LOcs.LGmath.LO
keywords fittingproblemslogic-basedhypothesisclassesdecidablestructuresPresburgerarithmeticrealorderedfieldcomputationalcomplexityquerylanguages
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 examines fitting problems, where one checks if a finite sample of inputs and outputs can be produced by some function in a logic-based class. It focuses on classes defined over decidable infinite structures such as the ordered field of real numbers and Presburger arithmetic on integers. The authors determine the complexity of deciding whether such a function exists, exactly or approximately, and identify cases where queries in a natural query language over the sample can decide fittability. A sympathetic reader would care because this links logical definability with the feasibility of learning or hypothesis fitting in infinite domains.

What carries the argument

Fitting problems for logically-defined hypothesis classes over infinite structures, decided via complexity analysis and natural query languages.

What would settle it

A concrete falsifier would be exhibiting a sample over the reals where no fitting function exists according to the logic class but the query procedure incorrectly says it does, or vice versa.

Watch

Extended reading notes

Core claim

We study fitting problems for logically-defined classes in common decidable structures like the real ordered field and Presburger arithmetic, isolating the complexity of these fitting problems with particular attention to cases where queries in a natural query language over the sample can determine whether a sample is fittable.

Load-bearing premise

The structures under consideration are common decidable structures such as the real ordered field and Presburger arithmetic for which the relevant logical theories admit effective decision procedures.

Editorial extensions

If this is right

  • If the complexity is isolated for these structures, then fitting can be automated for samples in real arithmetic and integer linear arithmetic.
  • Query languages can replace full search for fittability in many cases.
  • Broader classes defined via combinatorial or model-theoretic properties also admit complexity characterizations.

Reading between the lines

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

  • These results may apply to other decidable structures beyond those mentioned.
  • Connections could exist to learning theory in infinite domains where exact fitting is required.
  • Approximate fitting might lead to different complexity results not fully explored here.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The paper studies fitting problems (exact and approximate) for hypothesis classes defined by logical formulas over infinite structures, with a focus on decidable ones such as the real ordered field and Presburger arithmetic. It isolates the computational and descriptive complexity of these fitting problems and pays particular attention to cases in which fittability of a sample can be decided by queries expressed in a natural query language over the sample. The analysis is extended to broader hypothesis classes defined via combinatorial or model-theoretic properties.

Significance. If the complexity isolations hold, the work supplies a systematic complexity-theoretic account of fitting for logically defined classes over infinite domains, exploiting the decidability of the target theories. The query-language approach to fittability offers a concrete bridge between model-theoretic decidability and algorithmic learning procedures. The generalization to combinatorial and model-theoretic classes broadens the applicability beyond the two concrete structures.

minor comments (2)
  1. The abstract asserts that complexities are isolated but supplies no concrete complexity classes or proof outlines; adding one illustrative result (e.g., a PSPACE or NP bound for a specific structure) would improve readability without altering the technical content.
  2. The notion of a 'natural query language' over the sample is central yet introduced only informally in the abstract; an early, self-contained definition (perhaps in §2 or §3) would help readers track the subsequent reductions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. No major comments were provided in the report, so there are no specific points requiring point-by-point response or revision at this stage.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation self-contained via external decidability results

full rationale

The paper isolates computational and descriptive complexity of exact/approximate fitting for logic-defined hypothesis classes over decidable structures (real ordered field, Presburger arithmetic) and model-theoretic classes, emphasizing fittability via natural query languages over samples. It invokes standard effective decision procedures for the target theories as an external, pre-existing fact to obtain the complexity results; these procedures are not derived or fitted within the paper. No equations define a quantity in terms of itself, no parameters are fitted to a data subset and then relabeled as a prediction, and no load-bearing premise reduces to a self-citation chain. The combinatorial and model-theoretic extensions inherit decidability benefits from outside sources without internal reduction. The work is therefore self-contained against external benchmarks.

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

No specific free parameters, axioms, or invented entities are mentioned in the abstract; the work appears to rely on standard decidability assumptions for the cited structures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?." pith.science (2026). https://pith.science/paper/IJLAUWJW

@misc{pith2026260601107,
  author       = {Pith},
  title        = {Pith review of: How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IJLAUWJW}},
  note         = {Machine review of arXiv:2606.01107}
}
read the original abstract

We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.

Figures

Figures reproduced from arXiv: 2606.01107 by the authors.

Figure 1
Figure 1. Example of the initial segment 𝐼𝑛 and its subsets, for ℓ = 2 and 𝑛 = 2. tuples in TupleTriples𝑛 are triples of the form TupleOf0 (𝑖), TupleOf1 (𝑖), TupleOf2 (𝑖) where 𝑖 is a vertex of 𝐺. We encode 𝐺 with the 𝐼-based embedded finite model 𝑇 𝐼 𝐺 that interpret the relation 𝑇 as follows: 𝑇 contains a 6ℓ-tuple 𝑤® if and only if there is an edge (𝑖, 𝑗) ∈ 𝐸 such that 𝑤® = (TupleOf0 (𝑖), TupleOf1 (𝑖), TupleOf2 (𝑖), TupleOf… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 1 canonical work pages

  1. [1]

    Abrahamsen, L

    M. Abrahamsen, L. Kleist, and T. Miltzow. Training Neural Networks is ER-complete. InNeurIPS, 2021

    2021

  2. [2]

    Allender, P

    E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen. On the complexity of numerical analysis.SIAM J. Comput., 2009

    2009

  3. [3]

    Anderson and M

    A. Anderson and M. Benedikt. From learnable objects to learnable random objects, 2025. https://arxiv.org/abs/2504.00847

    work page arXiv 2025

  4. [4]

    M. Anthony. Some connections between learning and optimization.Discrete Applied Mathematics, 144(1):17–26, 2004

    2004

  5. [5]

    Arora, A

    R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In ICLR, 2018

    2018

  6. [6]

    S. Basu, R. Pollack, and M.-F. Roy.Existential Theory of the Reals, pages 465–492. Springer, 2003

    2003

  7. [7]

    O. V. Belegradek, A. P. Stolboushkin, and M. A. Taitslin. Extended order-generic queries.Annals of Pure and Applied Logic, 97(1):85–125, 1999

    1999

  8. [8]

    Ben Yaacov

    I. Ben Yaacov. On theories of random variables.Israel Journal of Mathematics, 194:957–1012, 2013

    2013

Show all 54 references
  1. [9]

    Ben Yaacov and H

    I. Ben Yaacov and H. J. Keisler. Randomizations of models as metric structures.Confluentes Mathematici, 1(2):197–223, 2009

    2009

  2. [10]

    Benedikt

    M. Benedikt. Generalizing finite model theory. In V. Stoltenberg-Hansen and J. Väänänen, editors,Logic Colloquium ’03, page 3–24. Cambridge University Press, 2006

    2006

  3. [11]

    Benedikt and E

    M. Benedikt and E. Hrushovski. Embedded finite models beyond restricted quantifier collapse. InLICS, 2023

    2023

  4. [12]

    Benedikt and L

    M. Benedikt and L. Libkin. Relational queries over interpreted structures.J. ACM, 47(4):644–680, July 2000

    2000

  5. [13]

    Benedikt, L

    M. Benedikt, L. Libkin, T. Schwentick, and L. Segoufin. Definable relations and first-order query languages over strings. J. ACM, 50(5):694–751, 2003

    2003

  6. [14]

    Bertschinger, C

    D. Bertschinger, C. Hertrich, P. Jungeblut, T. Miltzow, and S. Weber. Training Fully Connected Neural Networks is∃R -Complete. InNeurIPS, 2023

    2023

  7. [15]

    L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines.Bulletin of the American Mathematical Society, 21(1):1–46, 1989

    1989

  8. [16]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension.J. ACM, 36(4):929–965, 1989

    1989

  9. [17]

    Bruyère, G

    V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire. Logic and 𝑝-recognizable sets of integers.Bull. Belg. Math. Soc. Simon Stevin, 1(2):191–238, 1994

    1994

  10. [18]

    R. J. Büchi. Weak second-order arithmetic and finite automata.Math. Logic Quart., 6(1-6):66–92, 1960

    1960

  11. [19]

    C. C. Chang and H. J. Keisler.Model theory. North-Holland, third edition, 1990

    1990

  12. [20]

    Carathéodory

    C. Carathéodory. Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. Mathematische Annalen, 64(1), 1907

    1907

  13. [21]

    Chernikov and P

    A. Chernikov and P. Simon. Externally definable sets and dependent pairs II.Transactions of the American Mathematical Society, 367(7):5217–5235, 2015

    2015

  14. [22]

    R. Fagin. Probabilities on finite models.Journal of Symbolic Logic, 41(1):50–58, 1976

    1976

  15. [23]

    Figueira, A

    D. Figueira, A. Jez, and A. W. Lin. Data path queries over embedded graph databases. InPODS, 2022

    2022

  16. [24]

    Flum and M

    J. Flum and M. Ziegler. Pseudo-finite homogeneïty and saturation.The Journal of Symbolic Logic, 64(4):1689–1699, 1999

    1999

  17. [25]

    Froese and C

    V. Froese and C. Hertrich. Training neural networks is NP-hard in fixed dimension. InNeurIPS, 2023

    2023

  18. [26]

    M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy.Math. Syst. Theory, 17(1):13–27, 1984

    1984

  19. [27]

    S. Goel, A. R. Klivans, P. Manurangsi, and D. Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. InITCS, 2021

    2021

  20. [28]

    E. Grädel. Automatic structures: Twenty years later. InLICS, 2020

    2020

  21. [29]

    Grandjean

    E. Grandjean. Complexity of the first-order theory of almost all finite structures.Information and Control, 57(2):180–204, 1983

    1983

  22. [30]

    Grohe and M

    M. Grohe and M. Ritzert. Learning first-order definable concepts over structures of small degree. InLICS, 2017

    2017

  23. [31]

    Grötschel, L

    M. Grötschel, L. Lovász, and A. Schrijver.Geometric Algorithms and Combinatorial Optimization, volume 2 ofAlgorithms and Combinatorics. Springer, 1988

    1988

  24. [32]

    Hankala, M

    T. Hankala, M. Hannula, J. Kontinen, and J. Virtema. Complexity of neural network training and ETR: extensions with effectively continuous functions. InAAAI, 2023. How (and when) can you fit examples to logic-based hypothesis classes over infinite structures? 17

    2023

  25. [33]

    Hieronymi, T

    P. Hieronymi, T. Nell, and E. Walsberg. Wild theories with o-minimal open core.Annals of Pure and Applied Logic, 169(2):146–163, 2018

    2018

  26. [34]

    X. Hu, Y. Liu, H. Xiu, P. K. Agarwal, D. Panigrahi, S. Roy, and J. Yang. Selectivity functions of range queries are learnable. InSIGMOD, 2022

    2022

  27. [35]

    Immerman

    N. Immerman. Relational queries computable in polynomial time.Information and Control, 68:86–104, 1986

    1986

  28. [36]

    Janković and M

    S. Janković and M. Merkle. A mean value theorem for systems of integrals.Journal of Mathematical Analysis and Applications, 342(1):334–339, 2008

    2008

  29. [37]

    H. J. Keisler. Randomizing a model.Advances in Mathematics, 143(1):124–158, 1999

    1999

  30. [38]

    Khachiyan and L

    L. Khachiyan and L. Porkolab. Integer optimization on convex semialgebraic sets.Discret. Comput. Geom., 23(2):207–224, 2000

    2000

  31. [39]

    Lambotte and F

    Q. Lambotte and F. Point. On expansions of (Z, +, 0).Annals of Pure and Applied Logic, 171(8), 2020

    2020

  32. [40]

    H. W. Lenstra. Integer programming with a fixed number of variables.Math. Oper. Res., 8(4):538–548, 1983

    1983

  33. [41]

    L. Libkin. Embedded finite models and constraint databases. InFinite Model Theory and Its Applications. 2007

    2007

  34. [42]

    Olteanu and M

    D. Olteanu and M. Schleich. F: regression models over factorized views.Proc. VLDB Endow., 9(13):1573–1576, 2016

    2016

  35. [43]

    Paredaens, J

    J. Paredaens, J. V. den Bussche, and D. V. Gucht. First-order queries on finite structures over the reals.SIAM J. Comput., 27(6):1747–1763, 1998

    1998

  36. [44]

    Densité et dimension.Annales de l’Institut Fourier, 33(3):233–282, 1983

    Patrick Assouad. Densité et dimension.Annales de l’Institut Fourier, 33(3):233–282, 1983

    1983

  37. [45]

    Pitt and L

    L. Pitt and L. G. Valiant. Computational limitations on learning from examples.J. ACM, 35(4):965–984, 1988

    1988

  38. [46]

    Poizat.Les Petits Cailloux: Une approche modèle-théorique de l’algorithmie

    B. Poizat.Les Petits Cailloux: Une approche modèle-théorique de l’algorithmie. Aléas, Lyon, 1995

    1995

  39. [47]

    J. Renegar. On the computational complexity and geometry of the first-order theory of the reals, part I: introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals.J. Symb. Comput., 1992

    1992

  40. [48]

    Schrijver.Theory of Linear and Integer Programming

    A. Schrijver.Theory of Linear and Integer Programming. John Wiley & Sons, 1986

    1986

  41. [49]

    S. Shelah. Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory.Annals of Mathematical Logic, 3(3):271–362, 1971

    1971

  42. [50]

    S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41:247–261, 1972

    1972

  43. [51]

    Shelah and P

    S. Shelah and P. Simon. Adding linear orders.The Journal of Symbolic Logic, 77(2):717–725, 2012

    2012

  44. [52]

    Simon.A Guide to NIP Theories

    P. Simon.A Guide to NIP Theories. Cambridge University Press, 2015

    2015

  45. [53]

    ten Cate, M

    B. ten Cate, M. Funk, J. C. Jung, and C. Lutz. Fitting algorithms for conjunctive queries.SIGMOD Rec., 52(4):6–18, 2023

    2023

  46. [54]

    extension axiom

    M. Tong. Distal Expansions of Presburger Arithmetic by a sparse predicate.Journal of Symbolic Logic, page 1–33, 2024. 18 Michael Benedikt and Alessio Mansutti A RQ FITTING IS PRESERVED WHEN MOVING TO NON-STANDARD MODELS Let 𝔐 be a structure with domain 𝑀 and signature 𝐿. We re...

    2024

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.