Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-035 | 5th March 2019 15:13

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


Authors: Alexey Milovanov
Publication: 5th March 2019 16:25
Downloads: 827


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 algorithm on Sylvester-Gallai-type theorem about linear polynomials. We show how it is possible to generalize this approach to depth-$4$ circuits. However we failed to implement this plan completely. We succeeded to construct a polynomial time deterministic algorithm for depth-$4$ circuits with bounded top fanin and its correctness requires a hypothesis. Also we present a polynomial-time (unconditional) algorithm for some subclass of depth-$4$ circuits with bounded top fanin.

ISSN 1433-8092 | Imprint