BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME:Theory Colloquium Spring 2008 Events
BEGIN:VEVENT
DTSTART;TZID=US/Eastern:20080506T161500
DTEND;TZID=US/Eastern:20080506T173000
URL;VALUE=URI:http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=1861
SUMMARY:Game Theory with Costly Computation
LOCATION:32-G449 (Kiva)
DESCRIPTION:Series: Theory Colloquium Spring 2008\nSpeaker:  Rafael Pass\, Cornell University\nHost: Silvio Micali\, MIT\nContact: Alexandr Andoni\, 617 253 6182\, andoni@mit.edu\nRefreshment Time: 3:45PM\nRelevant URL: <a href="http://theory.csail.mit.edu/theory-seminars/calendar.html">http://theory.csail.mit.edu/theory-seminars/calendar.html</a>\n[Please note the UNUSUAL LOCATION\, 32-G449.]\n\nWe develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. Using this framework\, we provide a game-theoretic definition of protocol security that takes both computation and incentives into account.\n\nWe show that a special case of the definition is equivalent to a variant of precise zero-knowledge (Micali and Pass\, STOC'06). This result shows that the two approaches used for dealing with "deviating" players in two different communities---Nash equilibrium in game theory\, and zero-knowledge "simulation" in cryptography---are intimately connected; indeed\, they are essentially equivalent in the context of secure computation.\n\nPrior knowledge of game theory or cryptography is not assumed.\n\nJoint work with Joseph Halpern.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=US/Eastern:20080513T161500
DTEND;TZID=US/Eastern:20080513T173000
URL;VALUE=URI:http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=1876
SUMMARY:On set cover in geometric settings
LOCATION:32-155
DESCRIPTION:Series: Theory Colloquium Spring 2008\nSpeaker:  Sariel Har-Peled\, U of Illinois at Urbana-Champaign\nHost: Piotr Indyk\, MIT\nContact: Alexandr Andoni\, 617 253 6182\, andoni@mit.edu\nRefreshment Time: 3:45PM\nRelevant URL: <a href="http://theory.csail.mit.edu/theory-seminars/calendar.html">http://theory.csail.mit.edu/theory-seminars/calendar.html</a>\nIn this talk\, we will survey some of the known results on weighted set cover in geometric settings\, and how the known approximation algorithms work. In the second part of the talk\, we will discuss some recent results\, on the weighted set cover for weighted halfplanes\, and fat shapes in the plane.
END:VEVENT
END:VCALENDAR