ECCC-Report TR19-035https://eccc.weizmann.ac.il/report/2019/035Comments and Revisions published for TR19-035en-usTue, 05 Mar 2019 16:25:03 +0200
Paper TR19-035
| PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials |
Alexey Milovanov
https://eccc.weizmann.ac.il/report/2019/035
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.Tue, 05 Mar 2019 16:25:03 +0200https://eccc.weizmann.ac.il/report/2019/035