[Коллоквиум]: Computational Aspects of Monotone Dualization
343 views · Published 16 May 2015 · 1:12:03 · Indexed 27 October 2026
Channel: ФКН ВШЭ · 2015 · Education
Speaker: Kazuhisa Makino - Research Institute for Mathematical Sciences, Kyoto University Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including computer science, artificial intelligence, data mining, machine learning, and game theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 30 years. We briefly survey computational results for this problem, which includes the remarkable result by M.L. Fredman and L.G. Khachiyan that the problem is solvable in quasi-polynomial time (and thus most likely not coNP-hard), as well as on follow-up works.
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
[Презентация факультета в ДК ЗИЛ]: Иван Аржанцев, декан факультета компьютерных наук