{"id":4094,"date":"2026-04-26T13:08:17","date_gmt":"2026-04-26T20:08:17","guid":{"rendered":"https:\/\/colleges.claremont.edu\/ccms\/?post_type=tribe_events&#038;p=4094"},"modified":"2026-04-26T13:08:17","modified_gmt":"2026-04-26T20:08:17","slug":"an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu","status":"publish","type":"tribe_events","link":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/","title":{"rendered":"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU)"},"content":{"rendered":"<p><strong>Abstract:<\/strong> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":262,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_price":"","_stock":"","_tribe_ticket_header":"","_tribe_default_ticket_provider":"","_tribe_ticket_capacity":"0","_ticket_start_date":"","_ticket_end_date":"","_tribe_ticket_show_description":"","_tribe_ticket_show_not_going":false,"_tribe_ticket_use_global_stock":"","_tribe_ticket_global_stock_level":"","_global_stock_mode":"","_global_stock_cap":"","_tribe_rsvp_for_event":"","_tribe_ticket_going_count":"","_tribe_ticket_not_going_count":"","_tribe_tickets_list":"[]","_tribe_ticket_has_attendee_info_fields":false,"_tribe_events_status":"","_tribe_events_status_reason":"","_tribe_events_is_hybrid":"","_tribe_events_is_virtual":"","_tribe_events_virtual_video_source":"","_tribe_events_virtual_embed_video":"","_tribe_events_virtual_linked_button_text":"","_tribe_events_virtual_linked_button":"","_tribe_events_virtual_show_embed_at":"","_tribe_events_virtual_show_embed_to":[],"_tribe_events_virtual_show_on_event":"","_tribe_events_virtual_show_on_views":"","_tribe_events_virtual_url":"","footnotes":"","_tec_slr_enabled":"","_tec_slr_layout":""},"tags":[],"tribe_events_cat":[14],"class_list":["post-4094","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-analysis-seminar","cat_analysis-seminar"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.2 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences\" \/>\n<meta property=\"og:description\" content=\"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 [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/\" \/>\n<meta property=\"og:site_name\" content=\"Claremont Center for the Mathematical Sciences\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/\",\"url\":\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/\",\"name\":\"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences\",\"isPartOf\":{\"@id\":\"https:\/\/colleges.claremont.edu\/ccms\/#website\"},\"datePublished\":\"2026-04-26T20:08:17+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/colleges.claremont.edu\/ccms\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Events\",\"item\":\"https:\/\/colleges.claremont.edu\/ccms\/events\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU)\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/colleges.claremont.edu\/ccms\/#website\",\"url\":\"https:\/\/colleges.claremont.edu\/ccms\/\",\"name\":\"Claremont Center for the Mathematical Sciences\",\"description\":\"Proudly Serving the Math Community at the Claremont Colleges Since 2007\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/colleges.claremont.edu\/ccms\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/","og_locale":"en_US","og_type":"article","og_title":"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences","og_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 [&hellip;]","og_url":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/","og_site_name":"Claremont Center for the Mathematical Sciences","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/","url":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/","name":"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU) - Claremont Center for the Mathematical Sciences","isPartOf":{"@id":"https:\/\/colleges.claremont.edu\/ccms\/#website"},"datePublished":"2026-04-26T20:08:17+00:00","breadcrumb":{"@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/colleges.claremont.edu\/ccms\/event\/an-exact-algorithm-for-the-unanimous-vote-problem-feyza-duman-keles-nyu\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/colleges.claremont.edu\/ccms\/"},{"@type":"ListItem","position":2,"name":"Events","item":"https:\/\/colleges.claremont.edu\/ccms\/events\/"},{"@type":"ListItem","position":3,"name":"An Exact Algorithm for the Unanimous Vote Problem (Feyza Duman Keles, NYU)"}]},{"@type":"WebSite","@id":"https:\/\/colleges.claremont.edu\/ccms\/#website","url":"https:\/\/colleges.claremont.edu\/ccms\/","name":"Claremont Center for the Mathematical Sciences","description":"Proudly Serving the Math Community at the Claremont Colleges Since 2007","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/colleges.claremont.edu\/ccms\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"ticketed":false,"_links":{"self":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events\/4094","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events"}],"about":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/types\/tribe_events"}],"author":[{"embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/users\/262"}],"version-history":[{"count":1,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events\/4094\/revisions"}],"predecessor-version":[{"id":4095,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events\/4094\/revisions\/4095"}],"wp:attachment":[{"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/media?parent=4094"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tags?post=4094"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/colleges.claremont.edu\/ccms\/wp-json\/wp\/v2\/tribe_events_cat?post=4094"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}