Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Theoretical Computer Science

Publications, Preprints, Poster

 
Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration
joint work with Maximilian Merz
Conference version: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'21), to appear.
Constant Delay Enumeration for Conjunctive Queries — a Tutorial
joint work with Fabian Gerhardt and Nicole Schweikardt
Tutorial: SIGLOG News, Volume 7, Issue 1, pp. 4-33, 2020.
Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration
joint work with Nofar Carmeli, Benny Kimelfeld, Nicole Schweikardt, Shai Zeevi
Preprint: CoRR, vol. abs/1912.10704, 2019.
Conference version: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'20), pp. 393–409, 2020.
Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width
joint work with Nicole Schweikardt
Conference version: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS'19), pp. 58:1-58:15, 2019.
Compiling Existential Positive Queries to Bounded-Variable Fragments
joint work with Hubie Chen
Conference version: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS'19), pp. 353-364, 2019.
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs
Preprint: Electronic Colloquium on Computational Complexity (ECCC), Report No. 154 (2017).
Conference version: Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS'18), 11:1--11:14, 2018.
Answering UCQs under updates and in the presence of integrity constraints
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1709.10039, 2017.
Conference version: Proceedings of the 21th International Conference on Database Theory (ICDT'18), pp. 8:1--8:19, 2018.
Answering FO+MOD queries under updates on bounded degree databases
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1702.08764, 2017.
Conference version: Proceedings of the 20th International Conference on Database Theory (ICDT'17), pp.8:1-8:18, 2017.
Journal version: Invited to ACM Transactions on Database Systems (TODS).
Answering Conjunctive Queries under Updates
joint work with Jens Keppeler and Nicole Schweikardt
Preprint: CoRR, vol. abs/1702.06370, 2017.
Conference version: Proceedings of the 36th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'17), pp.303-318, 2017.
Poster: The poster presented at PODS'17.
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
joint work with Martin Grohe
Preprint: CoRR, vol. abs/1607.04287, 2016.
Conference version: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pp.327-339, 2017.
Supercritical Space-Width Trade-offs for Resolution
joint work with Jakob Nordström
Journal version: SIAM Journal on Computing (SICOMP), Volume 49, Issue 1, pp. 98-118, 2020.
Conference version: Proceedings of the 43nd International Colloquium on Automata, Languages and Programming (ICALP'16), pp.57:1-57:14, 2016.
Preprint: CoRR, vol. abs/1612.07162, 2016.
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
joint work with Jakob Nordström
Journal version: Journal of the ACM, accepted for publication.
Preprint: CoRR, vol. abs/1608.08704, 2016.
Conference version: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), pp.267-276, 2016.
Limitations of Algebraic Approaches to Graph Isomorphism Testing
joint work with Martin Grohe
Preprint: CoRR, vol. abs/1502.05912, 2015.
Conference version: Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP'15).
Parameterized Complexity of Fixed-Variable Logics
joint work with Michael Elberfeld
Conference version: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'14).
The Propagation Depth of Local Consistency
Preprint: CoRR, vol. abs/1406.4679, 2014.
Conference version: Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP'14), 2014.
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
joint work with Paul Bonsma and Martin Grohe
Journal version: Theory of Computing Systems (TOCS), Volume 60, Issue 4, pp. 581–614, 2017.
Preprint: CoRR, vol. abs/1509.08251, 2015.
Conference version: Proceedings of the 21st Annual European Symposium on Algorithms (ESA'13), Lecture Notes in Computer Science 8125, pp.145-156, 2013.
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy
joint work with Andreas Krebs and Oleg Verbitsky
Journal version: ACM Transactions on Computational Logic (TOCL), Volume 16, Issue 3, 2015.
Preprint: CoRR, vol. abs/1212.2747, 2013.
Conference version: Proceedings of the 22nd EACSL Annual Conference on Computer Science Logic (CSL'13), pp.61-80, 2013.
On the speed of constraint propagation and the time complexity of arc consistency testing
joint work with Oleg Verbitsky
Preprint: CoRR, vol. abs/1303.7077, 2012.
Conference version: Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS '13), Lecture Notes in Computer Science Volume 8087, pp.159-170, 2013.
Journal version: Journal of Computer and System Sciences (JCSS), Volume 91, pp.104-114, 2018.
On the Complexity of Finding Narrow Proofs
Preprint: CoRR, vol. abs/1204.0775, 2012.
Conference version: Proceedings of the 53th IEEE Symposium on Foundations of Computer Science (FOCS'12), pp.351-360, 2012.
Lower Bounds for Existential Pebble Games and k-Consistency Tests
Journal version: Logical Methods in Computer Science (LMCS), Volume 9, Issue 4, 2013.
Conference version: Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LICS'12), pp.25-34, 2012.

Theses

Lower Bounds for Heuristic Algorithms
Dissertation: RWTH Aachen University, 2014.
Summary (in german): Untere Schranken für heuristische Algorithmen. In: Steffen Hölldobler et. al. (Hrsg.). Ausgezeichnete Informatikdissertationen 2014, pp.31-40, Lecture Notes in Informatics (LNI), Gesellschaft für Informatik, Bonn 2015. LINK
Über die Schaltkreiskomplexität parametrisierter Probleme
Diploma thesis (in german): Humboldt-Universität zu Berlin, 2010.