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 semiannual
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 45) hourlong
presentations by leading theoretical computer scientists about
stateoftheart advances
in various areas. Some presentations give a survey of the latest
advances in some area,
while others may concentrate on a particular (often groundbreaking)
result.
The meeting is free and open to everyone; in particular, students are
encouraged to attend.
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 LongCode 12:00  1:55 Lunch break
1:55  2:25 Dr. Matt Blaze Cryptology and NonComputer Security
2:30  3:25 Prof. Hugo Krawczyk Theory and Practice of CryptographicallyProtected 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:
Yevgeniy Dodis (NYU)
Tal Malkin (Columbia)
(212)9397097
Tal Rabin (IBM Research)
Baruch Schieber (IBM
Research)
Abstracts:
Network Models for Multiplayer Game Theory
Prof. Michael Kearns (University of Pennsylvania)
Over the last several years, a number of authors have developed graphtheoretic or network models for largepopulation 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 LongCode
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 nontrivial 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 "longcode"  a combinatorial object that plays a central role in these constructions. Then, focusing in particular on vertexcover and hypergraphcoloring, I will show a connection between the longcode and other wellstudied combinatorial objects: showing how ErdosKoRado 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 longcode.
Cryptology and NonComputer 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 masterkeyed 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 CryptographicallyProtected 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 realworld security problems. Some ten years later one can certainly say that Complexitybased 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 realworld 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 errorcorrecting codes for which proximity to codewords is testable with constant number of queries.
Based on joint works with Eli BenSasson, Oded Goldreich, Prahladh Harsha, Salil Vadhan and Avi Wigderson.
"Every day is
Theory Day"
