A. Milovanov

collaborators

2 papers

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$ …

On the computational power of C-random strings

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

On the computational power of $C$ -random strings

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