BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/current/newsitem/16077
 /31-March-2026-Computational-Social-Choice-Seminar
 -Paul-Goldberg
DTSTAMP:20260226T142137
SUMMARY:Computational Social Choice Seminar, Paul 
 Goldberg
ATTENDEE;ROLE=Speaker:Paul Goldberg
DTSTART;TZID=Europe/Amsterdam:20260331T160000
LOCATION:L1.12 in LAB42, Science Park 900, Amsterd
 am
DESCRIPTION:An unambiguous problem is a computatio
 nal search problem for which any instance has at m
 ost one solution. We are interested in particular 
 in problems where this uniqueness of solutions is 
 due to the structure of the problem itself, as opp
 osed to being due to a (hard to verify) promise th
 at any solution is unique. There are not many such
  problems in the class NP (amongst problems that a
 re not known to be polynomial-time solvable), but 
 there are various interesting ones in the class Σ^
 P_2. For example, some are based on the idea that 
 we can design competitions for which there is at m
 ost one winner. With exponentially-many competitor
 s, we seek a competitor that beats all his opponen
 ts: if "beats" is checkable in polynomial time, we
  have a Σ^P_2 problem having at most one solution.
  Towards classifying the complexity of these probl
 ems, we introduce complexity classes "Polynomial T
 ournament Winner" and "Polynomial Condorcet Winner
 ".  This is joint work in progress with Matan Gilb
 oa, Elias Koutsoupias, and Noam Nisan. I will try 
 to include reminders of definitions of any complex
 ity classes I refer to, apart from P and NP.
X-ALT-DESC;FMTTYPE=text/html:\n  <p>An unambiguous
  problem is a computational search problem for whi
 ch any instance has at most one solution. We are i
 nterested in particular in problems where this uni
 queness of solutions is due to the structure of th
 e problem itself, as opposed to being due to a (ha
 rd to verify) promise that any solution is unique.
  There are not many such problems in the class NP 
 (amongst problems that are not known to be polynom
 ial-time solvable), but there are various interest
 ing ones in the class Σ^P_2. For example, some are
  based on the idea that we can design competitions
  for which there is at most one winner. With expon
 entially-many competitors, we seek a competitor th
 at beats all his opponents: if &quot;beats&quot; i
 s checkable in polynomial time, we have a Σ^P_2 pr
 oblem having at most one solution. Towards classif
 ying the complexity of these problems, we introduc
 e complexity classes &quot;Polynomial Tournament W
 inner&quot; and &quot;Polynomial Condorcet Winner&
 quot;.</p>\n  <p>This is joint work in progress wi
 th Matan Gilboa, Elias Koutsoupias, and Noam Nisan
 . I will try to include reminders of definitions o
 f any complexity classes I refer to, apart from P 
 and NP.</p>\n
URL:https://staff.science.uva.nl/u.endriss/seminar
 /
CONTACT:Ulle Endriss at ulle.endriss at uva.nl
END:VEVENT
END:VCALENDAR