Beecken, Malte ; Mittmann, Johannes ; Saxena, Nitin
(2011)
*Algebraic Independence and Blackbox Identity Testing*
In: Proceedings of the 38th International Conference on Automata, Languages and Programming - Volume Part II, July 2011.

Full text not available from this repository.

Official URL: https://dx.doi.org/10.5555/2027223.2027236

## Abstract

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. The transcendence degree (trdeg) of a set f1, ..., fm ⊂ Fx1, ..., xn of polynomials is the maximal size r of an algebraically independent subset. In this paper we design blackbox and efficient linear maps ϕ that reduce the number of variables from n to r but maintain trdeg{ϕ(fi)}i = r, assuming fi's sparse and small r. We apply these fundamental maps to solve several cases of blackbox identity testing: 1. Given a circuit C and sparse subcircuits f1, ..., fm of trdeg r such that D := C(f1, ..., fm) has polynomial degree, we can test blackbox D for zeroness in poly(size(D))r time. 2. Define a ΣΠΣΠδ(k, s, n) circuit C to be of the form Σi=1k Πj=1s fi,j, where fi,j are sparse n-variate polynomials of degree at most δ. For k = 2, we give a poly (δsn)δ2 time blackbox identity test. 3. For a general depth-4 circuit we define a notion of rank. Assuming there is a rank bound R for minimal simple ΣΠΣΠδ(k, s, n) identities, we give a poly(δsnR)Rkδ2 time blackbox identity test for ΣΠΣΠδ(k, s, n) circuits. This partially generalizes the state of the art of depth-3 to depth-4 circuits.The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.

Item Type: | Conference or Workshop Item (Paper) |
---|---|

Source: | Copyright of this article belongs to Association for Computing Machinery. |

ID Code: | 122772 |

Deposited On: | 16 Aug 2021 07:31 |

Last Modified: | 16 Aug 2021 07:31 |

Repository Staff Only: item control page