5 citations · 12 across the 6 of their papers we have counts for
7 papers
EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis
Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde
Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blow…
Learning temporal formulas from examples is hard
Corto Mascle, Nathanaël Fijalkow, Guillaume Lagarde
We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a w…
Scaling Neural Program Synthesis with Distribution-based Search
Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon +3
We consider the problem of automatically constructing computer programs from input-output examples. We investigate how to augment probabilistic and neural program synthesis methods…
The Complexity of Learning Linear Temporal Formulas from Examples
Nathanaël Fijalkow, Guillaume Lagarde
In this paper we initiate the study of the computational complexity of learning linear temporal logic (LTL) formulas from examples. We construct approximation algorithms for fragme…
On Efficient Low Distortion Ultrametric Embedding
Vincent Cohen-Addad, Karthik C. S., Guillaume Lagarde
A classic problem in unsupervised learning and data analysis is to find simpler and easy-to-visualize representations of the data that preserve its essential properties. A widely-u…
Lempel-Ziv: a "one-bit catastrophe" but not a tragedy
Guillaume Lagarde, Sylvain Perifel
The so-called "one-bit catastrophe" for the compression algorithm LZ'78 asks whether the compression ratio of an infinite word can change when a single bit is added in front of it.…
De Bruijn-Erdős type theorems for graphs and posets
Pierre Aboulker, Guillaume Lagarde, David Malec +2
A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theore…