Gibt es einen alternativen Beweis oder eine Darstellung des Ergebnisses von Grigoriev und Karpinski (STOC 1998, doi: 10.1145 / 276698.276872 ) für die exponentiellen Untergrenzen für arithmetische Schaltungen der Tiefe 3, die über ein festes endliches Feld berechnen ?
Ich konnte Abschnitt 2 des Papiers nicht verstehen. Welche Intuition steckt hinter der Betrachtung des F-Linearoperators ?
circuit-complexity
arithmetic-circuits
Stattrav
quelle
quelle