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 Hakoniemi | 1 | 0 | 0.34 |