SwePub
Sök i SwePub databas

  Extended search

Träfflista för sökning "(WFRF:(Jakob Robert)) srt2:(2020-2022) srt2:(2021) pers:(Nordström Jakob) "

Search: (WFRF:(Jakob Robert)) srt2:(2020-2022) srt2:(2021) pers:(Nordström Jakob)

  • Result 1-2 of 2
Sort/group result
   
EnumerationReferenceCoverFind
1.
  • De Rezende, Susanna F., et al. (author)
  • Automating algebraic proof systems is NP-hard
  • 2021
  • In: STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 0737-8017. - 9781450380539 ; , s. 209-222
  • Conference paper (peer-reviewed)abstract
    • We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.
  •  
2.
  • De Rezende, Susanna F., et al. (author)
  • Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
  • 2021
  • In: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 30:1
  • Journal article (peer-reviewed)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.
  •  
Skapa referenser, mejla, bekava och länka
  • Result 1-2 of 2
Type of publication
conference paper (1)
journal article (1)
Type of content
peer-reviewed (2)
Author/Editor
de Rezende, Susanna ... (2)
Nordström, Jakob (2)
Robere, Robert (2)
Pitassi, Toniann (1)
Sokolov, Dmitry (1)
Göös, Mika (1)
show more...
Khuller, Samir (1)
Williams, Virginia V ... (1)
Meir, Or (1)
show less...
University
Lund University (2)
Language
English (2)
Research subject (UKÄ/SCB)
Natural sciences (2)
Year
2021 (2)

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view