6 Search Results for "Vereshchagin, Nikolay"

Document
DOI: 10.4230/LIPIcs.STACS.2026.8
On the p-adic Skolem Problem

Authors: Piotr Bacik, Joël Ouaknine, David Purser, and James Worrell

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The Skolem Problem asks to determine whether a given linear recurrence sequence (LRS) has a zero term. Showing decidability of this problem is equivalent to giving an effective proof of the Skolem-Mahler-Lech Theorem, which asserts that a non-degenerate LRS has finitely many zeros. The latter result was proven over 90 years ago via an ineffective method showing that such an LRS has only finitely many p-adic zeros. In this paper we consider the problem of determining whether a given LRS has a p-adic zero, as well as the corresponding function problem of computing exact representations of all p-adic zeros. We present algorithms for both problems and report on their implementation. The output of the algorithms is unconditionally correct, and termination is guaranteed subject to the p-adic Schanuel Conjecture (a standard number-theoretic hypothesis concerning the p-adic exponential function). While these algorithms do not solve the Skolem Problem, they can be exploited to find natural-number and rational zeros under additional hypotheses. To illustrate this, we apply our results to show decidability of the Simultaneous Skolem Problem (determine whether two coprime linear recurrences have a common natural-number zero), again subject to the p-adic Schanuel Conjecture.
Cite as

Piotr Bacik, Joël Ouaknine, David Purser, and James Worrell. On the p-adic Skolem Problem. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bacik_et_al:LIPIcs.STACS.2026.8,
  author =	{Bacik, Piotr and Ouaknine, Jo\"{e}l and Purser, David and Worrell, James},
  title =	{{On the p-adic Skolem Problem}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.8},
  URN =		{urn:nbn:de:0030-drops-254979},
  doi =		{10.4230/LIPIcs.STACS.2026.8},
  annote =	{Keywords: Skolem Problem, p-adic Schanuel Conjecture, Skolem Conjecture, Exponential Local-Global Principle, exponential polynomial}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.84
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

Authors: Andrei Romashchenko

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings (a, b, c), there exists a string z such that each conditional Kolmogorov complexity C(a|z), C(b|z), C(c|z) is approximately half of the corresponding unconditional Kolmogorov complexity. We provide a negative answer to this question by constructing a triple (a, b, c) for which no such string z exists. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on recent bounds for point-line incidences over prime fields, obtained using tools from additive combinatorics and algebraic methods, notably results by Bourgain-Katz-Tao and Stevens-De Zeeuw. As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields.
Cite as

Andrei Romashchenko. Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{romashchenko:LIPIcs.MFCS.2025.84,
  author =	{Romashchenko, Andrei},
  title =	{{Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{84:1--84:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-241914},
  doi =		{10.4230/LIPIcs.MFCS.2025.84},
  annote =	{Keywords: Kolmogorov complexity, algorithmic information theory, communication complexity, discrete geometry}
}
Document
DOI: 10.4230/OASIcs.Manzini.2
A Survey of the Bijective Burrows-Wheeler Transform

Authors: Hideo Bannai, Dominik Köppl, and Zsuzsanna Lipták

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
The Bijective BWT (BBWT), conceived by Scott in 2007, later summarized in a preprint by Gil and Scott in 2009 (arXiv 2012), is a variant of the Burrows-Wheeler Transform which is bijective: every string is the BBWT of some string. Indeed, the BBWT of a string is the extended BWT [Mantaci et al., 2007] of the factors of its Lyndon factorization. The BBWT has been receiving increasing interest in recent years. In this paper, we survey existing research on the BBWT, starting with its history and motivation. We then present algorithmic topics including construction algorithms with various complexities and an index on top of the BBWT for pattern matching. We subsequently address some properties of the BBWT as a compressor, discussing robustness to operations such as reversal, edits, rotation, as well as compression power. We close with listing other bijective variants of the BWT and open problems concerning the BBWT.
Cite as

Hideo Bannai, Dominik Köppl, and Zsuzsanna Lipták. A Survey of the Bijective Burrows-Wheeler Transform. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 2:1-2:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bannai_et_al:OASIcs.Manzini.2,
  author =	{Bannai, Hideo and K\"{o}ppl, Dominik and Lipt\'{a}k, Zsuzsanna},
  title =	{{A Survey of the Bijective Burrows-Wheeler Transform}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{2:1--2:26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.2},
  URN =		{urn:nbn:de:0030-drops-239100},
  doi =		{10.4230/OASIcs.Manzini.2},
  annote =	{Keywords: Burrows-Wheeler Transform, compression, text indexing, repetitiveness measure, Lyndon words, index construction algorithms, bijective string transformation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.42
Nearest Neighbor Complexity and Boolean Circuits

Authors: Mason DiCicco, Vladimir Podolskii, and Daniel Reichman

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A nearest neighbor representation of a Boolean function f is a set of vectors (anchors) labeled by 0 or 1 such that f(x) = 1 if and only if the closest anchor to x is labeled by 1. This model was introduced by Hajnal, Liu and Turán [2022], who studied bounds on the minimum number of anchors required to represent Boolean functions under different choices of anchors (real vs. Boolean vectors) as well as the analogous model of k-nearest neighbors representations. We initiate a systematic study of the representational power of nearest and k-nearest neighbors through Boolean circuit complexity. To this end, we establish a close connection between Boolean functions with polynomial nearest neighbor complexity and those that can be efficiently represented by classes based on linear inequalities - min-plus polynomial threshold functions - previously studied in relation to threshold circuits. This extends an observation of Hajnal et al. [2022]. Next, we further extend the connection between nearest neighbor representations and circuits to the k-nearest neighbors case. As an outcome of these connections we obtain exponential lower bounds on the k-nearest neighbors complexity of explicit n-variate functions, assuming k ≤ n^{1-ε}. Previously, no superlinear lower bound was known for any k > 1. At the same time, we show that proving superpolynomial lower bounds for the k-nearest neighbors complexity of an explicit function for arbitrary k would require a breakthrough in circuit complexity. In addition, we prove an exponential separation between the nearest neighbor and k-nearest neighbors complexity (for unrestricted k) of an explicit function. These results address questions raised by [Hajnal et al., 2022] of proving strong lower bounds for k-nearest neighbors and understanding the role of the parameter k. Finally, we devise new bounds on the nearest neighbor complexity for several families of Boolean functions.
Cite as

Mason DiCicco, Vladimir Podolskii, and Daniel Reichman. Nearest Neighbor Complexity and Boolean Circuits. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dicicco_et_al:LIPIcs.ITCS.2025.42,
  author =	{DiCicco, Mason and Podolskii, Vladimir and Reichman, Daniel},
  title =	{{Nearest Neighbor Complexity and Boolean Circuits}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.42},
  URN =		{urn:nbn:de:0030-drops-226704},
  doi =		{10.4230/LIPIcs.ITCS.2025.42},
  annote =	{Keywords: Complexity, Nearest Neighbors, Circuits}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.17
Stochasticity in Algorithmic Statistics for Polynomial Time

Authors: Alexey Milovanov and Nikolay Vereshchagin

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called acceptability, plausibility and optimality. Roughly speaking, a probability distribution m is called an acceptable explanation for x, if x possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to m). Plausibility is a similar notion, however this time we require x to possess all properties T decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all' - the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution m is called an optimal explanation for x if m(x) is large. Almost all our results hold under some plausible complexity theoretic assumptions. Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, i.e. objects that do not have simple plausible (acceptable) explanations. Using the same techniques, we show that the distinguishing complexity of a string x can be super-logarithmically less than the conditional complexity of x with condition r for almost all r (for polynomial time bounded programs). Finally, we study relationships between the introduced notions.
Cite as

Alexey Milovanov and Nikolay Vereshchagin. Stochasticity in Algorithmic Statistics for Polynomial Time. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{milovanov_et_al:LIPIcs.CCC.2017.17,
  author =	{Milovanov, Alexey and Vereshchagin, Nikolay},
  title =	{{Stochasticity in Algorithmic Statistics for Polynomial Time}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.17},
  URN =		{urn:nbn:de:0030-drops-75222},
  doi =		{10.4230/LIPIcs.CCC.2017.17},
  annote =	{Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1335
Limit complexities revisited

Authors: Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional (plain) Kolmogorov complexity of $x$ when $n$ is known) equals $KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with $mathbf{0'$-oracle. Then we use the same argument to prove similar results for prefix complexity (and also improve results of (Muchnik, 1987) about limit frequencies), a priori probability on binary tree and measure of effectively open sets. As a by-product, we get a criterion of $mathbf{0'$ Martin-L"of randomness (called also $2$-randomness) proved in (Miller, 2004): a sequence $omega$ is $2$-random if and only if there exists $c$ such that any prefix $x$ of $omega$ is a prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the 1960ies this property was suggested in (Kolmogorov, 1968) as one of possible randomness definitions; its equivalence to $2$-randomness was shown in (Miller, 2004) while proving another $2$-randomness criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many prefixes $x$ of $omega$. Finally, we show that the low-basis theorem can be used to get alternative proofs for these results and to improve the result about effectively open sets; this stronger version implies the $2$-randomness criterion mentioned in the previous sentence.
Cite as

Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2008.1335,
  author =	{Bienvenu, Laurent and Muchnik, Andrej and Shen, Alexander and Veraschagin, Nikolay},
  title =	{{Limit complexities revisited}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{73--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1335},
  URN =		{urn:nbn:de:0030-drops-13350},
  doi =		{10.4230/LIPIcs.STACS.2008.1335},
  annote =	{Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis}
}
  • Refine by Type
  • 6 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2017
  • 1 2008

  • Refine by Author
  • 1 Bacik, Piotr
  • 1 Bannai, Hideo
  • 1 Bienvenu, Laurent
  • 1 DiCicco, Mason
  • 1 Köppl, Dominik
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Mathematics of computing → Information theory
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Communication complexity
  • Show More...

  • Refine by Keyword
  • 3 Kolmogorov complexity
  • 1 2-randomness
  • 1 Algorithmic Statistics
  • 1 Burrows-Wheeler Transform
  • 1 Circuits
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact