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

Conference item

We study fitting problems, sometimes called “training problems”, where given a finite sample of inputs and outputs, the goal is to determine whether a function in a certain class can produce those 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. Our framework encompasses classes that arise in practice, including neural network classifiers.

We also study fitting for classes indexed by distributions over structures, where we learn a distribution over elements from the statistics it induces on definable subsets; a framework that connects to learning-based cardinality estimation in databases. In both settings, we characterize the complexity of fitting and show how these problems can often be decided through encodings into natural query languages over the sample, while establishing broad structural theorems based on combinatorial and model-theoretic properties.

Authors: Benedikt, M; Mansutti, A

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Acceptance date: 2026-08-27
• Event title: ACM International Conference on Management of Data (SIGMOD/PODS 2027)
• Event location: Huntington Beach, CA, USA
• Event website: https://2027.sigmod.org/
• Event start date: 2026-06-13
• Event end date: 2026-06-19
• Language: English
• Keywords: fitting problems; embedded finite models; RQC; NIP; automatic structures