DIMACS Theory Lunch


Title:

Neighborhood principle in tic-tac-toe-like games and complexity

Speaker:

Jozsef Beck
Rutgers University

Place:

Room 402, Dept. of Computer Sciences, Computer Science Building,
35 Olden Street (corner of Olden and William Street), Princeton University

Time:

11:50 AM - 1:15 PM
Friday, March 3, 1995

Abstract:

A generalized tic-tac-toe game is played on an arbitrary hypergraph, the underlying set is the ``board", and the hyperedges are the ``winning sets". The players alternately mark points (elements of the board), and that player wins who first occupies a winning set. There are surprising principles like the ``random game principle" and the ``neighborhood principle". (These two principles together usually beat the ``pairing strategy".) At the end I want to show an application on the ``parallel matching complexity" of Ramsey theorem.

Host: Sanjeev Arora, Princeton University

If you have any questions, contact Sandy Barbu . As usual, we will serve the lunch at 11:50 and the talk will begin at 12:10.


dimacs-www@dimacs.rutgers.edu
Document last modified on March 1, 1995