Belovs, Aleksandrs ;
Ivanyos, Gábor ;
Qiao, Youming ;
Santha, Miklos ;
Yang, Siyi
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Abstract
The complexity class PPA consists of NPsearch problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems.
Here we prove the PPAcompleteness of two problems of radically different style. They are PPACircuit CNSS and PPACircuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the ChevalleyWarning Theorem over the two elements field GF(2). The input of these problems contain PPAcircuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPAcircuit can be paired in polynomial time.
BibTeX  Entry
@InProceedings{belovs_et_al:LIPIcs:2017:7526,
author = {Aleksandrs Belovs and G{\'a}bor Ivanyos and Youming Qiao and Miklos Santha and Siyi Yang},
title = {{On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {30:130:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7526},
URN = {urn:nbn:de:0030drops75260},
doi = {10.4230/LIPIcs.CCC.2017.30},
annote = {Keywords: ChevalleyWarning Theorem, Combinatorail Nullstellensatz, Polynomial Parity Argument, arithmetic circuit}
}
2017
Keywords: 

ChevalleyWarning Theorem, Combinatorail Nullstellensatz, Polynomial Parity Argument, arithmetic circuit 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

2017 