3 Search Results for "Andreev, Alexander E."

Document
DOI: 10.4230/LIPIcs.MFCS.2018.2
Plain Stopping Time and Conditional Complexities Revisited

Authors: Mikhail Andreev, Gleb Posobin, and Alexander Shen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)<n; (e) as maxC^X(x) where C^X(z) is plain Kolmogorov complexity of z relative to oracle X and the maximum is taken over all extensions X of x. We also show that some of these equivalent definitions become non-equivalent in the more general setting where the condition y and the object x may differ, and answer an open question from Chernov, Hutter and Schmidhuber [Alexey V. Chernov et al., 2007].
Cite as

Mikhail Andreev, Gleb Posobin, and Alexander Shen. Plain Stopping Time and Conditional Complexities Revisited. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 2:1-2:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:LIPIcs.MFCS.2018.2,
  author =	{Andreev, Mikhail and Posobin, Gleb and Shen, Alexander},
  title =	{{Plain Stopping Time and Conditional Complexities Revisited}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.2},
  URN =		{urn:nbn:de:0030-drops-95842},
  doi =		{10.4230/LIPIcs.MFCS.2018.2},
  annote =	{Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory}
}
Document
DOI: 10.4230/DagSemProc.06111.22
Very Large Cliques are Easy to Detect

Authors: Alexander E. Andreev and Stasys Jukna

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
It is known that, for every constant $kgeq 3$, the presence of a $k$-clique (a complete subgraph on $k$ vertices) in an $n$-vertex graph cannot be detected by a monotone boolean circuit using fewer than $Omega((n/log n)^k)$ gates. We show that, for every constant $k$, the presence of an $(n-k)$-clique in an $n$-vertex graph can be detected by a monotone circuit using only $O(n^2log n)$ gates. Moreover, if we allow unbounded fanin, then $O(log n)$ gates are enough.
Cite as

Alexander E. Andreev and Stasys Jukna. Very Large Cliques are Easy to Detect. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:DagSemProc.06111.22,
  author =	{Andreev, Alexander E. and Jukna, Stasys},
  title =	{{Very Large Cliques are Easy to Detect}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.22},
  URN =		{urn:nbn:de:0030-drops-6092},
  doi =		{10.4230/DagSemProc.06111.22},
  annote =	{Keywords: Clique function, monotone circuits, perfect hashing}
}
Document
DOI: 10.4230/DagSemProc.06111.19
The optimal sequence compression

Authors: Alexander E. Andreev

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
This paper presents the optimal compression for sequences with undefined values. Let we have $(N-m)$ undefined and $m$ defined positions in the boolean sequence $vv V$ of length $N$. The sequence code length can't be less then $m$ in general case, otherwise at least two sequences will have the same code. We present the coding algorithm which generates codes of almost $m$ length, i.e. almost equal to the lower bound. The paper presents the decoding circuit too. The circuit has low complexity which depends from the inverse density of defined values $D(vv V) = frac{N}{m}$. The decoding circuit includes RAM and random logic. It performs sequential decoding. The total RAM size is proportional to the $$logleft(D(vv V) ight) ,$$ the number of random logic cells is proportional to $$log logleft(D(vv V) ight) * left(log log logleft(D(vv V) ight) ight)^2 .$$ So the decoding circuit will be small enough even for the very low density sequences. The decoder complexity doesn't depend of the sequence length at all.
Cite as

Alexander E. Andreev. The optimal sequence compression. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{andreev:DagSemProc.06111.19,
  author =	{Andreev, Alexander E.},
  title =	{{The optimal sequence compression}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.19},
  URN =		{urn:nbn:de:0030-drops-6025},
  doi =		{10.4230/DagSemProc.06111.19},
  annote =	{Keywords: Compression, partial boolean function}
}
  • Refine by Author
  • 2 Andreev, Alexander E.
  • 1 Andreev, Mikhail
  • 1 Jukna, Stasys
  • 1 Posobin, Gleb
  • 1 Shen, Alexander

  • Refine by Classification
  • 1 Mathematics of computing → Information theory

  • Refine by Keyword
  • 1 Clique function
  • 1 Compression
  • 1 Kolmogorov complexity
  • 1 algorithmic information theory
  • 1 monotone circuits
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2006
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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