Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexey Milovanov:

TR19-035 | 5th March 2019
Alexey Milovanov

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

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

TR17-043 | 3rd March 2017
Alexey Milovanov, Nikolay Vereshchagin

Stochasticity in Algorithmic Statistics for Polynomial Time

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

ISSN 1433-8092 | Imprint