UPDATE (February 2017):
I will begin as an assistant professor
at the University of Warwick, UK,
in April 2017.
I am looking for highly motivated students and postdocs!
The general area of my research is theoretical computer science.
In particular, I am interested in theoretical foundations of verification:
its algorithmic aspects (decision and counting problems)
as well as combinatorial aspects (extremal properties
and characteristics of mathematical models of computation).
Publications
2017
D. Chistikov, S. Iván, A. Lubiw, J. Shallit.
Fractional coverings, greedy coverings,
and rectifier networks.
In: STACS'17 (to appear).
arXiv:1509.07588 [cs.CC]
D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell.
On rationality of nonnegative matrix factorization.
In: SODA'17 (to appear).
Extended version
available as
arXiv:1605.06848 [cs.CC]
2016
D. Chistikov, S. Kiefer, I. Marušić, M. Shirmohammadi, J. Worrell.
On restricted nonnegative matrix factorization.
In: ICALP'16 (to appear)
arXiv:1605.07061 [cs.FL]
D. Chistikov, C. Haase.
The taming of the semi-linear set.
In: ICALP'16 (to appear)
(pdf)
D. Chistikov, R. Majumdar, F. Niksic.
Hitting families of schedules for asynchronous programs.
In: CAV'16 (to appear)
arXiv:1602.03755 [cs.DM]
M. F. Atig, D. Chistikov, P. Hofman, K. Narayan Kumar, P. Saivasan, G. Zetzsche.
The complexity of regular abstractions of one-counter languages.
In: LICS'16 (to appear)
arXiv:1602.03419 [cs.FL]
D. Chistikov, W. Czerwiński, P. Hofman, Mi. Pilipczuk, M. Wehar.
Shortest paths in one-counter systems.
In: FoSSaCS'16.
LNCS, vol. 9634, pp. 462–478 (2016)
arXiv:1510.05460 [cs.FL]
D. Chistikov, P. Martyugin, M. Shirmohammadi.
Synchronizing automata over nested words.
In: FoSSaCS'16.
LNCS, vol. 9634, pp. 252–268 (2016)
(pdf)
2015
D. Chistikov, C. Haase, S. Halfon.
Context-free commutative grammars with integer counters and resets.
Accepted to Theoretical Computer Science, special issue for RP'14.
arXiv:1511.04893 [cs.FL]
D. Chistikov, R. Dimitrova, R. Majumdar.
Approximate counting in SMT
and value estimation for probabilistic programs.
In: TACAS'15.
LNCS, vol. 9035, pp. 320–334 (2015)
arXiv:1411.0659 [cs.LO]
2014
D. Chistikov.
Notes on counting with finite machines.
In: FSTTCS'14. LIPIcs, vol. 29, pp. 339–350 (2014)
(proceedings version:
pdf)
D. Chistikov, R. Majumdar.
Unary pushdown automata and straight-line programs.
In: ICALP'14. Part II.
LNCS, vol. 8573, pp. 146–157 (2014)
arXiv:1403.0509 [cs.FL]
D. Chistikov, V. Fedorova, A. Voronenko.
Certificates of non-membership
for classes of read-once functions.
Fundamenta Informaticae 132(1), 63–77 (2014)
(pdf)
2013
D. Chistikov, R. Majumdar.
A uniformization theorem
for nested word to word transductions.
In: CIAA 2013.
LNCS, vol. 7982, pp. 97–108
(2013)
(pdf)
D. V. Chistikov.
Using relevance queries for identification
of read-once functions.
Journal of Mathematical Sciences 192(3), 359–374
(2013)
(pdf)
(translated from Russian version published in
Zapiski Nauchnykh Seminarov POMI 402, 183–217
(2012))
2012
D. V. Chistikov.
Checking tests for read-once functions
over arbitrary bases.
In: CSR 2012.
LNCS, vol. 7353, pp. 52–63
(2012)
(pdf)
O. V. Zubkov, D. V. Chistikov, A. A. Voronenko.
An upper bound on checking test complexity
for almost all cographs.
In: SYNASC 2011,
pp. 323–330
(2012)
(pdf)
2011
D. V. Chistikov.
Test complexity of read-once functions.
Candidate of physical and mathematical sciences (equiv. to PhD) thesis.
Moscow State University (2011) (in Russian)
D. V. Chistikov.
Testing monotone read-once functions.
In: IWOCA 2011.
LNCS, vol. 7056, pp. 121–134
(2011)
(pdf)
A. A. Voronenko, D. V. Chistikov.
Learning read-once functions using subcube parity queries.
Computational Mathematics and Modeling 22(1), 81–91
(2011)
D. V. Chistikov.
Testing read-once functions over the elementary basis.
Moscow University Computational Mathematics and Cybernetics 35(4), 189–192
(2011)
(pdf)
A. A. Voronenko, V. S. Fedorova, D. V. Chistikov.
Iterated Boolean functions in the elementary basis.
Russian Mathematics (Iz. VUZ) 55(11), 61–65
(2011)
D. V. Chistikov.
On the relationship between diagnostic and checking tests
of the read-once functions.
Discrete Mathematics and Applications 21(2), 203–208
(2011)
2010
D. V. Chistikov.
Read-once functions with hard-to-test projections.
Moscow University Computational Mathematics and Cybernetics 34(4), 188–190
(2010)
S. E. Bubnov, A. A. Voronenko, D. V. Chistikov.
Some test length bounds for nonrepeating functions
in the
basis.
Computational Mathematics and Modeling 21(2), 196–205
(2010)
2009
A. A. Voronenko, D. V. Chistikov.
Learning read-once functions individually.
Uchenye Zapiski Kazanskogo Universiteta,
ser. Fiziko-Matematicheskie Nauki 151(2), 36–44
(2009)
(in Russian)
As a general rule, versions of papers kept on this website are preprints,
so you will not find publishers' formatting and fixes here.
Teaching
Model counting for logical theories.
ESSLLI'16, Bolzano, Italy,
15–19 August 2016.
Co-taught with Rayna Dimitrova and
sponsored by EACSL.
(course page)
