Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Schapiro (CEPSR) Building, Columbia University 412
Date: May 16, 2003, 2:50 p.m.
Host: Yevgeniy Dodis
Synopsis:
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 Probabilistically 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.
Notes:
In-person attendance only available to those with active NYU ID cards.