« search calendars

« DIMACS Tutorial on Fine-grained Complexity

DIMACS Tutorial on Fine-grained Complexity

July 15, 2024 - July 19, 2024

Location:

Rutgers Academic Building, Room 4225 (East Wing)

Rutgers University

College Avenue Campus

15 Seminary Place

New Brunswick, NJ 08901

Click here for map.

Organizer(s):

Amir Abboud, Weizmann Institute of Science

Karthik C.S., Rutgers University

Nick Fischer, Weizmann Institute of Science

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

 

Monday, July 15, 2024

8:00 AM - 9:00 AM

Registration - Coffee and light breakfast (provided)

9:00 AM - 10:00 AM

Lecture 1 - Introduction to Fine-Grained Complexity

Amir Abboud, Weizmann Institute of Science

10:00 AM - 10:10 AM

Break

10:10 AM - 11:00 AM

Lecture 2: 3SUM Hypothesis and Equivalent Formulations

Amir Abboud, Weizmann Institute of Science

11:00 AM - 12:30 PM
12:30 PM - 2:30 PM

Lunch (on your own -- not provided)

2:30 PM - 4:00 PM

Problem Solving Session

4:00 PM - 4:30 PM

Coffee Break (provided)

4:30 PM - 5:10 PM

Bird's View Lecture 1: 3SUM-Hardness of Geometric Problems

Nick Fischer, Weizmann Institute of Science

5:10 PM - 5:15 PM

End of Day 1

 

Tuesday, July 16, 2024

8:30 AM - 9:00 AM

Coffee and Light Breakfast (provided)

9:00 AM - 10:00 AM

Lecture 4: APSP Hypothesis

Nick Fischer, Weizmann Institute of Science

10:00 AM - 10:10 AM

Break

10:10 AM - 11:00 AM

Lecture 5: APSP-Hardness of Negative Triangle Detection

Nick Fischer, Weizmann Institute of Science

11:00 AM - 11:10 AM

Break

11:10 AM - 12:00 PM

Lecture 6: APSP-Hardness of Zero Triangle

Amir Abboud, Weizmann Institute of Science

12:00 PM - 2:00 PM

Lunch (On your own - not provided)

2:00 PM - 3:30 PM

Problem Solving Session

3:30 PM - 4:00 PM

Coffee Break (provided)

4:00 PM - 4:40 PM

Bird's View Lecture 2: APMF vs. APSP

Amir Abboud, Weizmann Institute of Science

4:40 PM - 4:45 PM

End of Day 2

 

Wednesday, July 17, 2024

8:30 AM - 9:00 AM

Coffee and Light Breakfast (provided)

9:00 AM - 10:00 AM

Lecture 7: Algorithms for k-SAT

Nick Fischer, Weizmann Institute of Science

10:00 AM - 10:10 AM

Break

10:10 AM - 11:00 AM

Lecture 8: Lower Bounds under ETH and SETH

Amir Abboud, Weizmann Institute of Science

11:00 AM - 11:10 AM

Break

11:10 AM - 12:00 PM

Lecture 9: Orthogonal Vectors Hypothesis

Amir Abboud, Weizmann Institute of Science

12:00 PM - 2:00 PM

Lunch (On your own - not provided)

2:00 PM - 3:30 PM

Problem Solving Session

3:30 PM - 4:00 PM

Coffee Break (provided)

4:00 PM - 4:40 PM
4:40 PM - 4:45 PM

End of Day 3

 

Thursday, July 18, 2024

8:30 AM - 9:00 AM

Coffee and Light Breakfast (provided)

9:00 AM - 10:00 AM

Lecture 10: SETH-Hardness of LCS

Amir Abboud, Weizmann Institute of Science

10:00 AM - 10:10 AM

Break

10:10 AM - 11:00 AM

Lecture 11: Hardness of Approximation in P, Part 1

Nick Fischer, Weizmann Institute of Science

11:00 AM - 11:10 AM

Break

11:10 AM - 12:00 PM

Lecture 12: Hardness of Approximation in P, Part 2

Nick Fischer, Weizmann Institute of Science

12:00 PM - 2:00 PM

Lunch (On your own - not provided)

2:00 PM - 3:30 PM

Problem Solving Session

3:30 PM - 4:00 PM

Coffee Break (provided)

4:00 PM - 4:40 PM

Bird's View Lecture 4: Barriers for Fine-Grained Reductions

Nick Fischer, Weizmann Institute of Science

4:40 PM - 4:45 PM

End of Day 4

 

Friday, July 19, 2024

8:30 AM - 9:00 AM

Coffee and Light Breakfast (provided)

9:00 AM - 10:00 AM

Lecture 13: Recent Developments in Fine-Grained Complexity

Amir Abboud, Weizmann Institute of Science

10:00 AM - 10:10 AM

Break

10:10 AM - 12:00 PM

Problem Solving Session

12:00 PM - 2:00 PM

Lunch (On your own - not provided)

2:00 PM - 3:00 PM

Office Hours

3:00 PM - 3:05 PM

End of Tutorial

 

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].

 

When you are ready to start your application, click on the "Registration" button below.

 

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. College Avenue Campus Map

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).