Pandey, Anurag ;
Saxena, Nitin ;
Sinhababu, Amit
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
Abstract
The motivation for this work comes from two problemstest algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields.
It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized polytime algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07).
In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth4 circuits). We also recover their quasipolytime hittingset for such models, for fields of characteristic smaller than the ones known before.
Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods.
BibTeX  Entry
@InProceedings{pandey_et_al:LIPIcs:2016:6505,
author = {Anurag Pandey and Nitin Saxena and Amit Sinhababu},
title = {{Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {74:174:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6505},
URN = {urn:nbn:de:0030drops65057},
doi = {10.4230/LIPIcs.MFCS.2016.74},
annote = {Keywords: independence, transcendence, finite field, HasseSchmidt, Jacobian, differential, inseparable, circuit, identity testing, lower bound, depth4, shifte}
}
2016
Keywords: 

independence, transcendence, finite field, HasseSchmidt, Jacobian, differential, inseparable, circuit, identity testing, lower bound, depth4, shifte 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

2016 