### ?

## Short lists with short programs in short time

Computational Complexity. 2018. Vol. 27. No. 1. P. 31-61.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a $O(\log |x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.

Publication based on the results of:

Bauwens B., Makhlin A., Vereshchagin N. et al., / Hasso-Plattner-Institut. Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-007.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of ...

Added: December 14, 2013

Shen A., Uspensky V. A., Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017

Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531-537

The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as ...

Added: January 17, 2020

Vereshchagin N., Milovanov A., / Weizmann Institute of Science. Series Technical report "Electronic Colloquium on Computational Complexity". 2017. No. TR17-043.

Added: March 7, 2017

Vereshchagin N., Theoretical Computer Science 2023 Vol. 940 P. 108-122

We consider the network consisting of three nodes 1, 2, 3 connected by two open channels
1 → 2 and 1 → 3. The information present in the node 1 consists of four strings x , y , z , w.
The nodes 2, 3 know x , w and need to know y , z, respectively. ...

Added: December 19, 2022

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 ...

Added: June 27, 2016

Bauwens B. F., Gács P., Romashchenko A. et al., Computability 2022 Vol. 11 No. 3-4 P. 165-185

Finding all linear inequalities for entropies remains an important open question in information theory. For a long time the only known inequalities for entropies of tuples of random variables were Shannon (submodularity) inequalities. Only in 1998 Zhang and Yeung 1998 found the first inequality that cannot be represented as a convex combination of Shannon inequalities, and ...

Added: December 23, 2022

Bienvenu L., Muchnik A., Shen A. et al., / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that lim supnC(x|n) equals C0′(x). Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary ...

Added: December 14, 2013

Vereshchagin N., / Hasso-Plattner-Institut. Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178.

The paper [Harry Buhrman, Michal Kouck\'y, Nikolay Vereshchagin. Randomized Individual Communication Complexity. \emph{IEEE Conference on Computational Complexity} 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate Kolmogorov complexity $C(x|y)$ of $x$ conditional ...

Added: December 14, 2013

Milovanov A., Theory of Computing Systems 2019 Vol. 63 No. 4 P. 833-848

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we ...

Added: October 17, 2018

Bauwens B. F., Zimand M., Journal of the ACM 2023 Vol. 70 No. 2 Article 9

In a lossless compression system with target lengths, a compressor 𝒞 maps an integer m and a binary string x to an m-bit code p, and if m is sufficiently large, a decompressor 𝒟 reconstructs x from p. We call a pair (m,x) achievable for (𝒞,𝒟) if this reconstruction is successful. We introduce the notion ...

Added: March 22, 2023

Beklemishev L. D., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20

We formulate some term rewriting systems in which the number of computation steps is finite for each output, but this number cannot be bounded by a provably total computable function in Peano arithmetic PA. Thus, the termination of such systems is unprovable in PA. These systems are derived from an independent combinatorial result known as the Worm ...

Added: March 13, 2016

Borchmann D., Hanika T., Obiedkov S., Discrete Applied Mathematics 2020 Vol. 273 P. 30-42

We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size ...

Added: October 29, 2019

Ружицкая Д. Д., САМОЙЛЕНКО А. А., Иванов А. Д. et al., Optoelectronics, Instrumentation and Data Processing 2017 Vol. 54 No. 1 P. 1-8

This paper presents an algorithm for processing the transmission spectra of whisperinggallery optical microcavities for use as a nanoparticle detector. The algorithm is based on the broadening of the microcavity resonance curve during precipitation of nanoparticles on the microcavity surface. Experimental results on the detection of particles are compared with Langmuir adsorption theory. The contribution ...

Added: May 25, 2018

Gostev I. M., М. : Юрайт, 2016

В настоящее время компьютерные науки стремительно развиваются. Новые версии операционных систем появляются каждые полтора-два года, поэтому было принято решение о включении в данную книгу такого материала, который не будет устаревать. Содержание учебника представляет собой некоторые наиболее общие принципы построения операционных систем, которые были разработаны более 50 лет назад и практически не изменились за прошедшее время. ...

Added: October 13, 2009

Litvin Y. V., Абрамов И. В., Технологии техносферной безопасности 2016 № 66

Advanced approach to the assessment of a random time of arrival fire fighting calculation on the object of protection, the time of their employment and the free combustion. There is some quantitative assessments with the review of analytical methods and simulation ...

Added: August 27, 2016

Aaij R., Abdelmotteleb A. S., Abellan Beteta C. et al., The European Physical Journal C - Particles and Fields 2023 Vol. 83 Article 543

https://link.springer.com/article/10.1140/epjc/s10052-023-11673-x#Abs1 ...

Added: December 4, 2023

Springer, 2012

Added: January 29, 2013

Karpov V. E., Karpova I. P., Procedia Engineering 2015 Vol. 100 P. 1459-1468

Work solutions are proposed for problems of leader definition and role distribution in homogeneous groups of robots. It is shown that transition from a swarm to a collective of robots with hierarchical organization is possible using exclusively local interaction. The local revoting algorithm is central to the procedure for choice of leader while redistribution of roles can ...

Added: March 14, 2015

Kiselyova N. N., Dudarev V.A., Korzhuev M. A., Inorganic Materials: Applied Research 2016 Vol. 7 No. 1 P. 34-39

A database (DB) on the bandgap of inorganic substances available via the Internet (http://bg.imetdb.ru) was developed for the information service of specialists in the sphere of inorganic chemistry and materials science. The DB is integrated with other information systems on the properties of inorganic substances and materials, which provides the search of a wide range ...

Added: February 23, 2016

Svetlana Maltseva, Kornilov V., Barakhnin V. et al., Complexity 2022 Vol. 2022 Article 5714395

We can observe self-organization properties in various systems. However, modern networked dynamical sociotechnical systems have some features that allow for realizing the benefits of self-organization in a wide range of systems in economic and social areas. The review examines the general principles of self-organized systems, as well as the features of the implementation of self-organization ...

Added: April 18, 2022

М. : National Instruments Russia, 2017

Содержание сборника составляют доклады с результатами оригинальных исследований и технических решений, ранее не публиковавшиеся. Мы надеемся, что предлагаемый сборник окажется полезным для специалистов, работающих в различных областях науки и техники, для широкого круга преподавателей, аспирантов и студентов ВУЗов, а также для преподавателей средних школ и технических колледжей. ...

Added: May 10, 2017

Furmanov K. K., Nikol'skii I. M., Computational Mathematics and Modeling 2016 Vol. 27 No. 2 P. 247-253

Added: December 22, 2016

Aaij R., Abdelmotteleb A. S., Abellán Beteta C. et al., Physical Review Letters 2022 Vol. 129 No. 9 Article 091801

The first study of the angular distribution of μþμ− pairs produced in the forward rapidity region via the Drell-Yan reaction pp → γ=Z þ X → lþl− þ X is presented, using data collected with the LHCb detector at a center-of-mass energy of 13 TeV, corresponding to an integrated luminosity of 5.1 fb−1. The coefficients ...

Added: December 29, 2022