{"ID":2921643,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-03T05:56:00.181519634Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.01107","arxiv_id":"2606.01107","title":"How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?","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.","short_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 descrip...","url_abs":"https://arxiv.org/abs/2606.01107","url_pdf":"https://arxiv.org/pdf/2606.01107v1","authors":"[\"Michael Benedikt\",\"Alessio Mansutti\"]","published":"2026-05-31T08:59:30Z","proceeding":"cs.LO","tasks":"[\"cs.LO\",\"cs.LG\",\"math.LO\"]","methods":"[]","has_code":false}