1 Search Results for "Yang, Siyi"

Document
DOI: 10.4230/LIPIcs.CCC.2017.30
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz

Authors: Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
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.
Cite as

Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, and Siyi Yang. On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 30:1-30:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{belovs_et_al:LIPIcs.CCC.2017.30,
  author =	{Belovs, Aleksandrs and Ivanyos, G\'{a}bor and Qiao, Youming and Santha, Miklos and Yang, Siyi},
  title =	{{On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{30:1--30:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.30},
  URN =		{urn:nbn:de:0030-drops-75260},
  doi =		{10.4230/LIPIcs.CCC.2017.30},
  annote =	{Keywords: Chevalley-Warning Theorem, Combinatorail Nullstellensatz, Polynomial Parity Argument, arithmetic circuit}
}
  • Refine by Author
  • 1 Belovs, Aleksandrs
  • 1 Ivanyos, Gábor
  • 1 Qiao, Youming
  • 1 Santha, Miklos
  • 1 Yang, Siyi

  • Refine by Classification

  • Refine by Keyword
  • 1 Chevalley-Warning Theorem
  • 1 Combinatorail Nullstellensatz
  • 1 Polynomial Parity Argument
  • 1 arithmetic circuit

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact