| 1. |
- Beck, C., et al.
(författare)
-
Some trade-off results for polynomial calculus
- 2013
-
Ingår i: STOC '13 Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450320290 ; , s. 813-822
-
Konferensbidrag (refereegranskat)abstract
- We present size-space trade-offs for the polynomial calculus (PC) and polynomial calculus resolution (PCR) proof systems. These are the first true size-space trade-offs in any algebraic proof system, showing that size and space cannot be simultaneously optimized in these models. We achieve this by extending essentially all known size-space trade-offs for resolution to PC and PCR. As such, our results cover space complexity from constant all the way up to exponential and yield mostly superpolynomial or even exponential size blow-ups. Since the upper bounds in our trade-offs hold for resolution, our work shows that there are formulas for which adding algebraic reasoning on top of resolution does not improve the trade-off properties in any significant way. As byproducts of our analysis, we also obtain trade-offs between space and degree in PC and PCR exactly matching analogous results for space versus width in resolution, and strengthen the resolution trade-offs in [Beame, Beck, and Impagliazzo '12] to apply also to k-CNF formulas.
|
|
| 2. |
- Huang, Sangxia, 1988-
(författare)
-
Approximation resistance on satisfiable instances for predicates with few accepting inputs
- 2013
-
Ingår i: Symposium on Theory of Computing Conference. - New York, NY, USA : ACM. - 9781450320290 ; , s. 457-466
-
Konferensbidrag (refereegranskat)abstract
- For every integer k≥ 3, we prove that there is a predicate P on k Boolean variables with 2O(k1/3) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Hastad and Khot where the predicate has 2 O(k1/2) accepting assignments.Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Chan [5]. We also use techniques from Wenner [32] to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.
|
|
