Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Sylvester-Gallai type problems:
TR14-130 | 17th October 2014
Ankit Gupta

Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... more >>>

TR20-125 | 17th August 2020
Gaurav Sinha

Efficient reconstruction of depth three circuits with top fan-in two

In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>

ISSN 1433-8092 | Imprint