Name
Abstract | ||
|---|---|---|
In a multi--ic depth three circuit every variable appears in at most of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi--ic depth three circuit can be where is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta et al. () on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi--ic depth three circuits for any arbitrary constant . |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/S00224-016-9742-9 | Theory Comput. Syst. |
Keywords | Field | DocType |
Arithmetic circuits,Multilinear depth three,Lower bound,Evaluation dimension | Discrete mathematics,Combinatorics,Exponential function,Polynomial,Upper and lower bounds,Electronic circuit,Multilinear map,Mathematics | Conference |
Volume | Issue | ISSN |
61 | 4 | 1432-4350 |
Citations | PageRank | References |
1 | 0.35 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Chandan Saha | 2 | 227 | 16.91 |