Organizer(s):

Karthik C.S., Rutgers University

Description

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.

Program

Monday, July 21, 2025

Tuesday, July 22, 2025

Wednesday, July 23, 2025

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. Please register using the link at the bottom of the page.

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 by April 15, 2025 for full consideration. You will receive a response shortly after the April 15 deadline. Please do not book your tickets until you hear from us if you need support!

What information is requested in the form? Here are some things we will ask for:

• A short statement (one paragraph) about your research area and your interest in the workshop .
• CV in PDF format (optional).
• Contact information for one faculty member who could speak to how attendance will benefit you. (We will only contact this person if we need more information.)
• Type/amount of support you will need.

Presented in association with the Special Focus on Fine-grained Complexity.