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

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

Program:

 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. 

Organizers:

Abstracts:

	      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
                              (MIT)


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.