Guo, Zeyu ;
Saxena, Nitin ;
Sinhababu, Amit
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity
Abstract
Testing whether a set f of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). Previously, the best complexity known was NP^{#P} (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). In this work we put the problem in AM cap coAM. In particular, dependence testing is unlikely to be NPhard and joins the league of problems of "intermediate" complexity, eg. graph isomorphism & integer factoring. Our proof method is algebrogeometric estimating the size of the image/preimage of the polynomial map f over the finite field. A gap in this size is utilized in the AM protocols.
Next, we study the open question of testing whether every annihilator of f has zero constant term (Kayal, CCC'09). We give a geometric characterization using Zariski closure of the image of f; introducing a new problem called approximate polynomials satisfiability (APS). We show that APS is NPhard and, using projective algebraicgeometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Gröbner basis computation). As an unexpected application of this to approximative complexity theory we get over any field, hittingsets for overline{VP} can be verified in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).
BibTeX  Entry
@InProceedings{guo_et_al:LIPIcs:2018:8878,
author = {Zeyu Guo and Nitin Saxena and Amit Sinhababu},
title = {{Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {10:110:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770699},
ISSN = {18688969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8878},
URN = {urn:nbn:de:0030drops88786},
doi = {10.4230/LIPIcs.CCC.2018.10},
annote = {Keywords: algebraic dependence, Jacobian, ArthurMerlin, approximate polynomial, satisfiability, hittingset, border VP, finite field, PSPACE, EXPSPACE, GCT Cha}
}
2018
Keywords: 

algebraic dependence, Jacobian, ArthurMerlin, approximate polynomial, satisfiability, hittingset, border VP, finite field, PSPACE, EXPSPACE, GCT Cha 
Seminar: 

33rd Computational Complexity Conference (CCC 2018)

Issue date: 

2018 
Date of publication: 

2018 