  The complexity class PPA consists of NP-search 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
PPA-completeness of two problems of radically different style. They are
PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the
Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two
elements field GF(2). The input of these problems contain PPA-circuits 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
PPA-circuit can be paired in polynomial time.
