1 citations · 2 across the 9 of their papers we have counts for
9 papers
Limit on the computational power of -random strings
Alexey Milovanov
We construct a universal decompressor for plain Kolmogorov complexity such that the Halting Problem cannot be decided by any polynomial-time oracle machine with…
On the computational power of -random strings
Alexey Milovanov
Denote by the Halting problem. Let , where is the plain Kolmogorov complexity of under a universal decompressor . We prove that…
Predictions and algorithmic statistics for infinite sequence
Alexey Milovanov
Consider the following prediction problem. Assume that there is a block box that produces bits according to some unknown computable distribution on the binary tree. We know first $…
PIT for depth- circuits and Sylvester-Gallai conjecture for polynomials
Alexey Milovanov
This text is a development of a preprint of Ankit Gupta. We present an approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-…
On Algorithmic Statistics for space-bounded algorithms
Alexey Milovanov
Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity an…
Algorithmic statistics: normal objects and universal models
Alexey Milovanov
Kolmogorov suggested to measure quality of a statistical hypothesis for a data by two parameters: Kolmogorov complexity of the hypothesis and the probability …
Algorithmic statistics, prediction and machine learning
Alexey Milovanov
Algorithmic statistics considers the following problem: given a binary string (e.g., some experimental data), find a "good" explanation of this data. It uses algorithmic inform…
Some properties of antistochastic strings
Alexey Milovanov
Antistochastic strings are those strings that lack any reasonable statistical explanations. We establish the follow property of such strings: every absolutely non-stochastic string…
Bounds of some parameters of elliptic curve on finite field
Alexey Milovanov
I prove lower bounds of some parameters of elliptic curve over finite field. There parameters are closely interrelated with cryptographic stability of elliptic curve.