| 11. |
- de Rezende, Susanna F.
(författare)
-
Lower Bounds and Trade-offs in Proof Complexity
- 2019
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Propositional proof complexity is a field in theoretical computer science that analyses the resources needed to prove statements. In this thesis, we are concerned about the length of proofs and trade-offs between different resources, such as length and space.A classical NP-hard problem in computational complexity is that of determining whether a graph has a clique of size k. We show that for all k ≪ n^(1/4) regular resolution requires length n^Ω(k) to establish that an Erdős–Rényi graph with n vertices and appropriately chosen edge density does not contain a k-clique. In particular, this implies an unconditional lower bound on the running time of state-of-the-artalgorithms for finding a maximum clique.In terms of trading resources, we prove a length-space trade-off for the cutting planes proof system by first establishing a communication-round trade-off for real communication via a round-aware simulation theorem. The technical contri-bution of this result allows us to obtain a separation between monotone-AC^(i-1) and monotone-NC^i.We also obtain a trade-off separation between cutting planes (CP) with unbounded coefficients and cutting planes where coefficients are at most polynomial in thenumber of variables (CP*). We show that there are formulas that have CP proofs in constant space and quadratic length, but any CP* proof requires either polynomial space or exponential length. This is the first example in the literature showing any type of separation between CP and CP*.For the Nullstellensatz proof system, we prove a size-degree trade-off via a tight reduction of Nullstellensatz refutations of pebbling formulas to the reversible pebbling game. We show that for any directed acyclic graph G it holds that G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatzrefutation of the pebbling formula over G in size t + 1 and degree s.Finally, we introduce the study of cumulative space in proof complexity, a measure that captures the space used throughout the whole proof and not only the peak space usage. We prove cumulative space lower bounds for the resolution proof system, which can be viewed as time-space trade-offs where, when time is bounded, space must be large a significant fraction of the time.
|
|
| 12. |
- de Rezende, Susanna F., et al.
(författare)
-
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
- 2019
-
Ingår i: Proceedings of the 34th Annual Computational Complexity Conference (CCC ’19). - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959771160 ; , s. 18:1-18:16
-
Konferensbidrag (refereegranskat)abstract
- We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if an only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.
|
|
| 13. |
- De Rezende, Susanna F., et al.
(författare)
-
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
- 2021
-
Ingår i: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 30:1
-
Tidskriftsartikel (refereegranskat)abstract
- We establish an exactly tight relation between reversiblepebblings of graphs and Nullstellensatz refutations of pebbling formulas,showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formulaover G in size t + 1 and degree s (independently of the field in whichthe Nullstellensatz refutation is made). We use this correspondenceto prove a number of strong size-degree trade-offs for Nullstellensatz,which to the best of our knowledge are the first such results for thisproof system.
|
|
| 14. |
- de Rezende, Susanna F., et al.
(författare)
-
The power of negative reasoning
- 2021
-
Ingår i: 36th Computational Complexity Conference, CCC 2021. - 1868-8969. - 9783959771931 ; 200
-
Konferensbidrag (refereegranskat)abstract
- Semialgebraic proof systems have been studied extensively in proof complexity since the late 1990s to understand the power of Gröbner basis computations, linear and semidefinite programming hierarchies, and other methods. Such proof systems are defined alternately with only the original variables of the problem and with special formal variables for positive and negative literals, but there seems to have been no study how these different definitions affect the power of the proof systems. We show for Nullstellensatz, polynomial calculus, Sherali-Adams, and sums-of-squares that adding formal variables for negative literals makes the proof systems exponentially stronger, with respect to the number of terms in the proofs. These separations are witnessed by CNF formulas that are easy for resolution, which establishes that polynomial calculus, Sherali-Adams, and sums-of-squares cannot efficiently simulate resolution without having access to variables for negative literals.
|
|
| 15. |
- Rezende, Susanna F.de, et al.
(författare)
-
KRW Composition Theorems via Lifting
- 2024
-
Ingår i: Computational Complexity. - 1016-3328. ; 33:1
-
Tidskriftsartikel (refereegranskat)abstract
- One of the major open problems in complexity theory is proving super-logarithmiclower bounds on the depth of circuits (i.e., P⊈NC1). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC1.Several works have made progress toward resolving this conjectureby proving special cases. In particular, these works proved the KRWconjecture for every outer function f, but only for few innerfunctions g. Thus, it is an important challenge to prove the KRWconjecture for a wider range of inner functions.In this work, we extend significantly the range of inner functionsthat can be handled. First, we consider the monotone versionof the KRW conjecture. We prove it for every monotone inner function gwhose depth complexity can be lower-bounded via a query-to-communicationlifting theorem. This allows us to handle several new and well-studiedfunctions such as the s-t-connectivity, clique,and generation functions.In order to carry this progress back to the non-monotone setting,we introduce a new notion of semi-monotone composition, whichcombines the non-monotone complexity of the outer function f withthe monotone complexity of the inner function g. In this setting,we prove the KRW conjecture for a similar selection of inner functions g,but only for a specific choice of the outer function f.
|
|
