[Коллоквиум]: Finding a majority ball with majority answers
168 views · Published 31 March 2016 · 43:54 · Indexed 6 November 2026
Channel: ФКН ВШЭ · 2016 · Education
Speaker: Mate Vizer - Renyi Institute Budapest
Suppose we are given a set of n balls {b1, …, bn} each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls. As an answer to such a query we obtain (the index of) a majority ball, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a non-minority ball, that is, a ball whose color occurs at least n/2 times among the n balls. We show that the minimum number of queries needed to solve this problem is Θ(n) in the adaptive case and Θ(n3) in the non-adaptive case. We also consider some related problems. This is a joint work with D. Gerbner, B. Keszegh, D. Palvolgyi, B. Patkos and G. Wiener.
More from this channel
-
1:18:31
[Коллоквиум]: On scale invariance, multifractal formalism, and their applications
-
1:09:43
[Коллоквиум]: Resourse Allocation in the Cloud - Assaf Schuster, Techion
-
1:08:04
[ИТ-лекторий] Занимательная прикладная аналитика в Яндексе
-
1:17:41
[Коллоквиум]: Probabilistic graphical models: Factor graphs and more
-
1:05:46
[Коллоквиум]: Process Mining: Data Science in Action - Wil van der Aalst
-
2:18
[Презентация факультета в ДК ЗИЛ]: Григорий Бакунов, директор по распрост. инф. технологий Яндекс
-
2:55
[Презентация факультета в ДК ЗИЛ]: Григорий Канторович, проректор по работе с абитуриентами ВШЭ
-
11:34
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук