7 citations · 32 across the 13 of their papers we have counts for
22 papers
Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs
Dmitry Chistikov, Matthias Englert, Ranko Lazic
We prove that, for the fundamental regression task of learning a single neuron, training a one-hidden layer ReLU network of any width by gradient flow from a small initialisation c…
The complexity of Presburger arithmetic with power or powers
Michael Benedikt, Dmitry Chistikov, Alessio Mansutti
We investigate expansions of Presburger arithmetic, i.e., the theory of the integers with addition and order, with additional structure related to exponentiation: either a function…
Presburger arithmetic with threshold counting quantifiers is easy
Dmitry Chistikov, Christoph Haase, Alessio Mansutti
We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier that determines whether the nu…
Subcubic Certificates for CFL Reachability
Dmitry Chistikov, Rupak Majumdar, Philipp Schepper
Many problems in interprocedural program analysis can be modeled as the context-free language (CFL) reachability problem on graphs and can be solved in cubic time. Despite years of…
The Big-O Problem
Dmitry Chistikov, Stefan Kiefer, Andrzej S. Murawski +1
Given two weighted automata, we consider the problem of whether one is big-O of the other, i.e., if the weight of every finite word in the first is not greater than some constant m…
Rational subsets of Baumslag-Solitar groups
Michaël Cadilhac, Dmitry Chistikov, Georg Zetzsche
We consider the rational subset membership problem for Baumslag-Solitar groups. These groups form a prominent class in the area of algorithmic group theory, and they were recently…
Globe-hopping
Dmitry Chistikov, Olga Goulko, Adrian Kent +1
We consider versions of the grasshopper problem (Goulko and Kent, 2017) on the circle and the sphere, which are relevant to Bell inequalities. For a circle of circumference , w…
Convergence of Opinion Diffusion is PSPACE-complete
Dmitry Chistikov, Grzegorz Lisowski, Mike Paterson +1
We analyse opinion diffusion in social networks, where a finite set of individuals is connected in a directed graph and each simultaneously changes their opinion to that of the maj…
Re-pairing brackets
Dmitry Chistikov, Mikhail Vyalyi
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can pair any opening bracket with any closing bracket to…
Bisimilarity Distances for Approximate Differential Privacy
Dmitry Chistikov, Andrzej S. Murawski, David Purser
Differential privacy is a widely studied notion of privacy for various models of computation. Technically, it is based on measuring differences between probability distributions. W…
O-Minimal Invariants for Discrete-Time Dynamical Systems
Shaull Almagor, Dmitry Chistikov, Joël Ouaknine +1
Termination analysis of linear loops plays a key rôle in several areas of computer science, including program verification and abstract interpretation. Already for the simplest var…
On Restricted Nonnegative Matrix Factorization
Dmitry Chistikov, Stefan Kiefer, Ines Marušić +2
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative matrix into a product of a nonnegative matrix and a nonne…
Nonnegative Matrix Factorization Requires Irrationality
Dmitry Chistikov, Stefan Kiefer, Ines Marušić +2
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative matrix into a product of a nonnegative matrix and a nonne…
Complexity of regular abstractions of one-counter languages
Mohamed Faouzi Atig, Dmitry Chistikov, Piotr Hofman +3
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA)…
Hitting Families of Schedules for Asynchronous Programs
Dmitry Chistikov, Rupak Majumdar, Filip Niksic
We consider the following basic task in the testing of concurrent systems. The input to the task is a partial order of events, which models actions performed on or by the system an…
Context-Free Commutative Grammars with Integer Counters and Resets
Dmitry Chistikov, Christoph Haase, Simon Halfon
We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on…
Shortest paths in one-counter systems
Dmitry Chistikov, Wojciech Czerwiński, Piotr Hofman +2
We show that any one-counter automaton with states, if its language is non-empty, accepts some word of length at most . This closes the gap between the previously known…
Fractional coverings, greedy coverings, and rectifier networks
Dmitry Chistikov, Szabolcs Iván, Anna Lubiw +1
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix that has a in the entry iff there is a…
Approximate Counting in SMT and Value Estimation for Probabilistic Programs
Dmitry Chistikov, Rayna Dimitrova, Rupak Majumdar
#SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and com…
Unary Pushdown Automata and Straight-Line Programs
Dmitry Chistikov, Rupak Majumdar
We consider decision problems for deterministic pushdown automata over a unary alphabet (udpda, for short). Udpda are a simple computation model that accept exactly the unary regul…
Checking Tests for Read-Once Functions over Arbitrary Bases
Dmitry V. Chistikov
A Boolean function is called read-once over a basis B if it can be expressed by a formula over B where no variable appears more than once. A checking test for a read-once function…
Learning Read-Once Functions Using Subcube Identity Queries
Dmitry V. Chistikov, Andrey A. Voronenko
We consider the problem of exact identification for read-once functions over arbitrary Boolean bases. We introduce a new type of queries (subcube identity ones), discuss its connec…