Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Algebraic computation models
Tags: fromMath mathToDef mathToSee récupéré

Name: Algebraic straight line program of length \(T\), with constants \(c_1,\dots,c_k\) and variables \(x_1,\dots,x_n\)
Definition: A sequence of \(T\) instructions \(y_i=z_{i_1} OP z_{i_2}\), and \(z_{i_1},z_{i_1}\) are constants, \(y_j\) for \(j<i\) or a \(x_i\).
Page: 319
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field,
\(T\in\mathbb N\),
\((c_i)\in\mathbb F\)
Kind: Def

Q: [...] is [...].
A: The output of \(T\); the value of \(y_T\)
Page: 319
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field, \(T\) an algebraic straight line programs.
Kind: Def

Definition: The function defined by \(T\).
Page: 319
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field
\(T\) an algebraic straight line programs.
Index: 4
Kind: Lem
Typ: A polynomial

Definition: The function defined by \(T\)
Page: 321
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field
\(T\) an algebraic straight line programs with division
Index: 5
Kind: Lem
Typ: A rational function of degree at most \(2^T\)

Question: The degree of the function defined by \(T\) is
Answer: at most \(2^T\).
Page: 319
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field
\(T\) an algebraic straight line programs
Index: 4
Kind: Lem

Question: The degree of the function defined by \(T\) is
Answer: at most \(2^T\).
Page: 321
Chapter: 16
Section: 2
Variables: \(\mathbb F\) a field
\(T\) an algebraic straight line programs with division
Index: 5
Kind: Lem

Name: An Algebraic circuit
Definition: A circuit with constants, \(+,\times\) as gates.
Page: 322
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field

Smaller0: \(f\) is computable by a circuit of size \(S\)
Greater0: \(f\) is computable by a straight line probgram of size \(S\) where each non-input variable is used exactly once
Page: 322
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field
\(f:\mathbb F^n\to\mathbb F\) a function
\(S\in\mathbb N\)
Index: 6
Kind: Lem

Smaller0: \(f\) is computable by a straight-line program of size \(S\)
Greater0: \(f\) is computable by a circuit of size \(3S\)
Page: 322
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field
\(f:\mathbb F^n\to\mathbb F\) a function
\(S\in\mathbb S\)
Index: 6
Kind: Lem

Name: A polynomially-bounded degree sequence of polynomials
Definition: A sequence of polynomials \((p_n)_{n\in\mathbb N}\in\mathbb F[x]\) such that there exists \(c\in\mathbb N\) such that the degree of \(p_n\) is at most \(cn^c\).
Page: 323
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field
Index: 7
Kind: Def

Definition: All polynomially bounded degree families of polynomials that are computable by algebraic circuits of polynomial size and degree.
Page: 323
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field.
Notation: \(\mathbf{AlgP_{/poly}}\)
Index: 7
Kind: Def

Definition: the set of functions \(\sum_{e\in\{0,1\}^{m-n} }g_m(x_1,\dots,x_n,e_{n+1},\dots,e_m)\) where \(g_m\in\mathbf{AlgP_{/poly} }\) and \(m\) is polynomial in \(n\).
Page: 323
Chapter: 16
Section: 3
Variables: \(\mathbf F\) a field.
Notation: \(\mathbf{AlgNP_{/poly}}\)
Index: 7
Kind: Def