CRISTIAN RIVEROS
Website
"In their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind." E. W. Dijkstra, Turing Award Lecture, 1972
Department of Computer Science
Vicuna Mackenna 4860
Edificio San Agustin, 4to piso
Macul, Santiago, 7820436
+56 2 23547407
cristian.riveros@uc.cl
Conference papers
2021
When is Approximate Counting for Conjunctive Queries Tractable? [ pdf ]
With Marcelo Arenas, Rajesh Jayaram, and Luis Alberto Croquevielle. To appear in STOC. [More info]
Expressive power of linear algebra query languages [ pdf ]
With Floris Geerts, Thomas Muñoz, and Domagoj Vrgoč. To appear in PODS. [More info]
Ranked enumeration of MSO logic on words [ pdf ]
With Pierre Bourhis, Alejandro Grez, and Louis Jachiet. To appear in ICDT. [More info]
2020
A Family of Centrality Measures for Graph Data Based on Subgraphs [ pdf ]
With Jorge Salas. In ICDT. [More info]
On the Expressiveness of Languages for Complex Event Recognition [ pdf ]
With Alejandro Grez, Martin Ugarte, and Stijn Vansummeren. In ICDT. [More info]
Towards Streaming Evaluation of Queries with Correlation in Complex Event Processing [ pdf ]
With Alejandro Grez. In ICDT. [More info]
2019
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation [ pdf | slides ] ( Best paper award )
With Marcelo Arenas, Rajesh Jayaram, and Luis Alberto Croquevielle. In PODS. [More info]
A Formal Framework for Complex Event Processing [ pdf ]
With Alejandro Grez and Martin Ugarte. In ICDT. [More info]
A Worst-Case Optimal Join Algorithm for SPARQL [ pdf ]
With Aidan Hogan, Carlos Rojas, and Adrian Soto. In ISWC. [More info]
2018
Constant Delay Algorithms for Regular Document Spanners [ pdf | slides ]
With Fernando Florenzano, Martin Ugarte, Stijn Vansummeren, and Domagoj Vrgoč. In PODS. [More info]
Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity [ pdf ]
With Francisco Maturana and Domagoj Vrgoč. In PODS. [More info]
Pumping Lemmas for Weighted Automata [ pdf ]
With Filip Mazowiecki. In STACS. [More info]
2017
Descriptive Complexity for counting complexity classes [ pdf | slides ]
With Marcelo Arenas and Martin Muñoz. In LICS. [More info]
Probabilistic Automata of Bounded Ambiguity [ pdf ]
With Nathanaël Fijalkow and James Worrell. In CONCUR. [More info]
2016
Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties [ pdf ]
With Filip Mazowiecki. In STACS. [More info]
A framework for annotating CSV-like data [ pdf ]
With Marcelo Arenas, Francisco Maturana, and Domagoj Vrgoč. In VLDB. [More info]
Querying Wikidata: Comparing SPARQL, Relational and Graph Databases [ pdf ]
With Daniel Hernández, Aidan Hogan, Carlos Rojas, and Enzo Zerega. In ISWC. [More info]
2015
Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata [ pdf ]
With Filip Mazowiecki. In CSL. [More info]
2013
Quantitative Monadic Second-Order Logic [ pdf | slides ]
With Stephan Kreutzer. In LICS. [More info]
Which DTDs are streaming bounded repairable? [ pdf | slides ]
With Pierre Bourhis and Gabriele Puppis. In ICDT. [More info]
2012
Bounded repairability for regular tree languages [ pdf | slides ]
With Gabriele Puppis and Slawek Staworko. In ICDT. [More info]
2011
The cost of traveling between languages [ pdf | slides ]
With Michael Benedikt and Gabriele Puppis. In ICALP. [More info]
Regular repair of specifications [ pdf | slides ]
With Michael Benedikt and Gabriele Puppis. In LICS. [More info]
2010
Foundations of schema mapping management [ pdf ]
With Marcelo Arenas, Jorge Pérez, and Juan Reutter. In PODS. [More info]
2009
Inverting schema mappings: Bridging the gap between theory and practice [ pdf ]
With Marcelo Arenas, Jorge Pérez, and Juan Reutter. In VLDB. [More info]
2008
The Recovery of a schema mapping: Bringing exchanged data back [ pdf ]
With Marcelo Arenas and Jorge Pérez. In PODS. [More info]
Journal versions
2020
Efficient Enumeration Algorithms for Regular Document Spanners [ pdf ]
With Fernando Florenzano, Martin Ugarte, Stijn Vansummeren, and Domagoj Vrgoč. In TODS. [More info]
Descriptive Complexity for Counting Complexity Classes [ pdf ]
With Marcelo Arenas and Martin Muñoz. In LMCS. [More info]
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation [ pdf ]
With Marcelo Arenas, Rajesh Jayaram, and Luis Alberto Croquevielle. In SIGMOD Record. [More info]
Probabilistic Automata of Bounded Ambiguity [ pdf ]
With Nathanaël Fijalkow and James Worrell. In Information and Computation. [More info]
2019
Copyless cost-register automata: Structure, expressiveness, and closure properties [ pdf ]
With Filip Mazowiecki. In JCSS. [More info]
2016
Bounded Repairability for Regular Tree Languages [ pdf ]
With Pierre Bourhis, Gabriele Puppis, and Slawek Staworko. In TODS. [More info]
A framework for annotating CSV-like data [ pdf ]
With Marcelo Arenas, Francisco Maturana, and Domagoj Vrgoč. In VLDB. [More info]
2015
Which XML Schemas are Streaming Bounded Repairable? [ pdf ]
With Pierre Bourhis and Gabriele Puppis. In ToCS. [More info]
2014
The per-character cost of repairing word languages [ pdf ]
With Michael Benedikt and Gabriele Puppis. In TCS. [More info]
2013
Bounded repairability of word languages [ pdf ]
With Michael Benedikt and Gabriele Puppis. In JCSS. [More info]
The language of plain SO-tgds: composition, inversion and structural properties [ pdf ]
With Marcelo Arenas, Jorge Pérez, and Juan Reutter. In JCSS. [More info]
2012
Query language-based inverses of schema mappings: semantics, computation, and closure properties [ pdf ]
With Marcelo Arenas, Jorge Pérez, and Juan Reutter. In VLDBJ. [More info]
2009
Composition and inversion of schema mappings [ pdf ]
With Marcelo Arenas, Jorge Pérez, and Juan Reutter. In SIGMOD Record. [More info]
The Recovery of a schema mapping: Bringing exchanged data back [ pdf ]
With Marcelo Arenas and Jorge Pérez. In TODS. [More info]

I am an Assistant Professor at the Department of Computer Science at the Pontificia Universidad Catolica de Chile. picture I received a D.Phil from the University of Oxford in 2013 and a M.Sc from Pontificia Universidad Católica de Chile in 2008. I was previously studying at Pontificia Universidad Católica de Chile as an undergraduate student where I received a B.A. in Mathematics in 2006 and my Professional Degree in Computer Engineering in 2008.

My research interests are mostly in data management systems, specifically, in data streams, information extraction, and graph data. Also, I do research on theoretical computer science, mostly in automata theory, logics, and computational complexity.