SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(De Rezende Susanna F.) srt2:(2023)"

Sökning: WFRF:(De Rezende Susanna F.) > (2023)

  • Resultat 1-2 av 2
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Conneryd, Jonas, et al. (författare)
  • Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
  • 2023
  • Ingår i: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - 0272-5428. - 9798350318944 ; , s. 1-11
  • Konferensbidrag (refereegranskat)abstract
    • We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3-colourable.
  •  
2.
  • De Rezende, Susanna F., et al. (författare)
  • Clique Is Hard on Average for Unary Sherali-Adams
  • 2023
  • Ingår i: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - 0272-5428. - 9798350318944 ; , s. 12-25
  • Konferensbidrag (refereegranskat)abstract
    • We prove that unary Sherali-Adams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-2 av 2
Typ av publikation
konferensbidrag (2)
Typ av innehåll
refereegranskat (2)
Författare/redaktör
de Rezende, Susanna ... (2)
Risse, Kilian (2)
Nordstrom, Jakob (1)
Conneryd, Jonas (1)
Pang, Shuo (1)
Potechin, Aaron (1)
Lärosäte
Lunds universitet (2)
Språk
Engelska (2)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (2)
År
2023 (2)Ta bort avgränsningen

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 Stäng

Kopiera och spara länken för att återkomma till aktuell vy