BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/979
DTSTAMP:20230914T125945Z
SUMMARY:Murdering Squares and Rectangles using Guillotines
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nAbstract: A bunch of di
 sjoint axis-parallel rectangles are drawn on a single piece of paper. The 
 aim is to divide the paper into several smaller pieces using a series of a
 xis-parallel guillotine cuts such that each rectangle is in a different pi
 ece of paper at the end of all the slashing. Some rectangles might die in 
 the process\; if a guillotine cut is made across the body of a rectangle\,
  then that rectangle is killed. In this talk\, we will see proofs of the f
 ollowing results.\n(i) For every configuration of n rectangles\, there is 
 a series of guillotine cuts such that at least n/log n rectangles survive 
 in the end.\n(ii) If all the rectangles are squares\, then there is a seri
 es of guillotine cuts such that at least n/68 squares survive in the end.\
 nTime permitting\, we will see that if the fraction in the first result ca
 n be improved to n/c (for some constant c)\, then it would imply a solutio
 n to a longstanding open problem in theoretical computer science.\n
URL:https://www.tcs.tifr.res.in/web/events/979
DTSTART;TZID=Asia/Kolkata:20190801T160000
DTEND;TZID=Asia/Kolkata:20190801T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR