CS 599: The Meta-Complexity Frontier, Fall 2023

Complexity theory studies the cost of solving computational problems using various resources such as time, space, and logic gates. Even after decades of effort, there is a huge gap between what we conjecture about the limits of efficient computation and what we can actually prove. For example, it appears that deciding if a string is "compressible" (MCSP) requires brute-force search, but we cannot (yet) prove this.

This class covers classical and recent "barrier" theorems that explain why it is so difficult to prove lower bounds for computational resource costs. Then, we study emerging connections between meta-mathematics of complexity (provability of theorems) and meta-computational problems like MCSP (existence of algorithms). These modern results offer tantalizing "magnification conditions" — seemingly weak conjectures that, if proven, would immediately imply breakthroughs in complexity theory.

We will explore the inherent tension: either complexity breakthroughs are much closer than they appear or even "weak" lower bounds are inherently difficult to prove. This will prepare students to articulate and work at the research frontier in (meta-)complexity.

Logistics

Instructor

Marco Carmosino

Email

marco [at] ntime [dot] org

Class Times

Tue, Thu 9:30 – 10:45AM (CGS 115)

Office Hours

11AM Every Friday CDS Room 926

Website

https://mcsp.work/MCF2023/

Syllabus

Prerequisites

The formal prerequisite is CS 332 (Theory of Computation) or a similar rigorous undergraduate introduction to the theory of computation. In reality, this is a proxy for the following background: Strong undergraduate-level preparation in math (combinatorics, discrete probability, graph theory, and logic), algorithms (asymptotic notation, running time analysis, graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming), and theory of computation (Turing machines, decidability, P, NP, reductions). Aside from this background, it's important to have "mathematical maturity": Comfort with mathematical abstraction, a solid understanding of basic combinatorics and discrete probability, and the ability to read, understand, and write mathematical proofs. Please talk to me if you are missing any of this preparation.

Topics

Our syllabus is based on the Spring 2023 Meta-Complexity program at the Simons Institute. We cover necessary background and some "spotlight" results from the program. Topics are arranged into three phases, reflecting an evolving technical perspective on meta-complexity.

1. Classical Barrier Results: Relativization, Algebrization, and Natural Proofs. Each barrier will be presented by proving a canonical lower bound and asking if the underlying technique can be extended to prove breakthrough results in complexity theory. The answer in each case is "no" and an appropriate barrier will allow us to understand why. We conclude this phase with Natural Proofs, prompting the question: how "constructive" should we expect the proofs of complexity separations to be?

2. Algorithmic Aspects of Complexity Separations: Pseudorandomness, Minimum Circuit Size Problem (MCSP), and Efficient Refutation. There are many ways to formalize a "constructive" separation of complexity classes. We establish the computational utility of a variety of constructive separation notions, relating them to key tasks in learning and cryptography. We show that even conditional hardness results for some of these "meta-complexity" problems would immediately imply breakthrough complexity separations. This phase concludes by observing that the results here do not answer our original question: we formalized constructive separations but not constructive proofs.

3. Constructive Meta-Mathematics of Computational Complexity: Proof Theory. The "gold standard" for no-go results in mathematics is formal independence from logical theories. Can we sharpen our barriers and notions of constructivity to meet this standard? Partially — this is an active and exciting area of research. We will cover classical results about the logical independence of P vs NP and the basics of bounded arithmetic, concluding with open problems and recent results along these lines.

Running Schedule

Resources

Background Course Notes

• Local Complexity Zoo

Required Textbook

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. ISBN-13: 978-0521424264.

Video Lectures

• MCSP and Hardness Magnification (Workshop, STOC 2020)
• Meta-Complexity Boot Camp, Simons Institute 2023

Journalism & Popular Media

• Complexity Theory’s 50-Year Journey to the Limits of Knowledge (Quanta, 2023)
• Alan Turing and the Power of Negative Thinking (Quanta, 2023)
• Researchers Identify ‘Master Problem’ Underlying All Cryptography (Quanta, 2022)
• Which Computational Universe Do We Live In? (Quanta, 2022)

Evaluation

There are three components of your participation in the course.

Homework (45%)

I expect to give three homework assignments and will post them below when they are available. You may work on these with other students in the class as long as you write up the solutions on your own and acknowledge your collaborators and any outside sources.

• Problem Set 1
• Problem Set 2
• Problem Set 3

Research Presentation (20%) and Project (25%)

Choose a paper, prepare a set of lecture notes, and present the paper to the class. Then expand on those notes by either a) trying your hand at some of the open problems suggested by the paper you've chosen or b) surveying additional related work to provide a more comprehensive context for it. You may work on your presentation and project either individually or in pairs. (Pairs may be allocated more time for their presentation and will be expected to complete more ambitious projects.)

Project Description and Topic Suggestions — More Topics TBA

Class Participation (10%)

Your active participation during class meetings will make it much more enjoyable for you (and for me!). You can also earn participation credit by commenting on Zulip or attending office hours. I may also pose short "reading response" prompts that are meant to guide you through the reading; these should be answered by email before the start of the next class period. Midway through the semester, I will send you indication of how your participation in class is going.

Course Policies

Academic Conduct

All Boston University students are expected to maintain high standards of academic honesty and integrity. It is your responsibility to be familiar with the Academic Conduct Code, which describes the ethical standards to which BU students are expected to adhere and students’ rights and responsibilities as members of BU’s learning community. All instances of cheating, plagiarism, and other forms of academic misconduct will be addressed in accordance with this policy. Penalties for academic misconduct can range from failing an assignment or course to suspension or expulsion from the university.

https://www.bu.edu/academics/policies/academic-conduct-code/

http://www.bu.edu/cas/current-students/phd-mfa-students/academic-policies-and-conduct-code/

Attendance Policy

Students are expected to attend each class session unless they have a valid reason for being absent. If you must miss class due to illness or another reason, please notify the instructor as soon as possible, ideally before the absence.

https://www.bu.edu/academics/policies/attendance/

Absence Due to Religious Observance

If you must miss class due to religious observance, you will not be penalized for that absence and you will receive a reasonable opportunity to make up any work or examinations that you may miss. Please notify the instructor of absences for religious observance as soon as possible, ideally before the absence.

https://www.bu.edu/academics/policies/absence-for-religious-reasons/

Bereavement

In the event of the death of an immediate family member, you should notify your advisor, who will help you coordinate your leave. You will be automatically granted five weekdays of leave, and if necessary, you advisor will help you to petition the Dean for additional leave time. You may also request a leave of absence due to bereavement. Please contact your advisor, who will help you with the process.

https://www.bu.edu/academics/policies/student-bereavement/

Disability Services

Students with documented disabilities, including learning disabilities, may be entitled to accommodations intended to ensure that they have integrated and equal access to the academic, social, cultural, and recreational programs the university offers. Accommodations may include, but are not limited to, additional time on tests, staggered homework assignments, note-taking assistance. If you believe you should receive accommodations, please contact the Office of Disability Services to discuss your situation. This office can give you a letter that you can share with instructors of your classes outlining the accommodations you should receive. The letter will not contain any information about the reason for the accommodations.

If you already have a letter of accommodation, you are encouraged to share it with your instructor as soon as possible.

Disability & Access Services
25 Buick Street, Suite 300
617-353-3658

access@bu.edu

http://www.bu.edu/disability/

Grade Grievances

If you feel that you have received an arbitrary grade in a course, you should attempt to meet with the grader before filing a formal appeal. If the student and the instructor are unable to arrive at a mutually agreeable solution, the student may file a formal appeal with the chair. This process must begin within six weeks of the grade posting. To understand how an “arbitrary grade” is defined, please explore the following link.

https://www.bu.edu/academics/policies/policy-on-grade-grievances-for-undergraduate-students-in-boston-university-courses/

Incomplete Grades

An incomplete grade (I) is used only when the student has conferred with the instructor prior to the submission of grades and offered acceptable reasons for the incomplete work. If you wish to take an incomplete in this class, please contact the instructor as soon as possible but certainly before the submission of final grades. To receive an incomplete, you and your instructor must both sign an “Incomplete Grade Report” specifying the terms under which you will complete the class.

https://www.bu.edu/academics/policies/incomplete-coursework/

Student Health Services

Offers an array of health services to students, including wellness education and mental health services (behavioral medicine).

http://www.bu.edu/shs/

http://www.bu.edu/shs/wellness/

http://www.bu.edu/shs/behavioral/index.shtml

Medical Leave of Absence

If you must take a leave of absence for medical reasons and are seeking to re-enroll, documentation must be provided to Student Health Services so that you may re-enroll. To take a medical leave, please talk with SHS and your advisor, so that they may assist you in taking the best course of action for a successful return.

http://www.bu.edu/usc/leaveandwithdrawal/arranging/

http://www.bu.edu/academics/policies/withdrawal-leave-of-absence-and-reinstatement/

ISSO

The International Students & Scholars Office is committed to helping international students integrate into the Boston University community, as well as answering and questions and facilitating any inquiries about documentation and visas.

https://www.bu.edu/isso/