Speaker: |
Kshitij Gajjar |

Organiser: |
Phani Raj Lolakapuri |

Date: |
Thursday, 1 Aug 2019, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

(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.

(ii) If all the rectangles are squares, then there is a series of guillotine cuts such that at least n/68 squares survive in the end.

Time permitting, we will see that if the fraction in the first result can be improved to n/c (for some constant c), then it would imply a solution to a longstanding open problem in theoretical computer science.