2026-07-24T09:36:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4939 2024-03-06T10:35:35Z ddc:004 open_access

Multi-k-ic Depth Three Circuit Lower Bound Kayal, Neeraj Saha, Chandan arithmetic circuits multilinear circuits depth three circuits lower bound individual degree In a multi-k-ic depth three circuit every variable appears in at most k 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-k-ic depth three circuit can be kn where n 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, Kamath, Kayal and Saptharishi [7] on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi-k-ic depth three circuits for any arbitrary constant k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Neeraj Kayal and Chandan Saha 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.527 urn:nbn:de:0030-drops-49395 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.527 eng https://creativecommons.org/licenses/by/3.0/legalcode