2002-12-03 23:45

Course Information

Title: Theory Workshop
Course Number: 15-850(a)
Credit: 2 (This cannot be counted towards course requirement.)
Time: Fridays, 10:00 - 12:00
Place: NSH 3002

The objective of the Theory Workshop is to allow us to work on new and exciting problems in theory. Unlike previous TGIWs, the talks would try to focus on techniques that are generally applicable to many theoretical topics rather than results confined in some particular areas. This makes it more likely for us to benefit in our own research.

The format of the course will be a series of seminars presented by students (or post-docs, or faculty members). Each seminar should consist of an introduction to a technique, followed by some example(s) to illustrate how to apply the technique. Your goal is to teach the technique to the audience so that they can recall the technique when it may be used to solve their problems later. Since illustrating some techniques may take more than two hours, you are welcomed to give seminars that span several days.

There will be no homework, but you are expected to show up in most of the seminars. BTW, occassionally, pastries will be provided, but you've got to come early. :P

Meeting Schedule

Date Speaker Topic
30-Aug-2002 Maverick Woo
The Discrepancy Method (Part 1)

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.

06-Sept-2002 None (IC Theory Faculty talks)
13-Sept-2002 Nikhil Bansal
Using The PCP Theorem

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.

20-Sept-2002 Shuchi Chawla
Semi-Definite Programming

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.

27-Sept-2002 Maverick Woo
Probability Fun Fair

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!

04-Oct-2002 No Speaker No Topic
11-Oct-2002 Luis von Ahn

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
18-Oct-2002 Ke Yang
Teach Yourself About Zero-Knowledge In Two Hours

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.

25-Oct-2002 Abie Flaxman
Linear Algebra in Combinatorics

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.

01-Nov-2002 No Speaker No Topic
08-Nov-2002 Amitabh Sinha
Approximation Algorithms Using Lagrangean Relaxations

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.

15-Nov-2002 Ke Yang
Teach Yourself More About Zero-Knowledge In Two Hours

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.

22-Nov-2002 Reto Strobl
Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems

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

29-Nov-2002 No Speaker Thanks-giving Break
06-Dec-2002 Bartosz Przydatek
Private Distributed Approximations,
or what if your ISP charges you for each bit?

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)

13-Dec-2002 None Happy Holidays!

Topics to come

These are all tentative and subjected to change.

Valid XHTML 1.1! Valid CSS! Maverick Woo