Amir Abboud - Challenges in Fine-Grained Complexity of Approximation in P
Автор: DIMACS CCICADA
Загружено: 2025-08-04
Просмотров: 207
Описание:
Amir Abboud, Weizmann Institute of Science, presents "Challenges in Fine-Grained Complexity of Approximation in P" at the DIMACS Workshop on Hardness of Approximation in P held at Rutgers University on July 21-23, 2025.
The talk will overview challenges in the fine-grained complexity of approximation in P and what we know about them so far. A large number of conditional lower bounds have been established in the last decade under a small number of core conjectures. Whether similar lower bounds hold for the approximate versions of these problems is often a meaningful open question. It is natural to seek “gap versions” of the core conjectures, as well as “gap amplification” techniques that relate a conjecture to its gap version. The talk will discuss the extent to which this has been accomplished for each conjecture.
Workshop webpage: http://dimacs.rutgers.edu/events/deta...
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
![Michal Wlodarczyk - Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard](https://imager.clipsaver.ru/RvPwmc2f3Z8/max.jpg)
