BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Claremont Center for the Mathematical Sciences - ECPv6.15.17.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Claremont Center for the Mathematical Sciences
X-ORIGINAL-URL:https://colleges.claremont.edu/ccms
X-WR-CALDESC:Events for Claremont Center for the Mathematical Sciences
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20250309T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20251102T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20260308T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20261101T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20270314T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20271107T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20260501T161500
DTEND;TZID=America/Los_Angeles:20260501T171500
DTSTAMP:20260615T150428
CREATED:20260426T200817Z
LAST-MODIFIED:20260426T200817Z
UID:4094-1777652100-1777655700@colleges.claremont.edu
SUMMARY:An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles\, NYU)
DESCRIPTION:Abstract: Consider n independent\, biased coins\, each with a known probability of heads. Presented with an ordering of these coins\, flip (i.e.\, toss) each coin once\, in that order\, until we have observed both a head and a tail\, or flipped all coins. The Unanimous Vote problem asks us to find the ordering that minimizes the expected number of flips. Gkenosis et al. [arXiv:1806.10660] gave a polynomial-time approximation algorithm for this problem\, where the approximation ratio is the golden ratio. They left open whether the problem was NP-hard. We answer this question by giving an exact algorithm that runs in time O(n log n). The Unanimous Vote problem is an instance of the more general Stochastic Boolean Function Evaluation problem: it thus becomes one of the only such problems known to be solvable in polynomial time. Our proof uses simple interchange arguments to show that the optimal ordering must be close to the ordering produced by a natural greedy algorithm. Beyond our main result\, we compare the optimal ordering with the best adaptive strategy\, proving a tight adaptivity gap of 1.2 + o(1) for the Unanimous Vote problem.
URL:https://colleges.claremont.edu/ccms/event/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu/
LOCATION:Emmy Noether Room\, Estella 1021\, Pomona College\,\, 610 N. College Ave.\, Claremont\, CA\, 91711\, United States
CATEGORIES:Analysis Seminar
ORGANIZER;CN="Ryan Aschoff":MAILTO:ryan.aschoff@cgu.edu
END:VEVENT
END:VCALENDAR