Thursday, April 12 2:30 PM-3:30 PM Eva Tardos, Cornell University The Price of Anarchy
Interaction of users with different incentives is a keyfeature of many
domains ranging from communication networks through social networks and
markets. In light of such competing forces, it is surprising how well some
of these mechanisms work. In this talk we consider a range of games
modeling such interactions, and consider the degradation of quality of
solution caused by the selfish behaviors of users.
Friday, April 13 3:00 PM-4:00 PM Avi Wigderson, Institute for Advanced Study Randomness
Is the universe inherently deterministic or probabilistic? Perhaps more importantly - can we tell the difference between the two? Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms and gambling. Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from "unpredictable" phenomena like the weather or the stock market?
A computational theory of randomness, developed in the past three decades, reveals (perhaps counter-intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I'll explain themain ideas and results of this theory
The talk is aimed at a general science audience, and no particular background will be assumed.
An answer key is now available. Here are the keys for problems 3.11 and 1.17 which were missing.
The four testfiles for Homework 3 are file 1, file 2, file 3, file 4. The first number represents the number of edges, the second the number of vertices, and each subsequent line represents an edge between the pair of numbered vertices. The answer key is now available. The answers to two another problem is also available.
The solutions to these problems must be submitted on www.programming-challenges.com. Register for an account and join my CSE 373 extra credit class if you are intersted.
A schedule for doing these problems that is somewhat consistant with this course is:
The objectives for the course are
The course will also satisfy the following program objective:
- Steven S. Skiena
- 1417 Computer Science Building
- Department of Computer Science
- State University of New York at Stony Brook
- Stony Brook, NY 11794-4400, USA
- skiena@cs.sunysb.edu
- 631-632-9026
Join the Stony Brook Computer Science Society