Paper Info
Title
Monomial size vs. Bit-complexity in Sums-of-Squares and Polynomial Calculus
Abstract
In this paper we consider the relationship between monomial-size and bit-complexity in Sums-of-Squares (SOS) in Polynomial Calculus Resolution over rationals $({\text{PCR}}/\mathbb{Q})$. We show that there is a set of polynomial constraints Qn over Boolean variables that has both SOS and ${\text{PCR}}/\mathbb{Q}$ refutations of degree 2 and thus with only polynomially many monomials, but for which...
Year
DOI
Venue
2021
10.1109/LICS52264.2021.9470545
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Keywords
DocType
ISBN
Computer science,Calculus
Conference
978-1-6654-4895-6
Citations 
PageRank 
References 
0
0.34
0
Authors
1
Name
Order
Citations
PageRank
Tuomas Hakoniemi100.34