MIT // The Algorithms Group at CSAIL

6.042J/ 18.042J Mathematics for Computer Science

Teacher: Profs. Tom Leighton & Ronitt Rubinfeld

Meeting Time: TR2.30-4 in 34-101

Brief Description: Mathematical tools and methods for computer science and engineering. Emphasis on development of rigorous thinking, analytical skills, and mathematical sophistication while learning elementary discrete mathematics. Topics: mathematical proofs; induction and well-ordering; divisibility and congruences; asymptotic notation and growth of functions; sets, relations, functions, and graphs; counting theory; recurrences and generating functions; and discrete probability.

URL: http://theory.lcs.mit.edu/classes/6.042/

6.046J/ 18.410J Introduction to Algorithms

Teacher: Profs. Erik Demaine & Madhu Sudan

Meeting Time: MW9.30-11 in 4-270

Brief Description: Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

URL: http://theory.lcs.mit.edu/classes/6.046

6.895 Randomness and Computation

Teacher: Prof. Ronitt Rubinfeld

Meeting Time: TBA

Brief Description:

The power and sources of randomness in computation. Topics include:
(1) Basic tools: polynomial zero testing, linearity testing, uniform generation and approximate counting, the influence of variables.
(2) Randomness in various computational settings: computational learning theory, communication complexity, probabilistic proofs.
(3) Generating randomness: pseudorandom generators, derandomization, expanders, extractors.

prerequisites: 6.046, 6.840 3-0-9 H Level Credit

URL: http://theory.lcs.mit.edu/~ronitt/COURSE/S06/index.html

18.409/ 6.443J Topics in Theoretical Computer Science

Teacher: Profs. Peter Shor and Ike Chuang

Meeting Time: TBA

Brief Description: Advanced graduate course on quantum computation and quantum information. The first semester of this two-course sequence (2.111/18.435J) was taught by Seth Lloyd in Fall of 2005. This semester, we will cover models of quantum computation, advanced quantum error correction codes, fault tolerance, quantum algorithms beyond factoring, properties of quantum entanglement, and quantum protocols and communication complexity.

URL: TBA

6.885 Distributed Algorithms for Mobile Wireless Ad Hoc Networks (H)

Teacher: Prof. Nancy Lynch

Meeting Time: TBA

Brief Description:

This subject qualifies as a Theoretical Computer Science Engineering Concentration subject. This course will cover distributed algorithms for mobile (and some non-mobile) wireless ad hoc networks, including those with interesting interactions with the real world. Focusing on algorithms that can be described precisely, and that have relatively well-defined correctness, fault-tolerance, and performance requirements. Aiming to understand the existing theory of wireless network algorithms and contribute to its further development. Thus, we would like to:
1. Understand the nature of wireless ad hoc network settings. What are typical correctness, reliability, and performance properties that can be assumed? What are the ``right'' complexity measures to use for evaluating algorithms?
2. Identify important, well-defined problems and subproblems that must be solved by distributed algorithms in wireless ad hoc networks. These will include problems of low-level and higher-level communication, time synchronization, localization, network configuration, resource allocation, tracking, and data management.
3. Learn about the most important existing algorithms for many of these problems, and identify places where additional algorithmic work is needed.
4. Identify some inherent limitations (lower bound and other impossibility results) on the solvability of problems in wireless networks.
5. Identify useful abstraction layers for programming wireless networks.
The course will involve reading a series of recent research papers, proceeding roughly from lower to higher layers in the ``protocol stack'': MAC layer: Collision avoidance, backoff strategies; Collision detection. Local infrastructure: Local consensus, leader election; Local reliable broadcast, replicated state machines; Localization; Time synchronization. Broadcast Point-to-point routing Location-based communication services: Location services; Geographical routing. Global infrastructure: Power-aware topology control; Clustering; Maximal independent set, spanning trees. Middleware services: Mutual exclusion, resource allocation; Token circulation; Group membership, group communication; Synchronization, consensus. Virtual node layers. Applications: Data aggregation; Implementing shared memory; Tracking; Robot motion coordination.

Prereq.: 6.046, 6.033, 6.852 or equivalent of each
3-0-9

URL: TBA

6.338J/18.337J Applied Parallel Computing

Teacher: Prof. Alan Edelman

Meeting Time:

TBA

Brief Description:

NOTE: The class this year will be involved in a supercomputing productivity study.

Advanced interdisciplinary introduction to applied parallel computing on modern supercomputers. Numerical topics include dense and sparse linear algebra, N-body problems, multigrid, fast-multipole, wavelets and Fourier transforms. Geometrical topics include partitioning and mesh generation. Other topics include applications oriented architecture, software systems, MPI, Cilk, data parallel systems, Parallel MATLAB, caches and vector processors with hands-on emphasis on understanding the realities and myths of what is possible on the world's fastest machines.

URL:

6.857 Computer and Network Security

URL: http://stellar.mit.edu/S/course/6/fa05/6.857/index.html

18.338J/ 16.394J The Mathematics and Applications of Infinite Random Matrices

Teacher: Prof. Alan Edelman and Prof. Moe Win

Meeting Time: TBA

Brief Description:

The focus of this semester will be on the mathematics of infinite random matrices.
We will learn about the tools such as the Stieltjes transform, and Free Probability used to characterize infinite random matrices.

Our emphasis will be on exploring known connections between these tools (such as the combinatorial aspects of free probability) and discovering new connnections (such as between multivariate orthogonal polynomials and free cumulants of free probability).

We will also discuss applications of these techniques to problems in engineering and statistical physics.

Additional topics will be decided based on the interests of the students. No particular prerequisites are needed though a proficiency in linear algebra and basic probability will be assumed. A familiarity with MATLAB will also be useful.

URL: http://web.mit.edu/18.338/www/

6.876/18.426 Cryptographic Game Theory

Teacher: Prof. Silvio Micali

Meeting Time: TBA

Brief Description: Mutually suspicious individuals with different and even conflicting goals often wish or need to cooperate towards a common goal. Can such cooperation succeed? What should such a success mean? Cryptographic Protocols and Game Theory provide different answers to these important questions, have developed different models, and forged different sets of working tools. This course aims at bridging these two approaches in a systematic way, and gain a new understanding of human interactions. The benefit of a unified approach, or at least one cognizant of the conceptualizations and techniques of both sides, is potentially enormous. (So even a modest success would be great!)

We start by reviewing fundamental notions and results of both fields, and then proceed to open a new approach to "champion problems" such as reaching correlated equilibrium and mechanism design. Topics include:

• Zero-knowledge Proofs
• Secure Function Evaluation
• Complete-Information Games and Equilibria
• Incomplete-Information Games and Sequential Reasoning
• Concurrency and Security
• Signaling and Security
• Collusion-free Security
• Correlated Equilibria via Extended Games
• Ideal Mechanism Design
• Rational Secure Computation

This is an experimental course, and active participation is essential. No prerequisites beyond basic efficient algorithms and Theory of Computation ---though some knowledge of Cryptography (e.g., 6.875) or Game Theory (e.g., 6.972 or 14.122) would be very useful.

URL:

6.885 Algebra and Computation

Teacher: Prof. Madhu Sudan

Meeting Time: TBA

Brief Description:

This course studies the interplay between algebra and computation. The course will be divided in two parts.

* The first part will cover algorithms in Algebra, Number Theory, and Group Theory. Some topics include algorithms for factoring polynomials (Berlekamp, Lenstra-Lenstra-Lovasz etc.) and algorithms for testing primes (Agarwal-Kayal-Saxena), multiplying matrices (Cohn-Umans), Solving systems of polynomial equations etc.

* The second part of the course will focus on the interplay between complexity theory and algebra as highlighted by algebraic versions of the P vs. NP question.

See http://theory.csail.mit.edu/~madhu/FT98 for notes from an earlier version of this course. Prereq: 6.840 + 6.046 + 18.703

URL: http://theory.csail.mit.edu/~madhu/FT05/

6.896 Sublinear time Algorithms

Teacher: Prof. Ronnitt Rubinfeld

Meeting Time: TBA

Brief Description:

We focus on the design of algorithms that are restricted
to run in sublinear time, and thus can view only a very
small portion of the data. The study of sublinear time
algorithms has been applied to problems from a wide range
of areas, including algebra, graph theory, geometry, string
and set operations, optimization and probability theory.
This course will introduce many of the various techniques
that have been applied to analyzing such algorithms.

URL: http://theory.lcs.mit.edu/~ronitt/COURSE/FT04/index.html

6.895 Essential Coding Theory

Teacher: Prof. Madhu Sudan

Meeting Time: TBA

Brief Description: Mathematical introduction to the topic of error-correcting codes. Course covers basic definitions, constructions, impossibility
results, and algorithms for using error-correcting codes. We will also study some applications of coding to computer science. Techniques used in the course include probability theory, linear algebra, and finite field algebra. Course will be self-contained though some knowledge of basic probability (6.041/6.042) and linear algebra would help.

URL: http://theory.csail.mit.edu/~madhu/FT04

6.885: Folding and Unfolding in Computational Geometry

Teacher: Prof. Erik Demaine

Meeting Time: TBA

Brief Description: Folding offers a wealth of beautiful geometric and algorithmic problems. Recent results in this area have lead, for example, to powerful techniques for complex origami design. Other problems relate to how to fold robotic arms without collision, how to bend sheet metal into desired 3D shapes, and understanding protein folding. Despite much recent progress on folding problems, some of the most fundamental questions remain tantalizingly unsolved. This class covers the state-of-the-art in folding research, including a variety of open problems, enabling the student to do research and advance the field. The class will include guest lectures from visiting experts.

I will also organize an optional problem-solving session, during which we can jointly try to solve open problems in folding. Results from this session would likely lead to class projects, and hopefully also paper submissions, but this is not the only way to do a class project. Class projects can also take the form of well-written descriptions of one or more papers in the area; formulations of clean, new open problems; or implementations of existing algorithms. Projects can be purely mathematical (geometric) and/or theoretical computer science (algorithmic/complexity theoretic). There may also be a project presentation and/or a small number of problem sets.

This is a graduate class but both undergraduate and graduate students are welcome. A background in discrete mathematics and algorithms (e.g., 6.046) is required. Refer to the class webpage for more details and updates.

URL: http://theory.csail.mit.edu/classes/6.885/fall04/

6.852J/18.437J Distributed Algorithms

Teacher: Prof. Nancy Lynch

Meeting Time: TBA

Brief Description:

Design and analysis of concurrent algorithms,
emphasizing those suitable for use in distributed networks. Process synchronization, allocation of computational resources, distributed consensus, distributed graph algorithms, election of a leader in a network, distributed termination, deadlock detection, concurrency control, communication, and clock synchronization. Special consideration given to issues of efficiency and fault tolerance. Formal models and proof methods for distributed
computation.

URL: http://theory.lcs.mit.edu/classes/6.852/05

6.854/18.415J: Advanced Algorithms

Teacher: Prof. David Karger

Meeting Time: TBA

Brief Description:

The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are "efficient," and even the model of computation can vary widely from area to area. In this second course in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to mathematical maturity.

The coursework will involve problem sets and a final project that is research-oriented.

URL:

18.433 Combinatorial Optimization

Teacher: Prof. Michel Goemans

Meeting Time: TBA

Brief Description:

Thorough treatment of linear programming and combinatorial optimization. Topics include matching theory, network flow, matroid optimization, and how to deal with NP-hard optimization problems. Prior exposure to discrete mathematics (such as 18.310) helpful.

URL: http://math.mit.edu/~goemans/18433.html

18.435J/2.111J Quantum Computation

Teacher: Prof. Peter Shor, E. Farhi & S. Lloyd

Meeting Time: TBA

Brief Description: Provides an introduction to the theory and practice of quantum computation. Topics covered: Physics of information processing; quantum algorithms including the factoring algorithm and Grover's search algorithm; quantum error correction; quantum communication and cryptography. Knowledge of quantum mechanics helpful but not required.

URL:

18.409 Convex Geometry and Random Walks

Teacher: Prof. Santosh Vempala

Meeting Time: TBA

Brief Description: Algorithmic problems in geometry often become tractable with the assumption of convexity (e.g. optimization, volume computation, learning, finding the average etc.). We will study this phenomenon in depth, beginning with classical topics such as the Brunn-Minkowski inequality and Gaussian isoperimetry, and then proceed to more recent developments in the field of geometric isoperimetric inequalities (e.g., if you cut a cylinder into two equal volume parts with a hyperplane, what is the minimum area of the separation? what is the maximum?), and their extensions to logconcave functions. One motivating problem will be that of efficiently sampling a geometric distribution by a random walk. Somewhat surprisingly, this problem plays a central role in the solution of all the algorithmic problems mentioned above.

URL: http://www-math.mit.edu/~vempala/convex/course.html

* Please be advised that this is a partial list. Please refer to MIT's on-line class listings, Course 6: Electrical Engineering and Computer Science, Course 18: Mathematics or the individual Faculty homepages for further details.