Travaux de recherche

Cette page liste tous mes travaux de recherche. Ceux indiqués par le signe (*) n'ont pas fait l'objet d'une évaluation par les pairs. Cette liste est également disponible comme un fichier PDF. This page is also available in English.

Pour une présentation plus lisible de ma recherche, voici une introduction (en anglais).

La version définitive de mes travaux est toujours celle qui est liée à partir de cette page : elle inclut toutes les modifications apportées suivant l'évaluation des pairs, et toutes les corrections ou errata appliquées après la publication, s'il y en a. Toutes mes publications sont en libre accès. N'achetez jamais mes travaux auprès d'un éditeur scientifique : vous gaspilleriez votre argent, et risqueriez de recevoir une version périmée ou moins bien formatée.

2025¶

• Antoine Amarilli, Corentin Barloy, Louis Jachiet, Charles Paperman.
  Dynamic Membership for Regular Tree Languages.
  MFCS 2025.
• Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid.
  Linear Time Subsequence and Supersequence Regex Matching.
  MFCS 2025.
• Antoine Amarilli, Benoît Groz.
  Cutwidth Bounds via Vertex Partitions.
  arXiv:2504.01574v2, 2025. (*)
• Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija, Mikaël Monet.
  Resilience for Regular Path Queries: Towards a Complexity Classification.
  PODS 2025. [erreurs mineures identifiées (en anglais)]
• Antoine Amarilli, Benoît Groz, Nicole Wein.
  Edge-Minimum Walk of Modular Length in Polynomial Time.
  ITCS 2025. [exposé par Nicole Wein, vidéo par Nicole Wein sur Youtube]
• Antoine Amarilli, Timothy van Bremen, Octave Gaspard, Kuldeep S. Meel.
  Approximating Queries on Probabilistic Graphs.
  Soumis au comité de lecture. [version conférence] (*)

2024¶

• Antoine Amarilli, Michael Benedikt.
  Tighter Bounds for Query Answering with Guarded TGDs.
  Soumis au comité de lecture. (*)
• Antoine Amarilli.
  Survey of Results on the ModPath and ModCycle Problems.
  arXiv:2409.00770v1, 2024. [code] (*)
• Antoine Amarilli, Florent Capelli.
  Tractable Circuits in Database Theory.
  SIGMOD Record Database Principles Column. (*)
• Antoine Amarilli, Marcelo Arenas, YooJung Choi, Mikaël Monet, Guy Van den Broeck, Benjie Wang.
  A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata.
  arXiv:2404.09674v1, 2024. (*)
• Antoine Amarilli, Mikaël Monet, Dan Suciu.
  The Non-Cancelling Intersections Conjecture.
  arXiv:2401.16210v1, 2024. (*)
• Antoine Amarilli, Timothy van Bremen, Kuldeep S. Meel.
  Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability.
  ICDT 2024. [version journal, exposé par Timothy van Bremen, erreurs mineures identifiées (en anglais)]
• Antoine Amarilli, Pierre Bourhis, Florent Capelli, Mikaël Monet.
  Ranked Enumeration for MSO on Trees via Knowledge Compilation.
  ICDT 2024. [exposé par Pierre Bourhis]
• Antoine Amarilli, Benny Kimelfeld, Sébastien Labbé, Stefan Mengel.
  Skyline Operators for Document Spanners.
  ICDT 2024. [exposé]

2023¶

• Antoine Amarilli, Charles Paperman.
  Locality and Centrality: The Variety ZG.
  LMCS.
• Osnat Drien, Matanya Freiman, Antoine Amarilli, Yael Amsterdamer.
  Query-Driven Resolution in Uncertain Databases.
  SIGMOD 2023.
• Antoine Amarilli.
  Degree-3 Planar Graphs as Topological Minors of Wall Graphs in Polynomial Time.
  arXiv:2302.03461v3, 2023. (*)
• Antoine Amarilli.
  Query Evaluation: Enumeration, Maintenance, Reliability.
  Thèse d'habilitation à diriger des recherches. (*)
• Antoine Amarilli, Mikaël Monet.
  Enumerating Regular Languages with Bounded Delay.
  STACS 2023. [exposé par Mikaël Monet, erreurs mineures identifiées (en anglais)]
• Antoine Amarilli.
  Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries.
  ICDT 2023. [exposé, vidéo]

2022¶

• Antoine Amarilli, Benny Kimelfeld.
  Uniform Reliability of Self-Join-Free Conjunctive Queries.
  LMCS, 2022. [version conférence]
• Antoine Amarilli, Mikaël Monet.
  Weighted Counting of Matchings in Unbounded-Treewidth Graph Families.
  MFCS 2022. [exposé par Mikaël Monet, code]
• Antoine Amarilli, Yael Amsterdamer.
  Worst-Case Analysis for Interactive Evaluation of Boolean Provenance.
  TAPP 2022. [exposé par Yael Amsterdamer]
• Antoine Amarilli, Louis Jachiet, Martín Muñoz, Cristian Riveros.
  Efficient Enumeration Algorithms for Annotated Grammars.
  PODS 2022. [exposé par Martín Muñoz, vidéo par Martín Muñoz sur Youtube]
• Antoine Amarilli, Michael Benedikt.
  When Can We Answer Queries Using Result-Bounded Data Interfaces?
  LMCS, 2022. [version conférence]
• Antoine Amarilli, İsmail İlkan Ceylan.
  The Dichotomy of Evaluating Homomorphism-Closed Queries on Probabilistic Graphs.
  LMCS, 2022. [version conférence]

2021¶

• Antoine Amarilli, Louis Jachiet, Charles Paperman.
  Dynamic Membership for Regular Languages.
  ICALP 2021. [exposé, vidéo sur Youtube ou en téléchargement direct]. Prix du meilleur article à ICALP'21 Track B.
• Osnat Drien, Antoine Amarilli, Yael Amsterdamer.
  Managing Consent for Data Access in Shared Databases.
  ICDE 2021. Article court. [erreurs identifiées (en anglais)]
• Antoine Amarilli, Benny Kimelfeld.
  Uniform Reliability of Self-Join-Free Conjunctive Queries.
  ICDT 2021. [version journal, exposé, vidéo sur PeerTube INFRES ou en téléchargement direct]
• Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth.
  Constant-Delay Enumeration for Nondeterministic Document Spanners.
  TODS, 2021. [version conférence, code par Rémi Dupré et Matthias Niewerth]

2020¶

• Julien Romero, Nicoleta Preda, Antoine Amarilli, Fabian M. Suchanek.
  Computing and Illustrating Query Rewritings on Path Views with Binding Patterns.
  CIKM 2020. Démonstration. [vidéo par Julien Romero sur ACM Digital Library ou en téléchargement direct, code par Julien Romero]
• Antoine Amarilli, İsmail İlkan Ceylan.
  A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs.
  ICDT 2020. [version journal, exposé, poster, vidéo sur TIB AV-Portal ou en téléchargement direct]. Prix du meilleur article à ICDT'20.
• Julien Romero, Nicoleta Preda, Antoine Amarilli, Fabian M. Suchanek.
  Equivalent Rewritings on Path Views with Binding Patterns.
  ESWC 2020. [exposé, vidéo par Julien Romero sur Videolectures.net ou sur Youtube ou en téléchargement direct]
• Antoine Amarilli, Michael Benedikt.
  Finite Open-World Query Answering with Number Restrictions.
  ToCL, 2020. [version conférence]
• Antoine Amarilli, Florent Capelli, Mikaël Monet, Pierre Senellart.
  Connecting Knowledge Compilation Classes and Width Parameters.
  ToCS, 2020. [version conférence]

2019¶

• Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli.
  Smoothing Structured Decomposable Circuits.
  NeurIPS 2019. Exposé spotlight. [exposé par Andy Shih, poster par Andy Shih]
• Antoine Amarilli, M. Lamine Ba, Daniel Deutch, Pierre Senellart.
  Computing Possible and Certain Answers over Order-Incomplete Data.
  TCS, 2019. [version conférence]
• Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth.
  Enumeration on Trees with Tractable Combined Complexity and Efficient Updates.
  PODS 2019. [exposé par Matthias Niewerth, poster par Matthias Niewerth, vidéo par Matthias Niewerth sur TIB AV-Portal ou en téléchargement direct, erreurs identifiées (en anglais)]
• Antoine Amarilli, Pierre Bourhis, Stefan Mengel, Matthias Niewerth.
  Constant-Delay Enumeration for Nondeterministic Document Spanners.
  ICDT 2019. [version journal, exposé par Matthias Niewerth, code par Rémi Dupré et Matthias Niewerth]. Mis en valeur comme ACM SIGMOD Research Highlights.
• Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart.
  Evaluating Datalog via Tree Automata and Cycluits.
  ToCS, 2019. [version conférence]

2018¶

• Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom.
  Query Answering with Transitive and Linear-Ordered Data.
  JAIR, 2018. [version conférence, erreurs identifiées (en anglais)]
• Antoine Amarilli, Charles Paperman.
  Topological Sorting under Regular Constraints.
  ICALP 2018. [exposé]
• Antoine Amarilli, Michael Benedikt.
  When Can We Answer Queries Using Result-Bounded Data Interfaces?
  PODS 2018. [version journal, exposé, poster, vidéo sur Youtube ou en téléchargement direct, erreurs identifiées (en anglais)]
• Antoine Amarilli, Mikaël Monet, Pierre Senellart.
  Connecting Width and Structure in Knowledge Compilation.
  ICDT 2018. [version journal, exposé par Mikaël Monet]
• Antoine Amarilli, Pierre Bourhis, Stefan Mengel.
  Enumeration on Trees under Relabelings.
  ICDT 2018. [exposé, poster]

2017¶

• Antoine Amarilli, M. Lamine Ba, Daniel Deutch, Pierre Senellart.
  Possible and Certain Answers for Queries over Order-Incomplete Data.
  TIME 2017. [version journal, exposé, erreurs identifiées (en anglais)]
• Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel.
  A Circuit-Based Approach to Efficient Enumeration.
  ICALP 2017. [exposé]
• Antoine Amarilli, Mikaël Monet, Pierre Senellart.
  Conjunctive Queries on Probabilistic Graphs: Combined Complexity.
  PODS 2017. [exposé par Mikaël Monet, poster par Mikaël Monet]
• Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart.
  Combined Tractability of Query Evaluation via Tree Automata and Cycluits.
  ICDT 2017. [version journal, exposé par Mikaël Monet, poster par Mikaël Monet]
• Antoine Amarilli, Yael Amsterdamer, Tova Milo, Pierre Senellart.
  Top-k Queries on Unknown Values under Order Constraints.
  ICDT 2017. [exposé par Yael Amsterdamer, poster par Yael Amsterdamer]
• Luis Galárraga, Simon Razniewski, Antoine Amarilli, Fabian M. Suchanek.
  Predicting Completeness in Knowledge Bases.
  WSDM 2017. [exposé par Luis Galárraga, poster par Luis Galárraga]

2016¶

• Antoine Amarilli, Silviu Maniu, Mikaël Monet.
  Challenges for Efficient Query Evaluation on Structured Probabilistic Data.
  SUM 2016. [exposé par Mikaël Monet]
• Antoine Amarilli, Marc Beunardeau, Rémi Géraud, David Naccache.
  Failure is Also an Option.
  The New Codebreakers: Essays Dedicated to David Kahn on the Occasion of His 85th Birthday. (*)
• Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom.
  Query Answering with Transitive and Linear-Ordered Data.
  IJCAI 2016. [version journal, exposé par Michael Vanden Boom, exposé plus détaillé, poster par Michael Vanden Boom, erreurs identifiées (en anglais)]
• Antoine Amarilli.
  Leveraging the Structure of Uncertain Data.
  Thèse de doctorat. [exposé, erreurs identifiées (en anglais)] (*)
• Antoine Amarilli, Pierre Bourhis, Pierre Senellart.
  Tractable Lineages on Treelike Instances: Limits and Extensions.
  PODS 2016. [exposé, poster, erreurs identifiées (en anglais)]
• Ruiming Tang, Antoine Amarilli, Pierre Senellart, Stéphane Bressan.
  A Framework for Sampling-Based XML Data Pricing.
  TLDKS, 2016. [version conférence]

2015¶

• Antoine Amarilli, Mehryar Mohri, Cyril Allauzen.
  Minimum Bayesian Risk Methods for Automatic Speech Recognition.
  US Patent 9123333. [je ne cautionne pas les brevets logiciels]
• Antoine Amarilli.
  Possibility in Probabilistic XML.
  ISI, 2015. [version conférence, la version éditeur n'est plus disponible]
• Antoine Amarilli, Silviu Maniu, Pierre Senellart.
  Intensional Data on the Web.
  ACM SIGWEB Newsletter, Summer 2015. (*)
• Antoine Amarilli, Michael Benedikt.
  Combining Existential Rules and Description Logics.
  IJCAI 2015. [exposé, exposé plus détaillé, poster]
• Aliaksandr Talaika, Joanna Biega, Antoine Amarilli, Fabian M. Suchanek.
  IBEX: Harvesting Entities from the Web Using Unique Identifiers.
  WebDB 2015. [exposé]
• Antoine Amarilli, Michael Benedikt.
  Finite Open-World Query Answering with Number Restrictions.
  LICS 2015. [version journal, exposé]
• Antoine Amarilli, Pierre Bourhis, Pierre Senellart.
  Provenance Circuits for Trees and Treelike Instances.
  ICALP 2015. [exposé]
• Antoine Amarilli.
  Structurally Tractable Uncertain Data.
  SIGMOD/PODS Ph.D. Symposium 2015. [exposé]

2014¶

• Antoine Amarilli, Luis Galárraga, Nicoleta Preda, Fabian M. Suchanek.
  Recent Topics of Research around the YAGO Knowledge Base.
  APWEB 2014. (*)
• Ruiming Tang, Antoine Amarilli, Pierre Senellart, Stéphane Bressan.
  Get a Sample for a Discount: Sampling-Based XML Data Pricing.
  DEXA 2014. [version journal, exposé par Ruiming Tang]
• Antoine Amarilli, Yael Amsterdamer, Tova Milo.
  Uncertainty in Crowd Data Sourcing under Structural Constraints.
  UnCrowd 2014. [exposé]
• Antoine Amarilli.
  The Possibility Problem for Probabilistic XML.
  AMW 2014. [version journal, exposé]
• Antoine Amarilli, Yael Amsterdamer, Tova Milo.
  On the Complexity of Mining Itemsets from the Crowd Using Taxonomies.
  ICDT 2014. [exposé]

2013¶

• Antoine Amarilli, Pierre Senellart.
  On the Connections between Relational and XML Probabilistic Data Models.
  BNCOD 2013. [exposé]

2012¶

• Antoine Amarilli, Fabrice Ben Hamouda, Florian Bourse, Robin Morisset, David Naccache, Pablo Rauzy.
  From Rational Number Reconstruction to Set Reconciliation and File Synchronization.
  TGC 2012. (*)
• Antoine Amarilli.
  Advances in Holistic Ontology Alignment.
  Rapport de stage de master. [exposé] (*)
• Marilena Oita, Antoine Amarilli, Pierre Senellart.
  Cross-Fertilizing Deep Web Analysis and Ontology Enrichment.
  VLDS 2012.
• Antoine Amarilli, Marc Jeanmougin.
  A Proof of the Pumping Lemma for Context-Free Languages Through Pushdown Automata.
  arXiv:1207.2819v1, 2012. (*)

2011¶

• Antoine Amarilli, David Naccache, Pablo Rauzy, Emil Simion.
  Can a Program Reverse-Engineer Itself?
  IMACC 2011. (*)
• Antoine Amarilli, Sascha Müller, David Naccache, Daniel Page, Pablo Rauzy, Michael Tunstall.
  Can Code Polymorphism Limit Information Leakage?
  WISTP 2011. [code] (*)

Errata¶

Pour les errata sur mes travaux de recherche, merci de se reporter à la version anglaise de cette page.