• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдена 21 публикация
Сортировка:
по названию
по году
Статья
Babenko M. A. Theory of Computing Systems. 2010. No. 46(1). P. 59-79.
Let G be an undirected graph and be a collection of disjoint subsets of nodes. Nodes in T 1∪⋅⋅⋅∪T k are called terminals, other nodes are called inner. By a TeX -path we mean a path P such that P connects terminals from distinct sets in TeX and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of TeX -paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn 2), where n and m denote the numbers of nodes and edges in G, respectively.
Добавлено: 17 декабря 2010
Статья
Vereshchagin N. Theory of Computing Systems. 2016. Vol. 58. No. 3. P. 463-481.
Добавлено: 7 февраля 2017
Статья
Bauwens B. F., Shen A. Theory of Computing Systems. 2013. Vol. 52. No. 2. P. 297-302.
Добавлено: 2 октября 2015
Статья
Babenko M. A., Kolesnichenko I., Smirnov I. Theory of Computing Systems. 2019. Vol. 63. No. 4. P. 637-646.

Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as this would violate the Ω (nlog n) bound for comparison-based sorting. It is known, however, that is takes only O(n+ klog k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose extract-min performance depends on the number of elements extracted so far. In this paper we show that this is indeed the case. We present a version of heap that performs insert in O(1) time and takes only O(log ∗ n+ log k) time to carry out the k-th extraction (where log ∗ denotes the iterated logarithm). All the above bounds are worst-case. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Добавлено: 6 декабря 2019
Статья
Podolskii V. V., Kulikov A. S. Theory of Computing Systems. 2019. Vol. 63. No. 5. P. 956-986.
Добавлено: 9 ноября 2019
Статья
Bauwens B. F. Theory of Computing Systems. 2017. Vol. 60. No. 2. P. 314-323.

Van Lambalgen’s theorem states that a pair (αβ) of bit sequences is Martin-Löf random if and only ifα is Martin-Löf random and β is Martin-Löf random relative to α. In [Information and Computation 209.2 (2011): 183-197, Theorem 3.3], Hayato Takahashi generalized van Lambalgen’s theorem for computable measures P on a product of two Cantor spaces; he showed that the equivalence holds for each β for which the conditional probability P(⋅|β) is computable. He asked whether this computability condition is necessary. We give a positive answer by providing a computable measure for which van Lambalgen’s theorem fails. We also present a simple construction of a computable measure for which conditional measure is not computable. Such measures were first constructed by Ackerman et al. ([1]).

Добавлено: 2 июня 2016
Статья
Bauwens B. F., Shen A., Takahashi H. Theory of Computing Systems. 2017. Vol. 61. No. 4. P. 1315-1336.
Добавлено: 1 ноября 2017
Статья
Vyalyi M., Cheng Q., Tarasov S. Theory of Computing Systems. 2010. Vol. 46. P. 120-142.
Добавлено: 17 октября 2014
Статья
Vereshchagin N. Theory of Computing Systems. 2014. Vol. 54. No. 2. P. 305-317.
Добавлено: 19 октября 2016
Статья
Vereshchagin N. Theory of Computing Systems. 2013.

When we represent a decision problem, like CIRCUIT-SAT, as a language over the binary alphabet, we usually do not specify how  to encode instances by binary strings. This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$'' does not depend on the encoding, provided both the encoding and the class $C$ are ``natural''. In this sense most of the Complexity theory  is ``encoding invariant''. The notion of a polynomial time computable distribution from Average Case Complexity is one of the exceptions from this rule. It might happen that a distribution over some objects, like circuits, is polynomial time computable in one encoding and is not polynomial time computable in the other encoding.In this paper we suggest an encoding invariant generalization of a notion of a polynomial time computable distribution. The completeness proofs of known distributional problems, like Bounded Halting are simpler for the new class than for  polynomial time computable distributions. This paper has no new technical contributions. All the statements are proved using the known techniques.

Добавлено: 1 февраля 2014
Статья
Bauwens B. F., Terwijn S. Theory of Computing Systems. 2011. Vol. 48. P. 247-268.
Добавлено: 2 октября 2015
Статья
Milovanov A. Theory of Computing Systems. 2019. Vol. 63. No. 4. P. 833-848.
Добавлено: 17 октября 2018
Статья
V'yugin V. Theory of Computing Systems. 2012. Vol. 50. No. 2. P. 296-312.
Добавлено: 30 января 2013
Статья
Kogan K., Lopez-Ortiz A., Nikolenko S. I. et al. Theory of Computing Systems. 2016. Vol. 58. No. 2. P. 322-344.
Добавлено: 9 октября 2014
Статья
Kozachinskiy A. Theory of Computing Systems. 2018. Vol. 62. No. 3. P. 583-599.

In this paper we study interactive “one-shot” analogues of the classical Slepian–Wolf theorem. Alice receives a value of a random variable X, Bob receives a value of another random variable Y that is jointly distributed with X. Alice’s goal is to transmit X to Bob (with some error probability ε). Instead of one-way transmission we allow them to interact. They may also use shared randomness. We show, that for every natural r Alice can transmit X to Bob using (1+1r)H(X|Y)+r+O(log2(1ε))(1+1r)H(X|Y)+r+O(log2⁡(1ε)) bits on average in 2H(X|Y)r+22H(X|Y)r+2 rounds on average. Setting r=⌈H(X|Y)−−−−−−−√⌉r=⌈H(X|Y)⌉ and using a result of Braverman and Garg (2) we conclude that every one-round protocol π with information complexity I can be compressed to a (many-round) protocol with expected communication about I+2I–√I+2I bits. This improves a result by Braverman and Rao (3), where they had I+5I–√I+5I. Further, we show (by setting r = ⌈H(X|Y)⌉) how to solve this problem (transmitting X) using 2H(X|Y)+O(log2(1ε))2H(X|Y)+O(log2⁡(1ε)) bits and 4 rounds on average. This improves a result of Brody et al. (4), where they had 4H(X|Y)+O(log1/ε)4H(X|Y)+O(log⁡1/ε) bits and 10 rounds on average. In the end of the paper we discuss how many bits Alice and Bob may need to communicate on average besides H(X|Y). The main question is whether the upper bounds mentioned above are tight. We provide an example of (X, Y), such that transmission of X from Alice to Bob with error probability ε requires H(X|Y)+Ω(log2(1ε))H(X|Y)+Ω(log2⁡(1ε)) bits on average.

 

 

Добавлено: 9 февраля 2017
Статья
V'yugin V. Theory of Computing Systems. 2016. P. 403-423.
Добавлено: 16 мая 2015
Статья
Kozachinskiy A. Theory of Computing Systems. 2019.
Добавлено: 11 апреля 2019
Статья
Bauwens B. F. Theory of Computing Systems. 2015. Vol. 58. No. 3. P. 482-501.
Добавлено: 2 октября 2015
Статья
Vereshchagin N. Theory of Computing Systems. 2017. Vol. 61. No. 4. P. 1440-1450.
Добавлено: 6 декабря 2017
Статья
Milovanov A. Theory of Computing Systems. 2017. Vol. 61. No. 2. P. 521-535.

Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms of Kolmogorov complexity. It is known that this cannot be achieved for some objects: there are some ``non-stochastic'' objects that do not have good explanations. In this paper we study the properties of maximally non-stochastic objects; we call them ``antistochastic''. In this paper, we demonstrate that the antistochastic strings have the following property: if an antistochastic string x has complexity k, then any k bit of information about x are enough to reconstruct x (with logarithmic advice). In particular, if we erase all but k bits of this antistochastic string, the erased bits can be restored from the remaining ones (with logarithmic advice). As a corollary we get the existence of good list-decoding codes with erasures (or other ways of deleting part of the information). Antistochastic strings can also be used as a source of counterexamples in algorithmic information theory. We show that the symmetry of information property fails for total conditional complexity for antistochastic strings.  

Добавлено: 27 июня 2016
Статья
Antunes L., Bauwens B. F., Souto A. et al. Theory of Computing Systems. 2017. Vol. 60. No. 2. P. 280-298.

Sophistication and logical depth are two measures that express how complicated the structure in a string is. Sophistication is defined as the minimal complexity of a computable function that defines a two-part description for the string that is shortest within some precision; the second can be defined as the minimal computation time of a program that is shortest within some precision. We show that the Busy Beaver function of the sophistication of a string exceeds its logical depth with logarithmically bigger precision, and that logical depth exceeds the Busy Beaver function of sophistication with logarithmically bigger precision. We also show that sophistication is unstable in its precision: constant variations can change its value by a linear term in the length of the string.

Добавлено: 4 мая 2016