BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Meirav Zehavi (BGU\, Beersheba)
DTSTART:20201117T173000Z
DTEND:20201117T180000Z
DTSTAMP:20260423T023010Z
UID:LA-CoCo/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/LA-CoCo/10/"
 >Computation of Hadwiger Number and Related Contraction Problems: Tight Lo
 wer Bounds</a>\nby Meirav Zehavi (BGU\, Beersheba) as part of LA Combinato
 rics and Complexity Seminar\n\n\nAbstract\nWe prove that the Hadwiger numb
 er of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) 
 cannot be computed in time $n^{o(n)}$\, unless the Exponential Time Hypoth
 esis (ETH) fails. This resolves a well-known open question in the area of 
 exact exponential algorithms. The technique developed for resolving the Ha
 dwiger number problem has a wider applicability. We use it to rule out the
  existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of 
 computational problems concerning edge contractions in graphs.\n\nJoint wo
 rk with Fomin\, Lokshtanov\, Mihajlin and Saurabh.\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/10/
END:VEVENT
END:VCALENDAR