2022

Chistikov, Dmitry, Haase, Christoph, Hadizadeh, Zahra and Mansutti, Alessio (2022) Higher-order quantified Boolean satisfiability. In: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria, 22-26 Aug 2022. Published in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), 241 ISBN 9783959772563. doi:10.4230/LIPIcs.MFCS.2022.33 ISSN 1868-8969.

Chistikov, Dmitry, Haase, Christoph and Mansutti, Alessio (2022) Geometric decision procedures and the VC dimension of linear arithmetic theories. In: 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), Haifa, Israel, 02–05 Aug 2022. Published in: LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science pp. 1-13. ISBN 9781450393515. doi:10.1145/3531130.3533372

Almagor, Shaull, Chistikov, Dmitry, Ouaknine, Joël and Worrell, James (2022) O-minimal invariants for discrete-time dynamical systems. ACM Transactions on Computational Logic (TOCL), 23 (2). pp. 1-20. 9. doi:10.1145/3501299 ISSN 1529-3785.

Chistikov, Dmitry, Kiefer, Stefan, Murawski, Andrzej S. and Purser, David (2022) The big-O problem. Logical Methods in Computer Science, 18 (1). 40:1-40:50. doi:10.46298/lmcs-18(1:40)2022 ISSN 1860-5974.

Chistikov, Dmitry, Majumdar, Rupak and Schepper, Philipp (2022) Subcubic certificates for CFL reachability. In: ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2022), Philadelphia, Pennsylvania, United States, 16-22 Jan 2022. Published in: Proceedings of the ACM on Programming Languages, 6 (POPL). doi:10.1145/3498702 ISSN 2475-1421.

Chistikov, Dmitry, Haase, Christoph and Mansutti, Alessio (2022) Quantifier elimination for counting extensions of Presburger arithmetic. In: 25th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2022), Munich, Germany, 2-7 Apr 2022. Published in: Foundations of Software Science and Computation Structures, 13242 pp. 225-243. ISBN 9783030992521. doi:10.1007/978-3-030-99253-8_12 ISSN 0302-9743.

2020

Chistikov, Dmitry, Kiefer, Stefan, Murawski, Andrzej S. and Purser, David (2020) The big-O problem for labelled markov chains and weighted automata. In: 31st International Conference on Concurrency Theory (CONCUR 2020), 1-4 Sep 2020. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 171 41:1-41:19. ISBN 9783959771603. doi:10.4230/LIPIcs.CONCUR.2020.41 ISSN 1868-8969.

Chistikov, Dmitry and Vyalyi, Mikhail (2020) Re-pairing brackets. In: The 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020), 8-11 Jul 2020. Published in: LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science pp. 312-326. ISBN 9781450371049. doi:10.1145/3373718.3394752

Chistikov, Dmitry, Goulko, Olga, Kent, Adrian and Paterson, Michael S. (2020) Globe-hopping. Proceedings of the Royal Society A : mathematical, physical and engineering sciences, 476 (2238). doi:10.1098/rspa.2020.0038 ISSN 1364-5021.

Chistikov, Dmitry and Haase, Christoph (2020) On the power of ordering in linear arithmetic theories. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020. Published in: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) pp. 1-15. ISBN 9783959771382. doi:10.4230/LIPIcs.ICALP.2020.119 ISSN 1868-8969.

Chistikov, Dmitry, Cadilhac, Michael and Zetzsche, Georg (2020) Rational subsets of Baumslag-Solitar groups. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 8-11 Jul 2020. Published in: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) pp. 1-16. ISBN 9783959771382. doi:10.4230/LIPIcs.ICALP.2020.116 ISSN 1868-8969.

2019

Chistikov, Dmitry, Lisowski, Grzegorz, Paterson, Michael S. and Turrini, Paolo (2019) Convergence of opinion diffusion is PSPACE-complete. In: AAAI-34th conference on Artificial Intelligence, New York, New York, 7-12 Feb 2020. Published in: Proceedings of The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020 pp. 7103-7110.

Chistikov, Dmitry, Murawski, Andrzej S. and Purser, David (2019) Asymmetric distances for approximate differential privacy. In: 30th International Conference on Concurrency Theory (CONCUR 2019), Amsterdam, Netherlands, 27-30 Aug 2019, 140 pp. 1-17. ISBN 9783959771214. doi:10.4230/LIPIcs.CONCUR.2019.10 ISSN 1868-8969.

Chistikov, Dmitry, Czerwiński, Wojciech , Hofman, Piotr , Pilipczuk, Michał and Wehar, Michael (2019) Shortest paths in one-counter systems. Logical Methods in Computer Science, 15 (1). 19:1-19:28. doi:10.23638/LMCS-15(1:19)2019 ISSN 1860-5974.

Chistikov, Dmitry, Martyugin, Pavel and Shirmohammadi, Mahsa (2019) Synchronizing automata over nested words. Journal of Automata, Languages and Combinatorics, 24 (2-4). pp. 219-251. doi:10.25596/jalc-2019-219 ISSN 1430-189X.

2018

Chistikov, Dmitry and Paterson, Mike (2018) Globe-hopping [pre-print]. Working Paper. Coventry, UK: University of Warwick. (Unpublished)

Chistikov, Dmitry, Murawski, Andrzej S. and Purser, David (2018) Bisimilarity distances for approximate differential privacy. In: International Symposium on Automated Technology for Verification and Analysis 2018, Los Angeles, USA, Oct 7-10 2018. Published in: Lecture Notes in Computer Science, 11138 pp. 194-210. ISBN 9783030010898. doi:10.1007/978-3-030-01090-4_12 ISSN 0302-9743.

Chistikov, Dmitry, Haase, Christoph and Halfon, Simon (2018) Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 735 . pp. 147-161. doi:10.1016/j.tcs.2016.06.017 ISSN 0304-3975.

Almagor, Shaull, Chistikov, Dmitry, Ouaknine, Joel and Worrell, James (2018) O-minimal invariants for linear loops. In: ICALP 2018: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9-13 Jul 2018. Published in: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107 114:1-114:14. ISBN 9783959770767. doi:10.4230/LIPIcs.ICALP.2018.114 ISSN 1868-8969.

2017

Chistikov, Dmitry, Dimitrova, Rayna and Majumdar, Rupak (2017) Approximate counting in SMT and value estimation for probabilistic programs. ACTA Informatica, 54 (8). pp. 729-764. doi:10.1007/s00236-017-0297-2 ISSN 0001-5903.

Chistikov, Dmitry and Haase, Christoph (2017) On the complexity of quantified integer programming. In: The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 July 2017. Published in: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 80 94:1-94:13. ISBN 9783959770415. doi:10.4230/LIPIcs.ICALP.2017.94 ISSN 1868-8969.

Chistikov, Dmitry, Iván, S., Lubiw, A. and Shallit, J. (2017) Fractional coverings, greedy coverings, and rectifier networks. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hannover, Germany, 8-11 Mar 2017. Published in: Leibniz International Proceedings in Informatics, LIPIcs, 66 23:1-23:14. ISBN 9783959770286. ISSN 1868-8969.

Chistikov, Dmitry, Kiefer, Stefan, Marušić, Ines, Shirmohammadi, Mahsa and Worrell, James (2017) Nonnegative matrix factorization requires irrationality. SIAM Journal on Applied Algebra and Geometry, 1 (1). pp. 285-307. doi:10.1137/16M1078835 ISSN 2470-6566.

Chistikov, D., Kiefer, S., Marušić, I., Shirmohammadi, M. and Worrell, J. (2017) On rationality of nonnegative matrix factorization. In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain, 16-19 Jan 2017. Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1290-1305. ISBN 9781611974782. doi:10.1137/1.9781611974782.84 ISSN 1071-9040.

2016

Atig, Mohamed Faouzi, Chistikov, Dmitry, Hofman, Piotr, Kumar, K. Narayan, Saivasan, Prakash and Zetzsche, Georg (2016) The complexity of regular abstractions of one-counter languages. In: 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5–8 Jul 2016. Published in: LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science pp. 207-216. ISBN 9781450343916 . doi:10.1145/2933575.2934561

Chistikov, Dmitry, Majumdar, Rupak and Niksic, Filip (2016) Hitting families of schedules for asynchronous programs. In: 28th International Conference, CAV 2016, Toronto, ON, Canada, 17-23 Jul 2016. Published in: Computer Aided Verification. CAV 2016., 9780 pp. 157-176. ISBN 9783319415390. doi:10.1007/978-3-319-41540-6_9 ISSN 0302-9743.

Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M. and Worrell, J. (2016) On restricted nonnegative matrix factorization. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016. Published in: Leibniz International Proceedings in Informatics, LIPIcs, 55 103:1-103:14. ISBN 9783959770132. ISSN 1868-8969.

Chistikov, Dmitry, Czerwiński, Wojciech, Hofman, Piotr, Pilipczuk, Michał and Wehar, Michael (2016) Shortest paths in one-counter systems. In: 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Apr 2016. Published in: Foundations of Software Science and Computation Structures. FoSSaCS 2016, 9634 pp. 462-478. ISBN 9783662496299. doi:10.1007/978-3-662-49630-5_27 ISSN 0302-9743.

Chistikov, Dmitry, Martyugin, Pavel and Shirmohammadi, Mahsa (2016) Synchronizing automata over nested words. In: 19th International Conference, FOSSACS 2016, Eindhoven, The Netherlands, 2-8 Arp 2016. Published in: Foundations of Software Science and Computation Structures. FoSSaCS 2016, 9634 pp. 252-268. ISBN 9783662496299. doi:10.1007/978-3-662-49630-5_15 ISSN 0302-9743.

Chistikov, Dmitry and Haase, Christoph (2016) The taming of the semi-linear set. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 55 (128). 128:1-128:13. ISBN 9783959770132. doi:10.4230/LIPIcs.ICALP.2016.128 ISSN 1868-8969.

2015

Chistikov, Dmitry, Dimitrova, Rayna and Majumdar, Rupak (2015) Approximate counting in SMT and value estimation for probabilistic programs. In: 21st International Conference, TACAS 2015, London, UK, 11-18 Apr 2015. Published in: Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2015, 9035 pp. 320-334. doi:10.1007/978-3-662-46681-0_26 ISSN 0302-9743.

2014

Chistikov, Dmitry, Fedorova, Valentina and Voronenko, Andrey (2014) Certificates of non-membership for classes of read-once functions. Fundamenta Informaticae, 132 (1). pp. 63-77. ISSN 0169-2968.

Chistikov, Dmitry (2014) Notes on counting with finite machines. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), New Delhi, India, 15–17 Dec 2014, 29 pp. 339-350. ISBN 9783939897774. ISSN 1868-8969.

Chistikov, Dmitry and Majumdar, Rupak (2014) Unary pushdown automata and straight-line programs. In: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8-11 Jul 2014. Published in: Automata, Languages, and Programming. ICALP 2014, 8573 pp. 146-157. ISBN 9783662439500. doi:10.1007/978-3-662-43951-7_13 ISSN 0302-9743.