Seminars
View all Seminars | Download ICal for this eventRecent developments on ∃R-completeness of packing and other problems
Series: Theory Seminar
Speaker: Dr. Mikkel Abrahamsen, Assistant Professor, Department of Computer Science, University of Copenhagen,
Date/Time: Oct 22 16:00:00
Location: Microsoft Teams - ON-LINE
Faculty Advisor:
Abstract:
We will give an introduction to the complexity class ∃R, which consists of problems that are polynomial time reducible to deciding whether system of polynomial equations and inequalities with integer coefficients and many unknowns has a real solution. Many classic problems have recently been shown to be ∃R-complete, such as the Art Gallery Problem, the Minimum Convex Cover problem, training neural networks, geometric embeddability of simplicial complexes, and many variants of 2D packing problems. We will outline some of the techniques used in these proofs, in particular for the case of the ∃R-hardness of packing problems.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Speaker Bio:
Host Faculty: Dr. Arindam Khan