Organizer(s):

Amir Abboud, Weizmann Institute of Science

Karthik C.S., Rutgers University

Nick Fischer, Weizmann Institute of Science

Description

A traditional goal of complexity theory is to distinguish between problems that are computationally tractable and those that are not. The tractable, so-called “easy”, problems are solvable in polynomial time and form the complexity class P. From a practical standpoint, however, even problems solvable in cubic or quadratic time may be impossible when the input data is large enough. As problem sizes have grown, the need for a more nuanced understanding of the complexity of problems in
P gave rise to the relatively new field of fine-grained complexity.

Fine-grained complexity seeks to better-understand the complexity of problems in P. The central idea is to investigate relationships between different problems using fine-grained reductions, that not only preserve the worst-case running time but also the dependence on various parameters, such as input size, dimensionality, and sparsity. Such reductions enable more precise comparison of the relative difficulty of different problems, even when they have similar worst-case running times.

This tutorial will cover key concepts in fine-grained complexity. It will be taught at a beginning graduate school level and be based on courses on fine-grained complexity currently offered at only a few top universities. It will cover:

• The main conjectured-to-be-hard problems, what we know about them algorithmically, and how to reduce them to other problems. These problems include: k-SAT, 3-SUM, All-Pairs Shortest Paths, and k-Clique.
• Various examples of fine-grained results for important problems on strings (e.g. Edit-Distance), graphs (e.g. Diameter), and geometric data (e.g. Closest Pair).
• Other topics such as hardness of approximation and barriers for reductions.
• Research directions and open questions that are currently driving research in the field.

The format of the tutorial will include a mix of whiteboard technical lectures, presentations with slides surveying certain topics, materials and references that students may explore on their own, and problem-solving sessions.

The desired learning outcomes are:

• Ability to prove whether or not a problem is solvable in near-linear time. Whereas a basic course in complexity theory provides the students with tools to prove whether a problem that they encounter is in P or not (assuming P is not equal to NP), this tutorial provides the tools to prove whether a problem is solvable in near-linear time or not (assuming certain conjectures).
• Familiarity with the most basic computational problems that are not known to be solvable in near-linear time.
• Ability to understand state-of-the-art research in fine-grained complexity.

Featured Lecturers:

• Amir Abboud, Senior Scientist, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science
• Nick Fischer, Postdoctoral Fellow, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science

Lecture materials: The links in the Program will take you to the slides for individual presentations. Alternatively, you can visit the Materials webpage for the Tutorial, which contains links to both lectures and exercises.

Exercise sheets:  [Prep sheet]  [3SUM]  [APSP]  [SETH]  [FGC in action]  [Miscellaneous]

Full video playlist

Code of Conduct

Program

Monday, July 15, 2024

Tuesday, July 16, 2024

Wednesday, July 17, 2024

Thursday, July 18, 2024

Friday, July 19, 2024

Call For Participation

Who may attend? The tutorial is designed for graduate students working on topics in and around theoretical computer science (TCS) who are not already familiar with fine-grained complexity. Students falling into this category will be prioritized for both attendance and support. Recent Ph.D.'s and advanced undergraduates may also apply, but we will try to accommodate graduate students first. 

We especially encourage diverse and inclusive participation and will give special consideration to applications from students belonging to underrepresented groups in computer science. We will also prioritize students who do not have access to an expert in fine-grained complexity at their institution and students working in other areas of TCS (i.e. not fine-grained complexity) who want to incorporate the fine-grained lens into their research. If any of these apply, be sure to let us know in your application.

To be able to attend, you must complete and submit this application form. Based on the material provided in your application, you will be notified of whether you have been selected. For full consideration, please apply before March 25, 2024. If you will need to apply for a visa you should apply as soon as you can, and we will try to expedite decisions. Update April 2, 2024: Applications are now closed.

Prerequisites: No prior knowledge of fine-grained complexity is assumed or needed, but we will assume comfort with mathematical proofs, algorithmic concepts, and NP-completeness. As such, a background in algorithms and in complexity theory at a beginning graduate-school level is desirable.

What information do I need to provide in the application? If you are ready to apply, Here are some things we will ask for:

• A short statement (one paragraph) that tells us about your research interests and why you think the course will be beneficial to you.
• CV (in PDF format).
• Contact information for a faculty member who has agreed to provide a recommendation for you. (You may optionally include a second, but this is not required.) Letters should be sent by the recommender to: fine-grained-complexity@dimacs.rutgers.edu. (The recommender should send the letter directly, as they will not receive an email requesting one.)
• Amount of support you will need to attend.

Is travel support available? Yes, but the availability of travel support is somewhat dependent on our ability to obtain external funding. We expect to have limited funds available to support lodging for some attendees and hope to also be able to support travel for some. The application includes a section related to support needs. If you are requesting travel support, please do not book your tickets until you hear from us!

Should I apply even if my ability to attend depends on travel support? Yes, absolutely! The application will allow you to tell us what support you need.

Am I less likely to be selected if I need support? No. Selection decisions will be independent of support. We will let you know how much support we will be able to provide when you are notified of selection.

Download (and share) the Call for Applications: [PDF].

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.

Sponsored by Institute for Computer Science, Artificial Intelligence and Technology (INSAIT), in association with the Special Focus on Fine-grained Complexity.