Seminars

View all Seminars  |  Download ICal for this event

Recent 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