moteur de recherche

Séminaire Algo - Andrey Kupavskii
Séminaire Algo - Andrey Kupavskii
26-Feb-2019 14:00
Age: 1 year

Andrey Kupavskii

Extremal results for families with forbidden subconfigurations

Salle de séminaire (4B05R) - Bâtiment Copernic

A family is a collection of subsets of an n-element set. Extremal set theory questions typically ask for the largest families that satisfy certain restrictions. In this talk, I will discuss some recent results in extremal set theory that deal with intersecting families, families without s pairwise disjoint sets, and related and lower bounds for the k-SUM problem. Then we will show that there exist linear decision trees and algebraic computation trees of depth O(n3 log3 n) solving k-SUM. Furthermore, we show that there exists a randomized algorithm that runs in O(n⌈k/2⌉+8) time, and performs O(n3 log3 n) linear queries on the input. Thus, it is possible to have an algorithm with a runtime almost identical (up to the +8) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of k. The techniques involve computational geometry tools such as Meiser's algorithm for point location (1993) and epsilon-nets.

<- Back to: Accueil