Sökning: WFRF:(Nordström Jakob 1972 ) >
Nullstellensatz Siz...
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
-
- de Rezende, Susanna F. (författare)
- KTH,Teoretisk datalogi, TCS
-
- Nordström, Jakob, 1972- (författare)
- KTH,Teoretisk datalogi, TCS,Univ Copenhagen, Copenhagen, Denmark
-
- Meir, Or (författare)
- Univ Haifa, Haifa, Israel
-
visa fler...
-
- Robere, Robert (författare)
- DIMACS, New Brunswick, NJ USA
-
visa färre...
-
(creator_code:org_t)
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019
- 2019
- Engelska.
-
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
- Relaterad länk:
-
https://computationa...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas