


Classes 

* Please be advised that this is a partial list. Please refer to MIT's online class listings, Course 6: Electrical Engineering and Computer Science, Course 18: Mathematics or the individual Faculty homepages for further details. Also, note that the times & teacher listings only apply to FALL 2006 & are subject to change. Not all classes below are offered every term. 

6.042J/ 18.042J Mathematics for Computer Science 
Teacher: 
Profs. Tom Leighton & Ronitt Rubinfeld 
Meeting Time: 
TR2.304 in 34101 
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 wellordering; 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.3011 in 4270 
Brief Description: 
Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics: sorting; search trees, heaps, and hashing; divideandconquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; numbertheoretic 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 309 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 twocourse
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 nonmobile) 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 welldefined correctness, faulttolerance, 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, welldefined problems and subproblems that must be solved by distributed algorithms in wireless ad hoc networks. These will include problems of lowlevel and higherlevel 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
Pointtopoint routing
Locationbased communication services: Location services; Geographical routing.
Global infrastructure: Poweraware 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
309

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, Nbody problems, multigrid, fastmultipole, 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 handson emphasis on understanding the realities and myths of what is possible on the world's fastest machines.

URL: 
http://beowulf.csail.mit.edu/18.337/index.html 
6.857 Computer and Network Security 
Teacher: 
Prof. Shafi Goldwasser 
Meeting Time: 
TBA 
Brief Description: 
Techniques for achieving security in multiuser computer systems and distributed computer systems. Topics: physical security; discretionary and mandatory access control; biometrics; informationflow models of security; covert channels; elementary cryptography; publickey cryptography; logic of authentication; electronic cash; viruses; firewalls; electronic voting; risk assessment; secure web browsers.. 
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:
 Zeroknowledge Proofs
 Secure Function Evaluation
 CompleteInformation Games and Equilibria
 IncompleteInformation Games and Sequential Reasoning
 Concurrency and Security
 Signaling and Security
 Collusionfree 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, LenstraLenstraLovasz etc.) and algorithms for testing primes (AgarwalKayalSaxena), multiplying matrices (CohnUmans), 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 errorcorrecting codes. Course covers basic definitions, constructions, impossibility
results, and algorithms for using errorcorrecting 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 selfcontained 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 stateoftheart 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 problemsolving 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 wellwritten 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, wordlevel parallelism, bit scaling, dynamic programming, network flow, linear programming, fixedparameter 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 researchoriented. 
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 NPhard 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 BrunnMinkowski 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://wwwmath.mit.edu/~vempala/convex/course.html 

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





