Source author record

Dmitry Chistikov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Computational Complexity Logic in Computer Science Discrete Mathematics Artificial Intelligence Machine Learning math-ph math.AG math.CA math.CO math.GR math.MP Multiagent Systems Programming Languages quant-ph Software Engineering

Catalog footprint

Research overview

14works

16topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Presburger arithmetic with threshold counting quantifiers is easy

We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier $\exists^{\ge c} y$ that determines whether the number of different $y$ satisfying some formula is at least $c \in \mathbb N$ , where $c$ is given in binary. Using a standard quantifier elimination procedure for Presburger arithmetic, the resulting theory is easily seen to be decidable in 4ExpTime. Our main contribution is to develop a novel quantifier-elimination procedure for a more general counting quantifier that decides this theory in 3ExpTime, meaning that it is no harder to decide than standard Presburger arithmetic. As a side result, we obtain an improved quantifier elimination procedure for Presburger arithmetic with counting quantifiers as studied by Schweikardt [ACM Trans. Comput. Log., 6(3), pp. 634-671, 2005], and a 3ExpTime quantifier-elimination procedure for Presburger arithmetic extended with a generalised modulo counting quantifier.

preprint2021arXiv

Subcubic Certificates for CFL Reachability

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 efforts, there are no known truly sub-cubic algorithms for this problem. We study the related certification task: given an instance of CFL reachability, are there small and efficiently checkable certificates for the existence and for the non-existence of a path? We show that, in both scenarios, there exist succinct certificates ( $O(n^2)$ in the size of the problem) and these certificates can be checked in subcubic (matrix multiplication) time. The certificates are based on grammar-based compression of paths (for positive instances) and on invariants represented as matrix constraints (for negative instances). Thus, CFL reachability lies in nondeterministic and co-nondeterministic subcubic time. A natural question is whether faster algorithms for CFL reachability will lead to faster algorithms for combinatorial problems such as Boolean satisfiability (SAT). As a consequence of our certification results, we show that there cannot be a fine-grained reduction from SAT to CFL reachability for a conditional lower bound stronger than $n^ω$ , unless the nondeterministic strong exponential time hypothesis (NSETH) fails. Our results extend to related subcubic equivalent problems: pushdown reachability and two-way nondeterministic pushdown automata (2NPDA) language recognition. For example, we describe succinct certificates for pushdown non-reachability (inductive invariants) and observe that they can be checked in matrix multiplication time. We also extract a new hardest 2NPDA language, capturing the "hard core" of all these problems.

preprint2020arXiv

Convergence of Opinion Diffusion is PSPACE-complete

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 majority of their influencers. We study the algorithmic properties of the fixed-point behaviour of such networks, showing that the problem of establishing whether individuals converge to stable opinions is PSPACE-complete.

preprint2020arXiv

Globe-hopping

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 $2π$ , we show that for unconstrained lawns of any length and arbitrary jump lengths, the supremum of the probability for the grasshopper's jump to stay on the lawn is one. For antipodal lawns, which by definition contain precisely one of each pair of opposite points and have length $π$ , we show this is true except when the jump length $ϕ$ is of the form $π\frac{p}{q}$ with $p,q$ coprime and $p$ odd. For these jump lengths we show the optimal probability is $1 - 1/q$ and construct optimal lawns. For a pair of antipodal lawns, we show that the optimal probability of jumping from one onto the other is $1 - 1/q$ for $p,q$ coprime, $p$ odd and $q$ even, and one in all other cases. For an antipodal lawn on the sphere, it is known (Kent and Pitalúa-García, 2014) that if $ϕ= π/q$ , where $q \in \mathbb N$ , then the optimal retention probability of $1-1/q$ for the grasshopper's jump is provided by a hemispherical lawn. We show that in all other cases where $0<ϕ< π/2$ , hemispherical lawns are not optimal, disproving the hemispherical colouring maximality hypotheses (Kent and Pitalúa-García, 2014). We discuss the implications for Bell experiments and related cryptographic tests.

preprint2020arXiv

O-Minimal Invariants for Discrete-Time Dynamical Systems

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 variants of linear loops the question of termination relates to deep open problems in number theory, such as the decidability of the Skolem and Positivity Problems for linear recurrence sequences, or equivalently reachability questions for discrete-time linear dynamical systems. In this paper, we introduce the class of \emph{o-minimal invariants}, which is broader than any previously considered, and study the decidability of the existence and algorithmic synthesis of such invariants as certificates of non-termination for linear loops equipped with a large class of halting conditions. We establish two main decidability results, one of them conditional on Schanuel's conjecture in transcendental number theory.

preprint2020arXiv

Rational subsets of Baumslag-Solitar groups

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 identified as an obstacle for understanding the rational subsets of $\text{GL}(2,\mathbb{Q})$ . We show that rational subset membership for Baumslag-Solitar groups $\text{BS}(1,q)$ with $q\ge 2$ is decidable and PSPACE-complete. To this end, we introduce a word representation of the elements of $\text{BS}(1,q)$ : their pointed expansion (PE), an annotated $q$ -ary expansion. Seeing subsets of $\text{BS}(1,q)$ as word languages, this leads to a natural notion of PE-regular subsets of $\text{BS}(1, q)$ : these are the subsets of $\text{BS}(1,q)$ whose sets of PE are regular languages. Our proof shows that every rational subset of $\text{BS}(1,q)$ is PE-regular. Since the class of PE-regular subsets of $\text{BS}(1,q)$ is well-equipped with closure properties, we obtain further applications of these results. Our results imply that (i) emptiness of Boolean combinations of rational subsets is decidable, (ii) membership to each fixed rational subset of $\text{BS}(1,q)$ is decidable in logarithmic space, and (iii) it is decidable whether a given rational subset is recognizable. In particular, it is decidable whether a given finitely generated subgroup of $\text{BS}(1,q)$ has finite index.

preprint2018arXiv

Bisimilarity Distances for Approximate Differential Privacy

Differential privacy is a widely studied notion of privacy for various models of computation. Technically, it is based on measuring differences between probability distributions. We study $ε,δ$ -differential privacy in the setting of labelled Markov chains. While the exact differences relevant to $ε,δ$ -differential privacy are not computable in this framework, we propose a computable bisimilarity distance that yields a sound technique for measuring $δ$ , the parameter that quantifies deviation from pure differential privacy. We show this bisimilarity distance is always rational, the associated threshold problem is in NP, and the distance can be computed exactly with polynomially many calls to an NP oracle.

preprint2016arXiv

Complexity of regular abstractions of one-counter languages

We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L(A): its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown if appropriate NFA of sub-exponential size exist.

preprint2016arXiv

Context-Free Commutative Grammars with Integer Counters and Resets

We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on them. Those grammars can alternatively be viewed as an extension of communication-free Petri nets. Our main results are that reachability and coverability are inter-reducible and both NP-complete. In particular, this class of commutative grammars enjoys semi-linear reachability sets. We also show that the inclusion problem is, in general, coNEXP-complete and already $Π_2^\text{P}$ -complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel $Π_2^\text{P}$ -complete variant of the classic subset sum problem.

preprint2016arXiv

Fractional coverings, greedy coverings, and rectifier networks

A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix $M$ that has a $1$ in the entry $(i,j)$ iff there is a path from the $j$ th source to the $i$ th sink. The smallest number of edges in a rectifier network computing $M$ is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two well-known techniques that have hitherto found little to no applications in this theory. Both of them build on a basic fact that depth- $2$ rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. We obtain new results by using fractional and greedy coverings (defined in the standard way). First, we show that all fractional coverings of the so-called full triangular matrix have cost at least $n\log n$ . This provides (a fortiori) a new proof of the tight lower bound on its depth- $2$ complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth- $2$ complexity of the Kneser-Sierpiński (disjointness) matrix. The previous upper bound is $O(n^{1.28})$ , and we improve it to $O(n^{1.17})$ , while the best known lower bound is $Ω(n^{1.16})$ . Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).

preprint2016arXiv

Hitting Families of Schedules for Asynchronous Programs

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 and specifies ordering constraints between them. The task is to determine if some scheduling of these events can result in a bug. The number of schedules to be explored can, in general, be exponential. Empirically, many bugs in concurrent programs have been observed to have small bug depth; that is, these bugs are exposed by every schedule that orders $d$ specific events in a particular way, irrespective of how the other events are ordered, and $d$ is small compared to the total number of events. To find all bugs of depth $d$ , one needs to only test a $d$ -hitting family of schedules: we call a set of schedules a $d$ -hitting family if for each set of $d$ events, and for each allowed ordering of these events, there is some schedule in the family that executes these events in this ordering. The size of a $d$ -hitting family may be much smaller than the number of all possible schedules, and a natural question is whether one can find $d$ -hitting families of schedules that have small size. In general, finding the size of optimal $d$ -hitting families is hard, even for $d=2$ . We show, however, that when the partial order is a tree, one can explicitly construct $d$ -hitting families of schedules of small size. When the tree is balanced, our constructions are polylogarithmic in the number of events.

preprint2016arXiv

On Restricted Nonnegative Matrix Factorization

Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$ . Restricted NMF requires in addition that the column spaces of $M$ and $W$ coincide. Finding the minimal inner dimension $d$ is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974. Furthermore, we investigate whether a rational matrix $M$ always has a restricted NMF of minimal inner dimension whose factors $W$ and $H$ are also rational. We show that this holds for matrices $M$ of rank at most $3$ and we exhibit a rank- $4$ matrix for which $W$ and $H$ require irrational entries.

preprint2015arXiv

Approximate Counting in SMT and Value Estimation for Probabilistic Programs

#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 computing the volume of a polytope. In the realm of satisfiability modulo theories (SMT) there is a growing need for model counting solvers, coming from several application domains (quantitative information flow, static analysis of probabilistic programs). In this paper, we show a reduction from an approximate version of #SMT to SMT. We focus on the theories of integer arithmetic and linear real arithmetic. We propose model counting algorithms that provide approximate solutions with formal bounds on the approximation error. They run in polynomial time and make a polynomial number of queries to the SMT solver for the underlying theory, exploiting "for free" the sophisticated heuristics implemented within modern SMT solvers. We have implemented the algorithms and used them to solve the value problem for a model of loop-free probabilistic programs with nondeterminism.

preprint2014arXiv

Unary Pushdown Automata and Straight-Line Programs

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 regular languages, but can be exponentially more succinct than finite-state automata. We complete the complexity landscape for udpda by showing that emptiness (and thus universality) is P-hard, equivalence and compressed membership problems are P-complete, and inclusion is coNP-complete. Our upper bounds are based on a translation theorem between udpda and straight-line programs over the binary alphabet (SLPs). We show that the characteristic sequence of any udpda can be represented as a pair of SLPs---one for the prefix, one for the lasso---that have size linear in the size of the udpda and can be computed in polynomial time. Hence, decision problems on udpda are reduced to decision problems on SLPs. Conversely, any SLP can be converted in logarithmic space into a udpda, and this forms the basis for our lower bound proofs. We show coNP-hardness of the ordered matching problem for SLPs, from which we derive coNP-hardness for inclusion. In addition, we complete the complexity landscape for unary nondeterministic pushdown automata by showing that the universality problem is $Π_2 \mathrm P$ -hard, using a new class of integer expressions. Our techniques have applications beyond udpda. We show that our results imply $Π_2 \mathrm P$ -completeness for a natural fragment of Presburger arithmetic and coNP lower bounds for compressed matching problems with one-character wildcards.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Dmitry Chistikov

Research overview

Is this your work?

14 publications

Presburger arithmetic with threshold counting quantifiers is easy

Subcubic Certificates for CFL Reachability

Convergence of Opinion Diffusion is PSPACE-complete

Globe-hopping

O-Minimal Invariants for Discrete-Time Dynamical Systems

Rational subsets of Baumslag-Solitar groups

Bisimilarity Distances for Approximate Differential Privacy

Complexity of regular abstractions of one-counter languages

Context-Free Commutative Grammars with Integer Counters and Resets

Fractional coverings, greedy coverings, and rectifier networks

Hitting Families of Schedules for Asynchronous Programs

On Restricted Nonnegative Matrix Factorization

Approximate Counting in SMT and Value Estimation for Probabilistic Programs

Unary Pushdown Automata and Straight-Line Programs

See the researcher in context

Building this map preview