Title: Theory / Unimportant / CS / Fundamental / Complexity / Wigderson / 12 Arithmetic complexity
Tags: hasSeenConjDef

Definition: The minimal size of an arithmetic circuit computing \(f\)
Page: 142
Chapter: 12
Variables: \(f\) a polynomial function
Notation: \(\mathrm{S}(f)\)

Question: \(\mathrm{S}(f)\) is bounded above by
Answer: \(O(\text{deg}f)\)
Page: 142
Chapter: 12
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)

Question: \(\mathrm{S}(f)\) worst case is bounded below by
Answer: \(\Omega(\sqrt {\text{deg}f})\).
Page: 142
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)

Question: \(\mathrm{S}(x^d)\) is
Answer: \(O(\log d)\).
Page: 142
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)

Question: \(\mathrm{S}(\prod_{i=1}^d (x^i))\) is
Answer: unknown.
Page: 142
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)

Smaller0: \(\mathrm{S}(\prod_{i=1}^d (x^i))\le (\log \text{deg }d)^{O(1)}\)
Greater0: Integer Factoring is in \(\mathcal P/poly\)
Page: 142
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)
Index: 2
Kind: Theo

Name: An arithmetic circuit over \(\mathbb F\)
Definition: the non-input gates are labeled with the arithmetic operations + or ×.
Page: 142
Chapter: 12
Section: 2
Variables: \(\mathbb F\) a field
Definition2: The input nodes can be labeled with the variables \(x_i\) , as well as with any constants from \(\mathbb F\).
Conjdef: A directed acyclic graph in which

Name: The size of \(C\)
Definition: The number of wires in the graph \(C\)
Page: 142
Chapter: 12
Section: 2
Variables: \(\mathbb F\) a field
\(C\) an arithmetic circuit

Name: An arithmetic formula
Definition: A circuit whose graph is a tree.
Page: 142
Chapter: 12
Section: 2
Variables: \(\mathbb F\) a field

Definition: The size of the minimal formula computing \(f\)
Page: 142
Chapter: 12
Section: 2
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x_1,\dots,x_n]\)
Notation: \(\mathrm L(f)\)

Smaller0: \(\mathrm{S}(f)\)
Greater0: \(\mathrm{L}(f)\)
Page: 143
Chapter: 12
Section: 1
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)
Hide sides: Yes

Question: The size complexity of \(x^p\) over \(\mathbb F_p\) is
Answer: at least \(\log p\) as a formal polynomial, and constant as a function (not considered here)
Page: 143
Chapter: 12
Section: 1

Definition: The determinant polynomial with variables \((x_{i,j})_{1\le i,j\le n}\)
Page: 143
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(n\in\mathbb N\)
Notation: \(Det_n\)

Definition: The family \((DET_n)_{n\in\mathbb N}\)
Page: 143
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field,
Notation: \(Det\)

Name: A multilinear polynomial
Definition: in which every variable appears in every monomial with degree at most 1
Page: 143
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
Definition2: affine in each variable
Conjdef: A polynomial, equivalently

Question: Almost all multilinear polynomials \(f\) on \(n\) variables with 0/1 coefficients require that \(S(f )\)
Answer: \( \ge 2^{n/10}\)
Page: 143
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
Index: 3
Kind: Theo

Smaller0: \(\mathrm L(f)\)
Greater0: \(\mathrm{S}(f)^{O(\log \text{deg }f)}\)
Page: 143
Chapter: 12
Section: 1
Variables: \(\mathbb F\) a field
\(f\in\mathbb F[x]\)
Index: 5
Kind: Theo
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)