Workshop on Hardness of Approximation in P
July 21 - 23, 2025
Rutgers University, New Brunswick, NJ (exact location TBA)
Organizer:
Karthik C.S., Rutgers University
Presented in association with the Special Focus on Fine-grained Complexity<http://dimacs.rutgers.edu/programs/sf/fg-complexity>.
*********************************************************************
Workshop Announcement:
Many important optimization problems are not tractable. A typical way to cope with such intractability is to design algorithms that find solutions whose cost or value is close to the optimum. In several interesting cases, it is possible to prove that even finding good approximate solutions is as hard as finding optimal solutions. The area that studies such inapproximability results is called hardness of approximation. In the area of hardness of approximation, the primary emphasis lies in demonstrating the NP-hardness of approximating different NP-Hard optimization problems via the celebrated PCP theorem. Nevertheless, over the past decade, there has been a booming focus on establishing hardness of approximation results for optimization problems within P.
The study of Hardness of Approximation in P has primarily focused on two categories of problems: parameterized problems and subquadratic hard problems. In parameterized complexity, the notable achievements are the hardness of approximation results for the k-Set Cover problem, the k-Set Intersection problem, and the k-Clique problem, with the current prized goal of the community being to prove the Parameterized Inapproximability Hypothesis (a.k.a. the PCP theorem for Parameterized Complexity). In fine-grained subquadratic hardness of approximation, the main highlights are the inapproximability of the Max Inner Product problem, Nearest Neighbor Search problem, and the Closest-LCS-Pair problem. While there are many important open problems, proving the subquadratic hardness of approximating the edit distance of two strings is arguably the current biggest challenge. This workshop will bring together three distinct communities-hardness of approximation in NP, fine-grained complexity, and parameterized complexity-to foster exchange of ideas and the development of synergistic collaborations among these communities.
To facilitate the seamless interaction among the three communities moving forward, the workshop will include several tutorials that collectively encompass the majority of the foundational knowledge necessary for engaging with hardness of approximation in P.
A preliminary program with scheduled speakers is available on the workshop website: http://dimacs.rutgers.edu/events/details?eID=3156
*********************************************************************
Call for Participation:
Presentations at this workshop are by invitation but others are welcome to attend. There is no fee to attend but registration is required. If you would like to attend this workshop, please register at the workshop web page<http://dimacs.rutgers.edu/events/details?eID=3156> using the button at the bottom of the page. Space is limited, so please register early if you plan to attend.
Request support: There are limited funds available to support travel. Priority will be given to those whose interests align with the topic and whose attendance is contingent on support, especially students. To request support please complete and submit this form<https://docs.google.com/forms/d/e/1FAIpQLSerJbNULDm0TkwweVS8UOrf4VVj6F4fPCrVuTCJJG3-rpWhFA/viewform?usp=sharing> by April 15, 2025 for full consideration. You will receive a response shortly after the April 15, 2025 deadline. Please do not book your tickets until you hear from us if you need support!
*********************************************************************
Workshop web site (including registration):
http://dimacs.rutgers.edu/events/details?eID=3156
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
