Organizer(s):

Amir Abboud, Weizmann Institute of Science

Karthik C.S., Rutgers University

Nick Fischer, Weizmann Institute of Science

Description

Note: The size of this event and the support available to attend it are contingent on receipt of external funds, but the event will be held in any case.

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

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

Code of Conduct