BOOKS

 

- With Marcelo Arenas, Leonid Libkin, Wim Martens, and Andreas Pieris. "Principles of Databases".  Work in progress.

 

- With Marcelo Arenas, Leonid Libkin and Filip Murlak. "Foundations of Data Exchange".  Cambridge University Press, 2014.

 

- With Marcelo Arenas, Leonid Libkin and Filip Murlak. "Relational and XML Data Exchange".  Morgan and Claypool, Synthesis Lectures on Data Management, 2010.

 

 

BOOK CHAPTERS

 

- With Leopoldo Bertossi and Loreto Bravo. "Characterizing and Computing Semantically Correct Answers from Databases with Annotated Logic and Answer Sets". In "Semantics of Databases", vol. 2582 of Springer Lecture Notes in Computer Science, L. Bertossi, G. Katona, K.D. Schewe, B. Thalheim, Eds., pages 1-27, 2003.

 

 

JOURNAL PAPERS

 

- With Marcelo Arenas, Leopoldo Bertossi, and Mikael Monet. "On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results".  Journal of Machine Learning Research, 24, 63:1-63:58, 2023.

 

- With Nelson Higuera, Jorge Perez, and Bernardo Subsercaseaux. "On the Expressiveness of LARA: A Proposal for Unifying Linear and Relational Algebra".  Theoretical Computer Science, 935: 105-127, 2022.

 

- With Jorge Perez and Javier Marinkovic. "Attention is Turing-Complete".  Journal of Machine Learning Research, 22: 75:1-75:35, 2021.

 

- With Marcelo Arenas and Mikael Monet. "The Complexity of Counting Problems Over Incomplete Databases".  ACM Transactions on Computational Logic (TOCL), 22(4), 2021.

 

- With Alexander Baumgartner, Victor Dalmau, and Benny Kimelfeld. "Regularizing Conjunctive Features for Classification".  Journal of Computer and System Sciences, 119: 97-124 (2021).

 

- With Diego Figueira, Georg Gottlob and Andreas Pieris. "Semantic Optimization of Conjunctive Queries".  Journal of the ACM, 67(6): 31:1-34:60 (2020).

 

- With Miguel Romero and Thomas Zeume. "A More General Theory of Static Approximations for Conjunctive Queries".  Theory of Computing Systems (ToCS), 64(5): 916-964 (2020). Special issue: Selected papers from ICDT 2018.

 

- With Sergio Abriola, Diego Figueira, and Santiago Figueira. "Bisimulations on Data Graphs".  Journal of Artifical Intelligence Research (JAIR) 61, pages 171-213, 2018.

 

- With Markus Kroll, Reinhard Pichler, and Sebastian Skritek. "Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection".  ACM Transactions on Database Systems (TODS) 43(2), pages 8:1-8:44, 2018.

 

- With Renzo Angles, Marcelo Arenas, Aidan Hogan, Juan Reutter and Domagoj Vrgoc. "Foundations of Modern Query Languages for Graph Databases".  ACM Computing Surveys (CSUR) 50(5), pages 68:1-68:40, 2017.

 

- With Andreas Pieris and Miguel Romero. "Semantic Optimization in Tractable Classes of Conjunctive Queries".  SIGMOD Record 46(2), pages 5-17, 2017.

 

- With Gaelle Fontaine. "On the Data Complexity of Consistent Query Answering over Graph Databases".  Journal of Computer and System Sciences (JCSS) 88, pages 164-194, 2017.

 

- With Pablo Muñoz. "Graph Logics with Rational Relations: The Role of Word Combinatorics".  ACM Transactions on Computational Logic (TOCL), 18(2), 2017.

 

- With Miguel Romero and Moshe Vardi. "Semantic Acyclicity on Graph Databases".  SIAM Journal on Computing (SICOMP), 45(4), pages 1339-1376, 2016.

 

- With Leonid Libkin. "Order-Invariant Types and Their Applications".  Logical Methods in Computer Science (LMCS), 12(1), 2016.

 

- With Gaelle Fontaine and Anthony Widjaja Lin. "Expressive Path Queries on Graphs with Data".  Logical Methods in Computer Science (LMCS), 11(4), 2015.

 

- With Leonid Libkin and Miguel Romero. "Efficient Approximations of Conjunctive Queries".  SIAM Journal on Computing (SICOMP), 43(3), pages 1085-1130, 2014.

 

- With Leonid Libkin and Juan Reutter. "Querying Regular Graph Patterns".  Journal of the ACM (JACM), 61(1), 2014. Special issue: Selected papers from PODS 2011.

 

- With Marcelo Arenas, Ronald Fagin and Leonid Libkin. "Solutions and Query Rewriting in Data Exchange".  Information and Computation 228, pages 28-61, 2013.

 

- With Diego Figueira and Leonid Libkin. "Graph Logics with Rational Relations".  Logical Methods in Computer Science (LMCS), 9(3), 2013.

 

- With Leonid Libkin and Juan Reutter. "Parameterized Regular Expressions and Their Languages".  Theoretical Computer Science (TCS) 474, pages 21-45, 2013.

 

- With Leonid Libkin, Anthony Widjaja Lin and Peter Wood. "Expressive Languages for Path Queries over Graph-structured Data".  ACM Transactions on Database Systems (TODS), 37(4), 2012.

 

- With Marcelo Arenas and Leonid Libkin. "Regular Languages for Nested Words: Fixed-points, Automata and Synchronization".  Theory of Computing Systems (ToCS), 49(3), pages 639-670, 2011.

 

- With Marcelo Arenas and Juan Reutter. "Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries".  Theory of Computing Systems (ToCS), 49(2), pages 489-564, 2011.

 

- With Leonid Libkin, Antonella Poggi and Cristina Sirangelo. "XML with Incomplete Information".  Journal of the ACM (JACM), 58(1): 4, 2010.

 

- "Logical Foundations of Relational Data Exchange".  SIGMOD Record, 38(1), pages 49-58, 2009.

 

- With Marcelo Arenas and Leonid Libkin. "Game-based Notions of Locality over Finite Models".  Annals of Pure and Applied Logic (APAL), 152(1-3), pages 3-30, 2008.

 

- With Rajeev Alur, Marcelo Arenas, Kousha Etessami, Neil Immerman and Leonid Libkin. "First-order and Temporal Logics for Nested Words".  Logical Methods in Computer Science (LMCS), Special issue: Selected papers LICS 2007, Vol. 4, Issue 4, pages 1-44, 2008.

 

 

CONFERENCE PAPERS

 

- With Marcelo Arenas, Diego Bustamente, Jose Caraball, Bernardo Subercaseaux. "A Uniform Language for Explaining Decision Trees".  In International Conference on Principles of Knowledge Representation and Reasoning, KR 2024.

 

- With Alexander Kozachinskiy, Anthony Widjaja Lin and Vladimir V. Podolskii. "Logical Languages Accepted by Transformer Encoders with Hard Attention".  In International Conference on Learning Representations, ICLR 2024.

 

- With Matthias Lanzinger. "On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters".  In International Conference on Learning Representations, ICLR 2024.

 

- With Xingyue Huang, Miguel Romero and Ismail Ilkan Ceylan. "A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs".  In Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023.

 

- With Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas and Mircea Petrache. "Three Iterations of (d - 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points".  In Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023.

 

- With Mauricio Duarte, Cristobal Rojas, and Tomasz Steifer. "No Agreement Without Loss: Learning and Social Choice in Peer Review".  In 26th European Conference on Artificial Intelligence, ECAI 2023.

 

- With Diego Figueira and Remi Morvan. "Separating Automatic Relations".  In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023.

 

- With Michael Galkin, Christopher Morris, and Miguel Romero. "Weisfeiler and Leman go Relational".  In Learning on Graphs 2022 (LoG 2022).

 

- With Marcelo Arenas, Miguel Romero, and Bernardo Subercaseaux. "On Computing Probabilistic Explanations for Decision Trees".  In Annual Conference on Neural Information Processing Systems 2022 (NeurIPS 2022).

 

- With Marcelo Arenas, Daniel Baez, Jorge Perez, and Bernardo Subercaseaux "Foundations of Symbolic Languages for Model Interpretability".  In Annual Conference on Neural Information Processing Systems 2021 (NeurIPS 2021).

 

- With Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. "Graph Neural Networks with Local Graph Parameters".  In Annual Conference on Neural Information Processing Systems 2021 (NeurIPS 2021).

 

- With Marcelo Arenas, Leopoldo Bertossi, and Mikael Monet. "The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits".  In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pages 6670-6678, 2021.

 

- With Mikael Monet, Jorge Perez, and Bernardo Subercaseaux. "Model Interpretability through the Lens of Computational Complexity".  In Proceedings of the Annual Conference on Neural Information Processing Systems 2020 (NeurIPS 2020).

 

- With Victor Dalmau, Cristina Feier, Carsten Lutz, and Andreas Pieris. "The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs".  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2020), pages 259-270, 2020.

 

- With Victor Dalmau, Cristina Feier, Carsten Lutz, and Andreas Pieris. "The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs".  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2020), pages 259-270, 2020.

 

- With Marcelo Arenas and Mikael Monet. "Counting Problems over Incomplete Databases".  In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2020), pages 165-177, 2020.

 

- With Egor V. Kostylev, Mikael Monet, Jorge Perez, Juan Reutter, and Juan Pablo Silva. "The Logical Expressiveness of Graph Neural Networks".  In 8th International Conference on Learning Representations (ICLR2020), 2020.

 

- With Nelson Higuera, Jorge Perez, and Bernardo Subercaseux. "On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra".  Accepted for publication in 23rd International Conference on Database Theory (ICDT 2020), 2020.

 

- With Chih-Duo Hong, Xuan Bach Le, Anthony W. Lin and Reino Niskanen. "Monadic Decomposability of Regular Relations".  In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), 2019.

 

- With Diego Figueira and Miguel Romero. "Boundedness of Conjunctive Regular Path Queries".  In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019), 2019.

 

- With Cristina Feier, Carsten Lutz, and Andreas Pieris. "When is Ontology-Mediated Querying Efficient?".  In Proceedings of the 34th ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), 2019.

 

- With Javier Marinkovic and Jorge Perez. "On the Turing Completeness of Modern Neural Network Architectures".  In 7th International Conference on Learning Representations (ICLR2019), 2019.

 

- With Alexander Baumgartner, Victor Dalmau, and Benny Kimelfeld. "Regularizing Conjunctive Features for Classification".  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2019), pages 2-16, 2019.

 

- With Gerald Berger, Carsten Lutz, and Andreas Pieris. "First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries".  In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pages 1707-1713, 2018.

 

- With Renzo Angles, Marcelo Arenas, Peter A. Boncz, George H. L. Fletcher, Claudio Gutierrez, Tobias Lindaaker, Marcus Paradies, Stefan Plantikow, Juan F. Sequeda, Oskar van Rest, and Hannes Voigt. "G-CORE: A Core for Future Graph Query Languages".  In Proceedings of the SIGMOD Conference 2018, pages 1421-1432, 2018.

 

- With Gerald Berger and Andreas Pieris. "Containment for Rule-Based Ontology-Mediated Queries".  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2018), pages 267-279, 2018.

 

- With Miguel Romero and Thomas Zeume. "A More General Theory of Static Approximations for Conjunctive Queries".  In Proceedings of the 21st International Conference on Database Theory (ICDT 2018), 2018.

 

- With Miguel Romero and Moshe Y. Vardi. "The Homomorphism Problem for Regular Graph Patterns".  In Proceedings of the 32nd ACM/IEEE Symposium on Logic in Computer Science (LICS 2017), 2017.

 

- With Miguel Romero. "The Complexity of Reverse Engineering Problems for Conjunctive Queries".  In Proceedings of the 20th International Conference on Database Theory (ICDT 2017), pages 1-17, 2017.

 

- With Georg Gottlob and Andreas Pieris. "Semantic Acyclicity under Constraints".  In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2016), pages 343-354, 2016.

 

- With Sergio Abriola, Diego Figueira, and Santiago Figueira. "Bisimulations on Data Graphs".  In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 2016), pages 309-318, 2016.

 

- With Anthony Widjaja Lin. "String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation XSS".  In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2016), pages 123-136, 2016.

 

- With Reinhard Pichler and Sebastian Skritek. "Efficient Evaluation and Approximation of Well-Designed Pattern Trees".  In Proceedings 34th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2015), pages 131-144, 2015.

 

- With Gaelle Fontaine. "On the Data Complexity of Consistent Query Answering over Graph Databases".  In Proceedings 18th International Conference on Database Theory (ICDT 2015), pages 380-397, 2015.

 

- With Pablo Muñoz. "Graph Logics with Rational Relations: The Role of Word Combinatorics".  In Proceedings 29th ACM-IEEE Symposium on Logic in Computer Science (CSL-LICS 2014), 12, 2014.

 

- With Miguel Romero and Moshe Vardi. "Does Query Evaluation Tractability Help Query Containment?".  In Proceedings 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2014), pages 188-199, 2014.

 

- With Gaelle Fontaine and Anthony Widjaja Lin. "Expressive Languages for Path Queries over Graphs with Data".  In Proceedings 19th Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2013), pages 71-85, 2013.

 

- "Querying Graph Databases".  Invited tutorial in Proceedings 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2013), pages 175-188, 2013.

 

- With Miguel Romero and Moshe Y. Vardi. "Semantic Acyclicity on Graph Databases".  In Proceedings 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'13), pages 237-248, 2013.

 

- With Jorge Perez and Juan Reutter. "Schema Mappings and Data Exchange for Graph Databases".  In Proceedings 16th International Conference on Database Theory (ICDT'13), pages 189-200, 2013.

 

- With Diego Figueira and Leonid Libkin. "Graph Logics with Rational Relations and the Generalized Intersection Problem".  In Proceedings 27th ACM/IEEE Symposium on Logic in Computer Science (LICS'12), pages 115-124, 2012.

 

- With Leonid Libkin and Miguel Romero. "Efficient Approximations of Conjunctive Queries".  In Proceedings 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'12), pages 249-260, 2012.

 

- With Leonid Libkin and Juan Reutter. "Parameterized Regular Expressions and Their Languages".  In Proceedings IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'11), pages 351-362, 2011.

 

- With Leonid Libkin and Juan Reutter. "Querying Graph Patterns".  In Proceedings 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'11), pages 199-210, 2011.

 

- With Carlos Hurtado, Leonid Libkin and Peter Wood. "Expressive Languages for Path Queries over Graph-structured Data".  In Proceedings 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'10), pages 3-14, 2010.

 

- With Leonid Libkin, Antonella Poggi, and Cristina Sirangelo. "XML with Incomplete Information: Models, Properties and Query Answering".  In Proceedings 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'09), pages 237-246, 2009.

 

- With Marcelo Arenas and Juan Reutter. "Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries".  In Proceedings 12th International Conference on Database Theory (ICDT 2009), pages 73-83, 2009.

 

- With Marcelo Arenas and Leonid Libkin. "Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization".  In Proceedings 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), vol. 4952 of Springer Lecture Notes in Computer Science, L. Arge, C. Cachin, T. Jurdzi'nski, A. Tarlecki, Eds., pages 888-899, 2007.

 

- With Rajeev Alur, Marcelo Arenas, Kousha Etessami, Neil Immerman and Leonid Libkin. "First-order and Temporal Logics for Nested Words".  In Proceedings 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), pages 151-160, 2007.

 

- With Marcelo Arenas and Leonid Libkin. "Combining Temporal Logics for Querying XML Documents". In Proceedings 11th International Conference on Database Theory (ICDT 2007), pages 359-373, 2007.

 

- With Leonid Libkin. "Temporal Logics over Unranked Trees". In Proceedings 20th IEEE Symposium on Logic in Computer Science (LICS 2005), pages 31-40, 2005.

 

- With Marcelo Arenas and Leonid Libkin. "Game-Based Notions of Locality over Finite Models". In Proceedings of 18th Annual Conference of the European Association for Computer Science Logic (CSL'04), vol. 3210 of Springer Lecture Notes in Computer Science, J. Marcinkowski, A. Tarlecki, Eds., pages 175-189, 2004.

 

- With Marcelo Arenas, Ronald Fagin and Leonid Libkin. "Locally Consistent Transformations and Query Answering in Data Exchange". In Proceedings of 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'04), pages 229-240, 2004.

 

- With Leopoldo Bertossi. "Logic Programs for Querying Inconsistent Databases". In "Practical Aspects of Declarative Languages: The Fifth International Symposium (PADL'03)", vol. 2562 of Springer Lecture Notes in Computer Science, Veronica Dahl, Phil Wadler, Eds., pages 339-356, 2003.

 

- With Leopoldo Bertossi. "Repairing Databases with Annotated Predicate Logic". In Proceedings of 9th International Workshop on Non-Monotonic Reasoning (NMR'O2), pages 160-170, 2002.