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.
Document last modified on March 1, 1995