{"id":"arxiv/2606.01107","url":"https://arxiv.org/abs/2606.01107","tags":["cs.LO","cs.LG","math.LO"],"score":0,"title":"How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?","domain":"cs.LO","source":"arxiv","authors":["Michael Benedikt","Alessio Mansutti"],"reviews":0,"subject":"cs.LO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-31","reactions":{}}