Paper Info
Title
Combinatorial Nullstellensatz Modulo Prime Powers and the Parity Argument.
Abstract
We present new generalizations of Olson's theorem and of a consequence of Alon's Combinatorial Nullstellensatz. These enable us to extend some of their combinatorial applications with conditions modulo primes to conditions modulo prime powers. We analyze computational search problems corresponding to these kinds of combinatorial questions and we prove that the problem of finding degree-constrained subgraphs modulo 2(d) such as 2(d)-divisible subgraphs and the search problem corresponding to the Combinatorial Nullstellensatz over F-2 belong to the complexity class Polynomial Parity Argument (PPA).
Year
Venue
Keywords
2014
ELECTRONIC JOURNAL OF COMBINATORICS
Combinatorial Nullstellensatz,Olson's theorem,PPA
DocType
Volume
Issue
Journal
21.0
4.0
ISSN
Citations 
PageRank 
1077-8926
0
0.34
References 
Authors
4
1
Name
Order
Citations
PageRank
László Zsolt Varga119424.42