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.

Update (April 30, 2025): We received quite a few applications for support before the April 15 deadline and have closed collection of additional applications.

Local Information

Conference Venue: The Tutorial will be held room 4225 (East Wing) of the Rutgers Academic Building located at 15 Seminary Place, New Brunswick, NJ. This is on the College Avenue Campus of Rutgers University.  If you click the map, it will show some of the key locations for the event. 

Parking: If you do not have a Rutgers parking permit and you plan to drive to the workshop, there will be free parking in Lots 26 and 30 on the College Avenue Campus, but you must register your car to park. A link to register for parking will be provided in the confirmation message you receive when you register for the workshop.

Dining in New Brunswick: New Brunswick has a wide variety of dining options to fit all budgets. Many are within an easy walk of the conference venue and the New Brunswick hotels (Heldrich and Hyatt).

• Dining options: Here are a few options.

• Lunch options: Here is a list of quickish lunch options near the lecture venue grouped by location, with an associated map.

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