Organizer(s):

Lijie Chen, University of California, Berkeley

Roei Tell, University of Toronto

Ryan Williams, Massachusetts Institute of Technology

Description

This summer DIMACS will hold an advanced workshop for graduate students in complexity theory! Our goal is to bring together up-and-coming complexity researchers and introduce them to some recent exciting lines of research in the field.

Workshop attendance does not require specific prior knowledge, beyond interest in complexity theory and mathematical maturity. In particular, the workshop is also open to strong students working in other areas of theoretical computer science who are interested in learning more about recent complexity research. Strong undergraduate students may also be considered.

Some of the exciting features of the workshop include:

• Keynote lectures by Avi Wigderson (IAS) and Ryan Williams (MIT)
• Four tutorial-style lecture series*, each of which will assume very little prior knowledge but will reach recent exciting developments:
  1. Meta-complexity, taught by Rahul Ilango (MIT)
  2. Error-correcting codes, taught by Swastik Kopparty (U Toronto)
  3. Algebraic complexity, taught by Nutan Limaye (IT University of Copenhagen)
  4. Derandomization, taught by Roei Tell (U Toronto)

     
     *Some tutorials will be held in parallel, and therefore students will be able to attend two of the four tutorials: one from the set { Meta-complexity, Error-correcting codes}, and one from the set { Algebraic complexity, Derandomization }. (see tutorial descriptions below)

• A presentation of the new C^3 locally testable code, by Lijie Chen (UC Berkeley)

There will also be small-group discussions, social events, and more!

Tutorial Descriptions:

• Meta-complexity, taught by Rahul Ilango (MIT)
  In this tutorial we will give an introduction to the area of metacomplexity. No prior background is assumed, and we will start with an overview of the major themes in metacomplexity. Our main goal is to build towards Hirahara's recent breakthrough showing that "Partial-MCSP is NP-hard" (you do not need to know what this means yet). Along the way, we will encounter important tools from the various areas of theoretical computer science that should be of broad interest (e.g.  secret sharing, reconstructive extractors, the PCP theorem, and more!).
   
• Error-correcting codes, taught by Swastik Kopparty (U Toronto)
  We will start with a quick introduction to codes and some central algebraic and combinatorial families of error-correcting codes. Then we will get a taste of codes and algorithms supporting more exotic error-correcting phenomena, such as local decoding, local testing, list decoding and more.
   
• Algebraic complexity, taught by Nutan Limaye (IT University of Copenhagen)
  In this tutorial on Algebraic Complexity, we will start by introducing the basics of algebraic computation. We will present the broad research themes being explored actively in this research area. We will study the techniques used in proving the recent state-of-the-art lower bounds for constant-depth algebraic circuits. In fact, we will also study all the proof details! We will end with some promising future research directions.
   
• Derandomization, taught by Roei Tell (U Toronto)
  The focus of this tutorial is derandomization, and in particular new developments in hardness vs randomness. We will first introduce textbook results, such as the reconstructive paradigm (Nisan-Wigderson, Impagliazzo-Wigderson) and hardness amplification. Then we will study new tools in this area from recent years, focused on constructions of targeted pseudorandom generators from functions hard for uniform algorithms. We'll conclude with very recent applications -- in particular, we will see the construction of a pseudodeterministic polynomial-time algorithm that finds prime numbers!

Videos

• View full video playlist
• Metacomplexity (Rahul Ilango) [part 1]  [part 2]  [part 3]  [recap]
• Error-correcting codes (Swastik Kopparty) [part1]  [part 2]  [part 3]
• Algebraic complixity (Nutan Limaye) [part1]  [part 2]  [part 3]
• Derandomization (Roei Tell) [part1]  [part 2]  [part 3]
• C^3 Locally Testable Codes (Lijie Chen) [video]
• Circuit Complexity from Circuit Analysis Algorithms (Keynote by Ryan Williams) [video]

Program

Monday, July 29, 2024

Tuesday, July 30, 2024

Wednesday, July 31, 2024

Thursday, August 1, 2024

Call For Participation

Attendance at the workshop is by application. The workshop is intended primarily for graduate students working in complexity theory. Applications from strong graduate students working in theoretical computer science (in general) will also be considered, as well as motivated undergraduate students interested in complexity.

We especially encourage diverse and inclusive participation, and will give special consideration to applications from students belonging to underrepresented groups in theoretical computer science. If you feel that this applies to you, we encourage you to let us know that in your application.

Support: Breakfast and lunch will be provided each day. Non-local participants will be offered shared lodging at a hotel in New Brunswick, NJ. Additional travel support will unfortunately be extremely limited.

To be able to attend: Please 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 May 19, 2024.

What information do I need to provide in the application? Here are some of the things we ask for:

• A short statement of interest (~2 paragraphs) telling us why you're interested in the workshop and how you feel it can be beneficial for you.
• CV (in PDF format).
• The name of a faculty member who will provide a recommendation for you. Letters should be sent by the recommender to: complexityWS@dimacs.rutgers.edu. (The recommender should send the letter directly, as they will not receive an email requesting one.)
• If travel support is necessary for your attendance, there will be a place for you to indicate this in the application. (We will do our best to consider it, but do recall that travel support is very limited).

This workshop is supported by the National Science Foundation under grant number CCF-2435051 and grant number CCF-1836666.

Presented in association with the Special Focus on Lower Bounds in Computational Complexity.