A. Milovanov

activity

20192026

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2026

Limit on the computational power of $C$ -random strings

Alexey Milovanov

We construct a universal decompressor $U$ for plain Kolmogorov complexity $C_{U}$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with…

cs.CC2024

On the computational power of $C$ -random strings

Alexey Milovanov

Denote by $H$ the Halting problem. Let $R_{U} := {x ∣ C_{U} (x) \geq ∣ x ∣}$ , where $C_{U} (x)$ is the plain Kolmogorov complexity of $x$ under a universal decompressor $U$ . We prove that…

cs.CC2019

PIT for depth- $4$ 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- $4$ …

Limit on the computational power of C-random strings

On the computational power of C-random strings

PIT for depth-4 circuits and Sylvester-Gallai conjecture for polynomials

Limit on the computational power of $C$ -random strings

On the computational power of $C$ -random strings

PIT for depth- $4$ circuits and Sylvester-Gallai conjecture for polynomials