Source author record

Guillaume Lagarde

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Machine Learning Computational Complexity Computational Geometry Data Structures and Algorithms Formal Languages and Automata Theory Logic in Computer Science math.CO math.MG

Catalog footprint

Research overview

3works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

The Complexity of Learning Linear Temporal Formulas from Examples

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 fragments of LTL and prove hardness results; in particular we obtain tight bounds for approximation of the fragment containing only the next operator and conjunctions, and prove NP-completeness results for many fragments.

preprint2020arXiv

On Efficient Low Distortion Ultrametric Embedding

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-used method to preserve the underlying hierarchical structure of the data while reducing its complexity is to find an embedding of the data into a tree or an ultrametric. The most popular algorithms for this task are the classic linkage algorithms (single, average, or complete). However, these methods on a data set of $n$ points in $Ω(\log n)$ dimensions exhibit a quite prohibitive running time of $Θ(n^2)$ . In this paper, we provide a new algorithm which takes as input a set of points $P$ in $\mathbb{R}^d$ , and for every $c\ge 1$ , runs in time $n^{1+\fracρ{c^2}}$ (for some universal constant $ρ>1$ ) to output an ultrametric $Δ$ such that for any two points $u,v$ in $P$ , we have $Δ(u,v)$ is within a multiplicative factor of $5c$ to the distance between $u$ and $v$ in the "best" ultrametric representation of $P$ . Here, the best ultrametric is the ultrametric $\tildeΔ$ that minimizes the maximum distance distortion with respect to the $\ell_2$ distance, namely that minimizes $\underset{u,v \in P}{\max}\ \frac{\tildeΔ(u,v)}{\|u-v\|_2}$ . We complement the above result by showing that under popular complexity theoretic assumptions, for every constant $\varepsilon>0$ , no algorithm with running time $n^{2-\varepsilon}$ can distinguish between inputs in $\ell_\infty$ -metric that admit isometric embedding and those that incur a distortion of $\frac{3}{2}$ . Finally, we present empirical evaluation on classic machine learning datasets and show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.

preprint2015arXiv

De Bruijn-Erdős type theorems for graphs and posets

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 theorem holds for graphs. Restricting our attention to comparability graphs, we obtain a version of the De Bruijn-Erdős theorem for partially ordered sets (posets). Moreover, in this case, we have an improved bound on the number of lines depending on the height of the poset. The extremal configurations are also determined.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.