All reports by Author Alexey Milovanov:

__
TR24-034
| 19th February 2024
__

Bruno Loff, Alexey Milovanov#### The hardness of decision tree complexity

__
TR22-134
| 23rd September 2022
__

Greg McLellan, Alexey Milovanov#### Some Games on Turing Machines and Power from Random Strings

Revisions: 1

__
TR19-035
| 5th March 2019
__

Alexey Milovanov#### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials

__
TR17-043
| 3rd March 2017
__

Alexey Milovanov, Nikolay Vereshchagin#### Stochasticity in Algorithmic Statistics for Polynomial Time

Bruno Loff, Alexey Milovanov

Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is ... more >>>

Greg McLellan, Alexey Milovanov

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.

Power from random strings.

\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea ...
more >>>

Alexey Milovanov

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.

This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ...
more >>>

Alexey Milovanov, Nikolay Vereshchagin

A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for $x$ if it looks likely that $x$ was drawn at random with respect to that distribution. In this paper, we ... more >>>