pith. sign in

arxiv: 2606.24848 · v1 · pith:LKJEGUJCnew · submitted 2026-06-23 · 💻 cs.LO

Complexity of Clique-Guarded First-Order Logic with Counting

Steffen van Bergerem , Johannes Friedrich Lange , Nicole Schweikardt This is my paper

Pith reviewed 2026-06-25 21:52 UTC · model grok-4.3

classification 💻 cs.LO
keywords clique-guarded logicfirst-order logic with countingVC-dimensionnowhere dense classeslocally bounded expansionquery answeringPAC learningenumeration
0
0 comments X

The pith

Clique-guarded first-order logic with counting admits computable VC-dimension bounds on nowhere dense classes and supports query and learning metatheorems on locally bounded expansion classes.

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

The paper introduces clique-guarded first-order logic with counting (cgFOC) as a fragment of first-order logic with counting. It establishes computable upper bounds on the VC-dimension of cgFOC formulas and the graph dimension of its counting terms when evaluated on nowhere dense classes of relational structures. These dimension bounds yield algorithmic metatheorems that make query answering, enumeration, and PAC learning of Boolean and multiclass problems tractable on classes of locally bounded expansion. The same results fail for a slight extension of cgFOC, which is already intractable on trees.

Core claim

We prove computable upper bounds on the Vapnik-Chervonenkis (VC) dimension of cgFOC formulas and on the graph dimension of cgFOC counting terms on nowhere dense classes of relational structures. Furthermore, we show algorithmic metatheorems for cgFOC for query answering, enumeration, and probably approximately correct (PAC) learning for Boolean and multiclass classification problems on classes of locally bounded expansion. On the other hand, we show that a slight extension of cgFOC is already intractable on trees.

What carries the argument

Clique-guarded first-order logic with counting (cgFOC), which restricts first-order quantification to cliques while permitting counting quantifiers, under the additional assumption of nowhere dense or locally bounded expansion structure classes.

If this is right

  • Boolean and multiclass PAC learning using cgFOC hypotheses becomes feasible with sample complexity governed by the computable VC-dimension bound.
  • Fixed-parameter tractable algorithms exist for answering and enumerating cgFOC queries on locally bounded expansion classes.
  • The metatheorems do not apply to any logic that properly extends cgFOC, even when restricted to trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sparsity conditions may allow similar dimension bounds for other guarded counting logics.
  • Real-world sparse data sets such as road networks or citation graphs could admit efficient cgFOC-based classification with explicit sample-size guarantees.
  • The separation on trees suggests a precise boundary between tractable and intractable counting logics under tree-like structure.

Load-bearing premise

The input structures must belong to nowhere dense classes or classes of locally bounded expansion.

What would settle it

A nowhere dense class of structures together with a family of cgFOC formulas whose VC-dimension grows unboundedly as formula size increases.

read the original abstract

We introduce clique-guarded first-order logic with counting (cgFOC), a fragment of the first-order logic with counting FOC [Kuske and Schweikardt, LICS 2017], and we study the complexity of this fragment. In particular, we prove computable upper bounds on the Vapnik-Chervonenkis (VC) dimension of cgFOC formulas and on the graph dimension of cgFOC counting terms on nowhere dense classes of relational structures. Furthermore, we show algorithmic metatheorems for cgFOC for query answering, enumeration, and probably approximately correct (PAC) learning for Boolean and multiclass classification problems on classes of locally bounded expansion. On the other hand, we show that a slight extension of cgFOC is already intractable on trees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces clique-guarded first-order logic with counting (cgFOC) as a fragment of FOC and proves computable upper bounds on the VC-dimension of cgFOC formulas and the graph dimension of cgFOC counting terms on nowhere dense classes of relational structures. It further establishes algorithmic metatheorems for cgFOC query answering, enumeration, and PAC learning (Boolean and multiclass) on classes of locally bounded expansion, while showing that a slight extension of cgFOC is intractable already on trees.

Significance. If the stated bounds and metatheorems hold, the work strengthens the theory of logical fragments with controlled complexity on sparse structures, linking VC-dimension and graph-dimension results to concrete algorithmic consequences for query evaluation and learning. The explicit contrast with intractability on trees helps delineate the fragment's boundary. The PAC-learning metatheorems constitute a non-trivial bridge between logic and statistical learning theory on sparse classes.

minor comments (2)
  1. [Abstract] The abstract states the existence of 'computable upper bounds' without indicating the form of the bounds or the dependence on the formula; a one-sentence clarification would help readers assess the strength of the result.
  2. Notation for clique-guarded quantification and the precise syntax of counting terms should be fixed early (ideally in a dedicated preliminary section) to avoid ambiguity when the metatheorems are stated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript on cgFOC, including the recognition of its contributions to VC-dimension bounds, algorithmic metatheorems, and the delineation of tractability boundaries. The report recommends minor revision but lists no specific major comments requiring response.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines cgFOC as a new fragment of the existing FOC logic from Kuske and Schweikardt (LICS 2017) and derives independent upper bounds on VC-dimension and graph dimension for nowhere dense classes, plus metatheorems for query answering, enumeration, and PAC learning on locally bounded expansion classes. These are presented as new proofs and algorithmic results rather than reductions to fitted parameters, self-definitions, or load-bearing self-citations. The intractability result for a slight extension on trees is likewise a separate contribution. No step in the derivation chain reduces by construction to its own inputs or renames prior results as novel; the sparsity conditions are explicit premises of the claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No free parameters or invented entities are apparent from the abstract; the work relies on standard mathematical assumptions in logic and graph theory.

axioms (2)
  • standard math Definitions and properties of nowhere dense classes and locally bounded expansion classes of structures.
    These are established concepts in structural graph theory used as the domain for the results.
  • standard math Standard semantics of first-order logic with counting.
    The fragment is defined within FOC from prior work.

pith-pipeline@v0.9.1-grok · 5661 in / 1443 out tokens · 29510 ms · 2026-06-25T21:52:25.369436+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages · 1 internal anchor

  1. [1]

    Interpreting nowhere dense graph classes as a classical notion of model theory

    Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. Eur. J. Comb. , 36:322--330, 2014. https://doi.org/10.1016/j.ejc.2013.06.048 doi:10.1016/j.ejc.2013.06.048

    work page doi:10.1016/j.ejc.2013.06.048 2014

  2. [2]

    V apnik-- C hervonenkis density in some theories without the independence property, I

    Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko. V apnik-- C hervonenkis density in some theories without the independence property, I . Transactions of the American Mathematical Society , 368(8):5889--5949, August 2016. https://doi.org/10.1090/tran/6659 doi:10.1090/tran/6659

    work page doi:10.1090/tran/6659 2016

  3. [3]

    Descriptive Complexity of Learning

    Steffen Bergerem v an Bergerem. Descriptive Complexity of Learning . PhD thesis, RWTH Aachen University, Germany, 2023. https://doi.org/10.18154/RWTH-2023-02554 doi:10.18154/RWTH-2023-02554

    work page doi:10.18154/rwth-2023-02554 2023

  4. [4]

    Learning concepts definable in first-order logic with counting

    Steffen Bergerem v an Bergerem. Learning concepts definable in first-order logic with counting. Log. Methods Comput. Sci. , 21(3), 2025. URL: https://doi.org/10.46298/lmcs-21(3:9)2025, https://doi.org/10.46298/LMCS-21(3:9)2025 doi:10.46298/LMCS-21(3:9)2025

    work page doi:10.46298/lmcs-21(3:9)2025 2025

  5. [5]

    On the Parameterized Com- plexity of Learning First-Order Logic

    Steffen Bergerem v an Bergerem, Martin Grohe, and Martin Ritzert. On the parameterized complexity of learning first-order logic. In Leonid Libkin and Pablo Barcel \' o , editors, PODS '22: International Conference on Management of Data, Philadelphia, PA , USA , June 12--17, 2022 , pages 337--346. ACM , 2022. https://doi.org/10.1145/3517804.3524151 doi:10....

    work page doi:10.1145/3517804.3524151 2022

  6. [6]

    Learning concepts described by weight aggregation logic

    Steffen Bergerem v an Bergerem and Nicole Schweikardt. Learning concepts described by weight aggregation logic. In Christel Baier and Jean Goubault - Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25--28, 2021, Ljubljana, Slovenia (Virtual Conference) , volume 183 of LIPIcs , pages 10:1--10:18. Schloss Dagstuhl...

    work page doi:10.4230/lipics.csl.2021.10 2021

  7. [7]

    Learning aggregate queries defined by first-order logic with counting

    Steffen Bergerem v an Bergerem and Nicole Schweikardt. Learning aggregate queries defined by first-order logic with counting. In Sudeepa Roy and Ahmet Kara, editors, 28th International Conference on Database Theory, ICDT 2025, March 25--28, 2025, Barcelona, Spain , volume 328 of LIPIcs , pages 4:1--4:19. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Inform...

    work page doi:10.4230/lipics.icdt.2025.4 2025

  8. [8]

    On the VC dimension of first-order logic with counting and weight aggregation

    Steffen Bergerem v an Bergerem and Nicole Schweikardt. On the VC dimension of first-order logic with counting and weight aggregation. In J \" o rg Endrullis and Sylvain Schmitz, editors, 33rd EACSL Annual Conference on Computer Science Logic, CSL 2025, February 10--14, 2025, Amsterdam, Netherlands , volume 326 of LIPIcs , pages 15:1--15:17. Schloss Dagstu...

    work page doi:10.4230/lipics.csl.2025.15 2025

  9. [9]

    Monadic NIP in monotone classes of relational structures

    Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos. Monadic NIP in monotone classes of relational structures. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10--14, 2023, Paderborn, Germany , volume 261 of LIPIcs , pages 119:1--1...

    work page doi:10.4230/lipics.icalp.2023.119 2023

  10. [10]

    A characterization of multiclass learnability

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO , USA , October 31 -- November 3, 2022 , pages 943--955. IEEE , 2022. https://doi.org/10.1109/FOCS54457.2022.00093 doi:10.1109/FOCS54457.2022.00093

    work page doi:10.1109/focs54457.2022.00093 2022

  11. [11]

    Multiclass learnability and the ERM principle

    Amit Daniely, Sivan Sabato, Shai Ben - David, and Shai Shalev - Shwartz. Multiclass learnability and the ERM principle. J. Mach. Learn. Res. , 16:2377--2404, 2015. URL: https://jmlr.org/papers/v16/daniely15a.html, https://doi.org/10.5555/2789272.2912074 doi:10.5555/2789272.2912074

    work page doi:10.5555/2789272.2912074 2015

  12. [12]

    Optimal learners for multiclass problems

    Amit Daniely and Shai Shalev - Shwartz. Optimal learners for multiclass problems. In Maria - Florina Balcan, Vitaly Feldman, and Csaba Szepesv \' a ri, editors, Proceedings of the 27th Conference on Learning Theory, COLT 2014, June 13--15, 2014, Barcelona, Spain , volume 35 of Proceedings of Machine Learning Research , pages 287--316. PMLR , 2014. URL: ht...

    2014

  13. [13]

    Testing first-order properties for subclasses of sparse graphs

    Zden e k Dvo r \' a k, Daniel Kr \' a l , and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM , 60(5):36:1--36:24, 2013. https://doi.org/10.1145/2499483 doi:10.1145/2499483

    work page doi:10.1145/2499483 2013

  14. [14]

    Giannopoulou, Stephan Kreutzer, O - joung Kwon, Micha Pilipczuk, Roman Rabinovich, and Sebastian Siebertz

    Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O - joung Kwon, Micha Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Pr...

    work page doi:10.4230/lipics.icalp.2017.63 2017

  15. [15]

    Solomon Feferman and Robert L. Vaught. The first order properties of products of algebraic systems. Fundamenta Mathematicae , 47(1):57--103, 1959. URL: http://eudml.org/doc/213526

    1959

  16. [16]

    Parameterized Complexity Theory

    J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

    work page doi:10.1007/3-540-29953-x 2006

  17. [17]

    Deciding First-Order Prop- erties of Nowhere Dense Graphs

    Haim Gaifman. On local and non-local properties. In Jacques Stern, editor, Proceedings of the Herbrand Symposium , volume 107 of Studies in Logic and the Foundations of Mathematics , pages 105--135. North-Holland Publishing Company, 1982. https://doi.org/10.1016/S0049-237X(08)71879-2 doi:10.1016/S0049-237X(08)71879-2

    work page doi:10.1016/s0049-237x(08)71879-2 1982

  18. [18]

    When trees grow low: Shrubs and fast MSO _1

    Robert Ganian, Petr Hlin e n \' y , Jaroslav Ne s et r il, Jan Obdr z \' a lek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO _1 . In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 -- 37th International Symposium, MFCS 2012, Bratislava, Slovakia,...

    work page doi:10.1007/978-3-642-32589-2 2012

  19. [19]

    o rg Flum, Erich Gr \

    Martin Grohe. Logic, graphs, and algorithms. In J \" o rg Flum, Erich Gr \" a del, and Thomas Wilke, editors, Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas] , volume 2 of Texts in Logic and Games , pages 357--422. Amsterdam University Press, 2008

    2008

  20. [20]

    Deciding first-order properties of nowhere dense graphs

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM , 64(3):17:1--17:32, 2017. https://doi.org/10.1145/3051095 doi:10.1145/3051095

    work page doi:10.1145/3051095 2017

  21. [21]

    Learning first-order definable concepts over structures of small degree

    Martin Grohe and Martin Ritzert. Learning first-order definable concepts over structures of small degree. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20--23, 2017 , pages 1--12. IEEE Computer Society, 2017. https://doi.org/10.1109/LICS.2017.8005080 doi:10.1109/LICS.2017.8005080

    work page doi:10.1109/lics.2017.8005080 2017

  22. [22]

    First-Order Query Evaluation with Cardinality Conditions

    Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems [ PODS 2018], Houston, TX , USA , June 10--15, 2018 , pages 253--266. ACM , 2018. Full version on arXiv: https://arxiv...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/3196959.3196970 2018

  23. [23]

    Learnability and definability in trees and similar structures

    Martin Grohe and Gy \" o rgy Tur \' a n. Learnability and definability in trees and similar structures. Theory Comput. Syst. , 37(1):193--220, 2004. https://doi.org/10.1007/s00224-003-1112-8 doi:10.1007/s00224-003-1112-8

    work page doi:10.1007/s00224-003-1112-8 2004

  24. [24]

    Decision theoretic generalizations of the PAC model for neural net and other learning applications

    David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput. , 100(1):78--150, 1992. https://doi.org/10.1016/0890-5401(92)90010-D doi:10.1016/0890-5401(92)90010-D

    work page doi:10.1016/0890-5401(92)90010-d 1992

  25. [25]

    The Hadamard product , pages 298--381

    Roger Alan Horn and Charles Royal Johnson. The Hadamard product , pages 298--381. Cambridge University Press, 1991. https://doi.org/10.1017/CBO9780511840371.006 doi:10.1017/CBO9780511840371.006

    work page doi:10.1017/cbo9780511840371.006 1991

  26. [26]

    Parameterized complexity of first-order logic

    Stephan Kreutzer and Anuj Dawar. Parameterized complexity of first-order logic. Electron. Colloquium Comput. Complex. , TR09-131 , 2009. URL: https://eccc.weizmann.ac.il/report/2009/131

    2009

  27. [27]

    First-order logic with counting

    Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20--23, 2017 , pages 1--12. IEEE Computer Society, 2017. https://doi.org/10.1109/LICS.2017.8005133 doi:10.1109/LICS.2017.8005133

    work page doi:10.1109/lics.2017.8005133 2017

  28. [28]

    Natarajan

    Balas K. Natarajan. On learning sets and functions. Mach. Learn. , 4:67--97, 1989. https://doi.org/10.1007/BF00114804 doi:10.1007/BF00114804

    work page doi:10.1007/bf00114804 1989

  29. [29]

    On nowhere dense graphs

    Jaroslav Ne s et r il and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb. , 32(4):600--617, 2011. https://doi.org/10.1016/j.ejc.2011.01.006 doi:10.1016/j.ejc.2011.01.006

    work page doi:10.1016/j.ejc.2011.01.006 2011

  30. [30]

    Sparsity -- Graphs, Structures, and Algorithms , volume 28 of Algorithms and Combinatorics

    Jaroslav Ne s et r il and Patrice Ossona de Mendez. Sparsity -- Graphs, Structures, and Algorithms , volume 28 of Algorithms and Combinatorics . Springer, 2012. https://doi.org/10.1007/978-3-642-27875-4 doi:10.1007/978-3-642-27875-4

    work page doi:10.1007/978-3-642-27875-4 2012

  31. [31]

    On the number of types in sparse graphs

    Micha Pilipczuk, Sebastian Siebertz, and Szymon Toru\' n czyk. On the number of types in sparse graphs. In Anuj Dawar and Erich Gr \" a del, editors, 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK , July 09--12, 2018 , pages 799--808. ACM , 2018. https://doi.org/10.1145/3209108.3209178 doi:10.1145/3209108.3209178

    work page doi:10.1145/3209108.3209178 2018

  32. [32]

    On the density of families of sets

    Norbert Sauer. On the density of families of sets. J. Comb. Theory A , 13(1):145--147, 1972. https://doi.org/10.1016/0097-3165(72)90019-2 doi:10.1016/0097-3165(72)90019-2

    work page doi:10.1016/0097-3165(72)90019-2 1972

  33. [33]

    Enumeration for FO queries over nowhere dense graphs

    Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO queries over nowhere dense graphs. J. ACM , 69(3):22:1--22:37, 2022. https://doi.org/10.1145/3517035 doi:10.1145/3517035

    work page doi:10.1145/3517035 2022

  34. [34]

    Linear time computable problems and first-order descriptions

    Detlef Seese. Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci. , 6(6):505--526, 1996. https://doi.org/10.1017/s0960129500070079 doi:10.1017/s0960129500070079

    work page doi:10.1017/s0960129500070079 1996

  35. [35]

    Constant delay enumeration for FO queries over databases with local bounded expansion

    Luc Segoufin and Alexandre Vigny. Constant delay enumeration for FO queries over databases with local bounded expansion. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21--24, 2017, Venice, Italy , volume 68 of LIPIcs , pages 20:1--20:16. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Inform...

    work page doi:10.4230/lipics.icdt.2017.20 2017

  36. [36]

    Understanding Machine Learning: From Theory to Algorithms

    Shai Shalev - Shwartz and Shai Ben - David. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press, 2014. https://doi.org/10.1017/CBO9781107298019 doi:10.1017/CBO9781107298019

    work page doi:10.1017/cbo9781107298019 2014

  37. [37]

    A combinatorial problem: stability and order for models and theories in infinitary languages

    Saharon Shelah. A combinatorial problem: stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics , 41(1):247--261, 1972. URL: http://dx.doi.org/10.2140/pjm.1972.41.247, https://doi.org/10.2140/pjm.1972.41.247 doi:10.2140/pjm.1972.41.247

    work page doi:10.2140/pjm.1972.41.247 1972

  38. [38]

    Aggregate queries on sparse databases

    Szymon Toru\' n czyk. Aggregate queries on sparse databases. 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 , June 14--19, 2020 , pages 427--443. ACM , 2020. https://doi.org/10.1145/3375395.3387660 doi:10.1145/3375395.3387660

    work page doi:10.1145/3375395.3387660 2020

  39. [39]

    Leslie G. Valiant. A theory of the learnable. Commun. ACM , 27(11):1134--1142, 1984. https://doi.org/10.1145/1968.1972 doi:10.1145/1968.1972

    work page doi:10.1145/1968.1972 1984

  40. [40]

    On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities,

    Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264--280, 1971. https://doi.org/10.1137/1116025 doi:10.1137/1116025

    work page doi:10.1137/1116025 1971

  41. [41]

    Colouring graphs with bounded generalized colouring number

    Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discret. Math. , 309(18):5562--5568, 2009. URL: https://doi.org/10.1016/j.disc.2008.03.024, https://doi.org/10.1016/J.DISC.2008.03.024 doi:10.1016/J.DISC.2008.03.024

    work page doi:10.1016/j.disc.2008.03.024 2009