Date

Speaker

Topic

30Aug2002 
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.
References


06Sept2002 
None 
(IC Theory Faculty talks) 
13Sept2002 
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.


20Sept2002 
Shuchi Chawla 
SemiDefinite Programming

SemiDefinite 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 semidefinite programs and will discuss
where and how it can be used. The focus will be on
applications to approximation algorithms.
References


27Sept2002 
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 slowpaced and selfcontained. Bring
paper and pencil!


04Oct2002 
No Speaker 
No Topic 
11Oct2002 
Luis von Ahn 
Generatingfunctionology

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


18Oct2002 
Ke Yang 
Teach Yourself About ZeroKnowledge 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
nonblackbox simulation and extraction, concurrency,
nonmalleability, 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.
References


25Oct2002 
Abie Flaxman 
Linear Algebra in Combinatorics

The socalled "LinearAlgebraic method" is a simple and
deviously clever way to prove upper bounds. I will lead
you through several examples, probably including
"Oddstown" and 2distance sets.


01Nov2002 
No Speaker 
No Topic 
08Nov2002 
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 selfcontained,
and references will be posted later.


15Nov2002 
Ke Yang 
Teach Yourself More About ZeroKnowledge In Two Hours

I will be talking about some advanced topics on Zero
Knowledge protocols, including NonBlackbox Simulation,
Concurrency, Nonmalleability and Universally Composable
Zero Knowledge. This is a followup from the ZK lecture I
gave a month ago. Prior knowledge about ZK is highly
recommended.


22Nov2002 
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 logarithmbased 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 logarithmbased
sharings.


29Nov2002 
No Speaker 
Thanksgiving Break 
06Dec2002 
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 MultiParty
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 communicationefficient
approximations often do not protect privacy of the data.
Recently, Feigenbaum et al. [FIMNSW'01] introduced the
problem of secure multiparty 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 5minintro 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 CMUAladdin "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)


13Dec2002 
None 
Happy Holidays! 