We will study a minimum spanning tree algorithm by Chazelle. The algorithm is deterministic and has an inverse Ackermann time bound. Besides being the fastest known algorithm of its kind, it also serves as a gentle introduction to the Discrepancy Method. We will see how sampling can be done deterministically and efficiently (in the case of MST) by using a lossy data structure which corrupts the data it contains in a controlled manner.

• Book by Bernard Chazelle
  (Look inside, courtesy of Amazon)
• MST Paper by Bernard Chazelle
• Soft Heap Paper by Bernard Chazelle
• MST Paper by Seth Pettie

The PCP Theorem is a remarkable mathematical achievement. Fortunately, using it does not "usually" require understanding the proof of the theorem.

We will see how different inapproximability results ($c$, $log n$, $2^{log^c n}$, $n^c$) for various problems are obtained from the basic PCP Theorem. We will illustrate the basic techniques by looking at several examples.

The lecture will closely follow the survey due to Arora and Lund.

Semi-Definite Programming is a lesser known cousin of Linear Programming. It is as easy to apply and solve as LPs, and can be used to express many convex programs. We will examine general properties of semi-definite programs and will discuss where and how it can be used. The focus will be on applications to approximation algorithms.

• Semi-Definite Programming for Combinatorial Optimization by C. Helmberg, Oct 2000.
• Semi-Definite Programming by L. Vandenberghe & S. Boyd, March 1996.

We will solve a number of interesting probability questions together and try to extract the general techniques used in the solutions. While some of the questions we will study are considered classic, we will try to put our focus on more recently solved puzzles.

The talk will be slow-paced and self-contained. Bring paper and pencil!

Generatingfunctionology is powerful combinatorial tool. It is a method of counting based on formal power series which can give very elegant and simple solutions to seemingly complicated problems. In this talk we will introduce the method and give a few examples to try to convince people that it really does work.

• Book by Herbert Wilf

I will talk about zero knowledge protocols and its variants. I will start by surveying the basic notations about zero knowledge and some technical details. Then I will discuss some more advanced issues, including non-blackbox simulation and extraction, concurrency, non-malleability, universal composability. Some prior understanding of ZK is greater beneficial although not necessary. This talk would be more of a survey than a tutorial as I will give no proofs.

• ZK page at MIT LCS
• ZK Chapter of Oded Goldreich's book

The so-called "Linear-Algebraic method" is a simple and deviously clever way to prove upper bounds. I will lead you through several examples, probably including "Odds-town" and 2-distance sets.

When designing approximation algorithms for optimization problems, it is sometimes the case that the problem is ``easy'' if we only consider all but one of the constraints. This motivates the Lagrangean approach: simply penalize the violation of the ``complicated'' constraint and add this to the objective function. We now solve the ``easy'' problem which remains, and then do a little tweaking to recover a good solution to the original problem.

We will illustrate this technique by applying it to a few specific problems. The talk will be fully self-contained, and references will be posted later.

I will be talking about some advanced topics on Zero Knowledge protocols, including Non-Blackbox Simulation, Concurrency, Non-malleability and Universally Composable Zero Knowledge. This is a follow-up from the ZK lecture I gave a month ago. Prior knowledge about ZK is highly recommended.

(This talk is based on a paper under the same title in ACM Conference on Computer and Communications Security by Christian Cachin, Klaus Kursawe, Anna Lysyanskaya and Reto Strobl. Reto is affliated with IBM Research Lab in Zurich.)

Verifiable secret sharing is an important primitive in distributed cryptography. With the growing interest in the deployment of threshold cryptosystems in practice, the traditional assumption of a synchronous network has to be reconsidered and generalized to an asynchronous model. This paper proposes the first practical verifiable secret sharing protocol for asynchronous networks. The protocol creates a discrete logarithm-based sharing and uses only a quadratic number of messages in the number of participating servers. It yields the first asynchronous Byzantine agreement protocol in the standard model whose efficiency makes it suitable for use in practice. Proactive cryptosystems are another important application of verifiable secret sharing. The second part of the talk intorduces proactive cryptosystems in asynchronous networks and presents an efficient protocol for refreshing the shares of a secret key for discrete logarithm-based sharings.

Alice and Bob have own some private data, $a$ resp. $b$. They don't want to disclose the data to each other, but they would like to compute jointly some function $f(a,b)$, without revealing more than necessary.

This problem is a special case of secure Multi-Party Computation (MPC), which has been investigated extensively in the last 20 years. One of the major results in this area says that anything that can be computed efficiently, can also be computed efficiently and securely. However, "efficient" in the above statement means "polynomial", and the known general protocols are practically useless (mainly due to the large communication complexity) if the private inputs are larger than a few bytes.

Of course, the area of communication complexity has been also intensively studied, and now we know many problems can be approximatively solved using very little communication. However, such communication-efficient approximations often do not protect privacy of the data.

Recently, Feigenbaum et al. [FIMNSW'01] introduced the problem of secure multi-party computation of approximations, with the goal of getting the best of two worlds: private computation with low communication overhead.

In this talk I'll first give you a 5min-intro to MPC, and then present the results by Feigenbaum et al., and some related works. I'll discuss also many open problems, some of which originate in CMU-Aladdin "Privacy in DATA" project.

[FIMNSW'01] Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca Wright. Secure Multiparty Computation of Approximations. Proc. of the 28th International Colloquium on Automata, Languages and Programming (ICALP '01)