CAS CS 591, Spring 2020

Recent results and new methods in computation theory

Steve Homer , homer@bu.edu

Office hours in Room 226 of MCS: Tuesday, 3:30 -4:30, Thursday, 12:30-1:45 and by appointment (just send me an email, or call 617-353-8927 (office))

Class Schedule

Tue,Thur 2:00-3:15 in room 102 of KCB (Kenmore classroom building)

Here is a schedule of the class speakers and dates , a list of topics we will be talking about in class and the order in which they will be discussed.

Here is a list of recent recordings of CS 591 lectures made since spring break by Zoom.

Some specific references and papers we may cover and discuss can be found here.

Topics

This class will study several areas of theoretical science where there are interesting, consequential open problems and where there has been some recent progress or new advances in techniques related to their solution. We will choose a few of these areas to read about and study, read papers where the problems were first examined, look at what progress has been made, and view potential future promising directions of study. Some time will be spent during the first weeks of class looking at specific problems of active interest and grouping them into a few areas of broader concern.

We will try to pick problems from three or four different areas of current interest and try to form a few cohesive topics which tell a clear story in each area. Some of these topics will be foundational and possibly require knowledge of old and well developed techniques. Others may be more current and center on new methods to approach hard problems. Several of the new approaches may use different, new models of computation to our advantage, or different computational paradigms to circumvent some past barriers to progress. These include automatically accelerating computation, parameterized complexity, mixed mode quantum computing, deriving lower bounds for problems using algorithmic upper bounds, uses of limited non-determinism, and others.

Some suggested possible initial topics are:

-Concrete or fine-grained complexity of problems.

-Using upper bounds to conclude lower bounds.

-Using efficient exponential algorithms to solve hard problems.

-New models of computations and techniques of speeding up classes of computations.

using parallel algorithms to speed up computation of hard problems using parallel algorithms

-Classical problems concerning circuit complexity or the complexity of Boolean functions

-Approximation algorithms using fixed parameter tractibility or parallelism to carry out the approximation.

-Quantum computing/quantum circuits/quantum speed-up

-Lower bound for hard problems and their current limits.

-Approximation algorithms using fixed parameter tractibility or parallelism to carry out the approximation.

Some specific references and papers we may cover and discuss can be found here.

Plan

The class is a graduate level seminar and students will take turns presenting papers and leading the class discussions. Each participant is expected to lead one week of the class discussion by summarizing a paper or two and promoting discussion with questions and observations based on the paper. The leader should explain and present enough background on the problem area to motivate the problem and the new results. Each week we will be cover one or two research papers, and all will be expected to read, review and discuss them. These papers will likely require that you find and read additional material as necessary to ensure your comprehension. Do not underestimate the amount of work this can be.

Shortly after leading the discussion, you will be required to submit a written review of the papers presented in your class presentation. These notes can take different forms but should include the main motivation and the ideas/results from the core papers and and bibliography of the papers read. Everyone will also be expected to actively participate in the in class discussion.

Prerequisites: This class is mainly intended for PhD students. Any MS or undergraduate students need to have taken a theory of computation course which covers the basic topics of complexity theory, for example CS 332 or CS 535 at BU. Also highly recommended is a strong, general graduate algorithms class, for example CS 530 at BU. A grade of B+ or better is expected in these classes. Exceptions can be made with the approval of the instructor.

Grading: Students will be graded on the quality of their lectures, the write-up of their topics, and their attendance and participation in the classes. Where good effort is made I expect to give good grades.

CS 591 Short Complexity Bibliography - SPRING - 2020

Recommended Texts

P, NP, and NP-Completeness: The Basics of Complexity Theory By Oded Goldreich, Cambridge University Press.

Sipser, M. Introduction to the Theory of Computation,PSW Publishing Company, Boston 1997. Third edition.

Homer, S., Selman A. Computability and Complexity Theory, Spring-Verlag New York 2001.

Garey, M., and Johnson, D. Computers and Intractability: A Guide to NP-Completeness, Freeman Press.

Papadimitriou, C. Computational Complexity Addison-Wesley Publishing Company, Reading 1994.

Lewis, H., Papadimitriou, C. Elements of the Theory of Computation, second edition, Prentice-Hall 1998

Computational Complexity: A Modern Approach 1st Edition, by Sanjeev Arora and Boaz Barak, Cambridge University Press.

The Nature of Computation 1st Edition by Cristopher Moore (Author), Stephan Mertens, Oxford Press.

A few links to some complexity course pages and notes

Professor Levin's Fundamentals of Computing

Notes and papers on complexity theory from Professor Jin-Yi Cai of Wisconsin.

Notes from the Weizmann Institute by Oded Goldreich.