Columbia University Department of Computer Science

The IBM Research | NYU | Columbia THEORY DAY
Friday, May 16, 2003

Davis auditorium, 412 Schapiro(CEPSR) building,
Columbia University, New York

The IBM Research | NYU | Columbia Theory Day is a semi-annual conference,
aimed to bring together people in the New York Metropolitan area for one day of
interaction and discussion.  The Theory Day features several (usually 4-5) hour-long
presentations by leading theoretical computer scientists about state-of-the-art advances
in various areas.  Some presentations give a survey of the latest advances in some area,
while others may concentrate on a particular (often ground-breaking) result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.


 9:30  - 10:00   Coffee and bagels

10:00 - 10:55 Prof. Michael Kearns
Network Models for Multiplayer Game Theory

10:55 - 11:05 Short break

11:05 - 12:00 Dr. Irit Dinur
Tighter Inapproximability and Recent Views of the Long-Code

12:00 - 1:55 Lunch break

1:55 - 2:25 Dr. Matt Blaze
Cryptology and Non-Computer Security

2:30 - 3:25 Prof. Hugo Krawczyk
Theory and Practice of Cryptographically-Protected Communications

3:25 - 3:45 Coffee break

3:45 - 4:40 Prof. Madhu Sudan
Small Probablistically Checkable Proofs with Low Query Complexity

The Theory Day is held at the Davis auditorium, 412 Schapiro (CEPSR) building,
500 West 120th Street, Columbia University, New York, NY 10027.
Click here for directions.

To subscribe to our mailing list, follow instructions here.


Yevgeniy Dodis (NYU)

Tal Malkin (Columbia)  (212)-939-7097

Tal Rabin (IBM Research)

Baruch Schieber (IBM Research)


Network Models for Multiplayer Game Theory

Prof. Michael Kearns
(University of Pennsylvania)

Over the last several years, a number of authors have developed
graph-theoretic or network models for large-population game theory.
In such models, each player or organization is represented by a
vertex in a graph, and payoffs are determined by the actions of only
those in the neighborhood of a player. This allows the detailed
specification of social, organizational, and other types of structure
in the strategic interaction of the population.

In this talk, I will survey these models and the attendant algorithms
for certain basic computations, including Nash and correlated equilibria.
Potential applications, as well as generalizations to areas such
as evolutionary game theory and macroeconomics, will also be discussed.

Tighter Inapproximability and Recent Views of the Long-Code

Dr. Irit Dinur
(NEC Research)

The discovery of the PCP theorem in the early 90s was a breakthrough
in the study of inapproximability. In the past decade various
improvements of the PCP theorem were discovered, along with highly
non-trivial ways of using it to obtain stronger (sometimes even tight)
hardness of approximation results.

In this talk, I will focus on a central paradigm by which many of the
stronger PCP hardness of approximation results have been obtained. I
will revisit the "long-code" - a combinatorial object that plays a
central role in these constructions. Then, focusing in particular on
vertex-cover and hypergraph-coloring, I will show a connection between
the long-code and other well-studied combinatorial objects: showing
how Erdos-Ko-Rado theorems on intersecting families of finite sets,
conditions on when a Boolean function is a Junta, and the chromatic
number of the Kneser graph can all be used to "decode" the long-code.

Cryptology and Non-Computer Security

Dr. Matt Blaze
(AT&T Research)

Computer security and cryptology takes much of its basic philosophy
and language from the world of mechanical locks, and yet we often
ignore the possibility that physical security systems might suffer from
the same kinds of attacks that plague computers and networks. This
talk examines mechanical locks from a computer scientist's viewpoint.
We describe attacks for amplifying rights in mechanical pin tumbler locks.
Given access to a single master-keyed lock and its associated change key,
a procedure is given that allows discovery and creation of a working master
key for the system. No special skill or equipment, beyond a small number
of blank keys and a metal file, is required, and the attacker need engage
in no suspicious behavior at the lock's location; the attacks
exploit the structure of the keyspaces of such locks. We end with
directions for research in this area and the suggestion that
mechanical locks are worthy objects of our attention and scrutiny.

Theory and Practice
of Cryptographically-Protected Communications

Prof. Hugo Krawczyk
(IBM Research and Technion)

The interaction between Complexity Theory and Cryptography has resulted in
a remarkable theory of cryptography, developed mainly in the 80's, that
laid the foundations for many basic notions and tools in this area.
Since the early 90's, and intensified later by the "Internet Revolution",
there has been an increasing interest in applying these theoretical
tools to the solution of real-world security problems. Some ten years
later one can certainly say that Complexity-based Cryptography
has not only generated a beautiful theory but also a highly usable one.
While the focus on actual applications has changed some of the problem
parameters (e.g., emphasizing finite rather than asymptotic analysis)
and specialized some of the research to specific efficient constructs,
most of the theoretical notions and tools remain very relevant in the
applied world.

This talk intends to touch on a (small) subset of topics that stress
this fascinating interaction between theory and practice in cryptography.
Specifically, we will discuss some examples related to the design and
analysis of secure communications with immediate relevance and applicability
to real-world secure communication protocols such as SSL and IPsec.
(We will also apologize for the presumptuous title...)

Small Probablistically Checkable Proofs
with Low Query Complexity
Prof. Madhu Sudan

The last decade saw dramatic constructions of proofs (or more
precisely, their verifiers) that are only polynomially longer
than classical proofs and verifiable probabilistically with a
constant number of queries. However, till recently at least
one of the two constants - the number of queries and the exponent
in the size of the proof - has been very large. In this talk I
will describe a sequence of results that has improved the state
of affairs significantly leading to nearly linear sized proofs
with small query complexity. I will also describe combinatorial
counterparts to probabilistically checkable proofs (called
locally testable codes) that yield error-correcting codes
for which proximity to codewords is testable with constant
number of queries.

Based on joint works with Eli Ben-Sasson, Oded Goldreich,
Prahladh Harsha, Salil Vadhan and Avi Wigderson.

"Every day is Theory Day"