Dmitry Chistikov

According to our database, Dmitry Chistikov authored at least 42 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Integer Linear-Exponential Programming in NP by Quantifier Elimination.

Dmitry Chistikov, Alessio Mansutti, Mikhail R. Starchak

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Invariants for One-Counter Automata with Disequality Tests.

Dmitry Chistikov, Jérôme Leroux, Henry Sinclair-Banks, Nicolas Waldburger

Proceedings of the 35th International Conference on Concurrency Theory, 2024

Learning a Social Network by Influencing Opinions.

Dmitry Chistikov, Luisa Estrada, Mike Paterson, Paolo Turrini

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, 2024

2023

Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs.

Dmitry Chistikov, Matthias Englert, Ranko Lazic

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The Complexity of Presburger Arithmetic with Power or Powers.

Michael Benedikt, Dmitry Chistikov, Alessio Mansutti

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Acyclic Petri and Workflow Nets with Resets.

Dmitry Chistikov, Wojciech Czerwinski, Piotr Hofman, Filip Mazowiecki, Henry Sinclair-Banks

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

2022

O-Minimal Invariants for Discrete-Time Dynamical Systems.

Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, James Worrell

ACM Trans. Comput. Log., 2022

Subcubic certificates for CFL reachability.

Dmitry Chistikov, Rupak Majumdar, Philipp Schepper

Proc. ACM Program. Lang., 2022

The Big-O Problem.

Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, David Purser

Log. Methods Comput. Sci., 2022

Higher-Order Quantified Boolean Satisfiability.

Dmitry Chistikov, Christoph Haase, Zahra Hadizadeh, Alessio Mansutti

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

Geometric decision procedures and the VC dimension of linear arithmetic theories.

Dmitry Chistikov, Christoph Haase, Alessio Mansutti

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Quantifier elimination for counting extensions of Presburger arithmetic.

Dmitry Chistikov, Christoph Haase, Alessio Mansutti

Proceedings of the Foundations of Software Science and Computation Structures, 2022

2021

Presburger arithmetic with threshold counting quantifiers is easy.

Dmitry Chistikov, Christoph Haase, Alessio Mansutti

CoRR, 2021

2020

Globe-hopping.

Dmitry Chistikov, Olga Goulko, Adrian Kent, Mike Paterson

CoRR, 2020

Re-pairing brackets.

Dmitry Chistikov, Mikhail Vyalyi

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

On the Power of Ordering in Linear Arithmetic Theories.

Dmitry Chistikov, Christoph Haase

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Rational Subsets of Baumslag-Solitar Groups.

Michaël Cadilhac, Dmitry Chistikov, Georg Zetzsche

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

The Big-O Problem for Labelled Markov Chains and Weighted Automata.

Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski, David Purser

Proceedings of the 31st International Conference on Concurrency Theory, 2020

Convergence of Opinion Diffusion is PSPACE-Complete.

Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson, Paolo Turrini

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Shortest paths in one-counter systems.

Dmitry Chistikov, Wojciech Czerwinski, Piotr Hofman, Michal Pilipczuk, Michael Wehar

Log. Methods Comput. Sci., 2019

Synchronizing Automata over Nested Words.

Dmitry Chistikov, Pavel Martyugin, Mahsa Shirmohammadi

J. Autom. Lang. Comb., 2019

Asymmetric Distances for Approximate Differential Privacy.

Dmitry Chistikov, Andrzej S. Murawski, David Purser

Proceedings of the 30th International Conference on Concurrency Theory, 2019

2018

Context-free commutative grammars with integer counters and resets.

Dmitry Chistikov, Christoph Haase, Simon Halfon

Theor. Comput. Sci., 2018

O-Minimal Invariants for Linear Loops.

Shaull Almagor, Dmitry Chistikov, Joël Ouaknine, James Worrell

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Bisimilarity Distances for Approximate Differential Privacy.

Dmitry Chistikov, Andrzej S. Murawski, David Purser

Proceedings of the Automated Technology for Verification and Analysis, 2018

2017

Nonnegative Matrix Factorization Requires Irrationality.

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell

SIAM J. Appl. Algebra Geom., 2017

Approximate counting in SMT and value estimation for probabilistic programs.

Dmitry Chistikov, Rayna Dimitrova, Rupak Majumdar

Acta Informatica, 2017

Fractional Coverings, Greedy Coverings, and Rectifier Networks.

Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, Jeffrey O. Shallit

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

On Rationality of Nonnegative Matrix Factorization.

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Complexity of Quantified Integer Programming.

Dmitry Chistikov, Christoph Haase

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The complexity of regular abstractions of one-counter languages.

Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman, K. Narayan Kumar, Prakash Saivasan, Georg Zetzsche

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

On Restricted Nonnegative Matrix Factorization.

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

The Taming of the Semi-Linear Set.

Dmitry Chistikov, Christoph Haase

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Hitting Families of Schedules for Asynchronous Programs.

Dmitry Chistikov, Rupak Majumdar, Filip Niksic

Proceedings of the Computer Aided Verification - 28th International Conference, 2016

2014

Certificates of Non-Membership for Classes of Read-Once Functions.

Dmitry Chistikov, Valentina Fedorova, Andrey A. Voronenko

Fundam. Informaticae, 2014

Unary Pushdown Automata and Straight-Line Programs.

Dmitry Chistikov, Rupak Majumdar

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Notes on Counting with Finite Machines.

Dmitry Chistikov

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

2013

A Uniformization Theorem for Nested Word to Word Transductions.

Dmitry Chistikov, Rupak Majumdar

Proceedings of the Implementation and Application of Automata, 2013

2012

Checking Tests for Read-Once Functions over Arbitrary Bases.

Dmitry V. Chistikov

Proceedings of the Computer Science - Theory and Applications, 2012

2011

An Upper Bound on Checking Test Complexity for Almost All Cographs.

Oleg V. Zubkov, Dmitry V. Chistikov, Andrey A. Voronenko

Proceedings of the 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2011

Testing Monotone Read-Once Functions.

Dmitry V. Chistikov

Proceedings of the Combinatorial Algorithms - 22nd International Workshop, 2011

2010

Learning Read-Once Functions Using Subcube Identity Queries

Dmitry V. Chistikov, Andrey A. Voronenko

CoRR, 2010