| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Semi-Algebraic Proofs, IPS Lower Bounds and the $ au$-Conjecture: Can a Natural Number be Negative? | Yaroslav Alekseev
; Dima Grigoriev
; Edward A. Hirsch
; Iddo Tzameret
; | Date: |
15 Nov 2019 | Abstract: | We introduce the binary value principle which is a simple subset-sum instance
expressing that a natural number written in binary cannot be negative, relating
it to central problems in proof and algebraic complexity. We prove conditional
superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of
this instance, based on a well-known hypothesis by Shub and Smale about the
hardness of computing factorials, where IPS is the strong algebraic proof
system introduced by Grochow and Pitassi (2018). Conversely, we show that short
IPS refutations of this instance bridge the gap between sufficiently strong
algebraic and semi-algebraic proof systems. Our results extend to full-fledged
IPS the paradigm introduced in Forbes et al. (2016), whereby lower bounds
against subsystems of IPS were obtained using restricted algebraic circuit
lower bounds, and demonstrate that the binary value principle captures the
advantage of semi-algebraic over algebraic reasoning, for sufficiently strong
systems. Specifically, we show the following: (abstract continues in document.) | Source: | arXiv, 1911.6738 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |