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

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.

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.

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

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.

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

*
*

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

*
*