> Detailanzeige

Kayal, Neeraj [VerfasserIn]; Saha, Chandan [VerfasserIn]; Tavenas, Sébastien [VerfasserIn] ; Neeraj Kayal and Chandan Saha and Sébastien Tavenas [MitwirkendeR]

An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht
  • Titel: An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits
  • Beteiligte: Kayal, Neeraj [VerfasserIn]; Saha, Chandan [VerfasserIn]; Tavenas, Sébastien [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ICALP.2016.33
  • Schlagwörter: shifted partials ; depth-3 circuits ; arithmetic circuits
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
  • Zugangsstatus: Freier Zugang