Thatchaphol Saranurak: Hardness of dynamic problems and the geometry of binary search trees
Time: Mon 2015-06-22 12.00
Location: Room 4523, Lindstedtsvägen 5, KTH
Participating: Thatchaphol Saranurak, Theory Group, KTH
Practicalities
Lunch is served at 12:00 noon (register at this doodle at the latest on saturday June 20). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
ABSTRACT
This talk consists of two separated parts; both about dynamic data structures.
The first part is about proving hardness of dynamic graph problems. In dynamic graph problems, one wants to maintain some properties (e.g. connectivity, distances between nodes, maximum matching) of a given graph where edges of a graph can be inserted and deleted. While there are several techniques for proving polylogarithmic lower bounds for the time required for the update, these techniques currently do not give polynomial (\(n^ε\)) lower bounds. Then, one way to show hardness of the problems is to assume some conjectures (e.g. SETH, 3SUM) and prove that an algorithm with fast update time would contradict the conjecture. I will survey the active development of these techniques for proving hardness based on conjectures. Then, I will talk about our new conjecture called the Online Matrix-Vector Multiplication, which very well tightly captures the hardness of many dynamic problems. This is joint work with Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.
The second part is about the geometry of binary search trees. First, I will talk about a Demaine et al. paper which shows how the "execution log" of a binary search tree algorithm can be represented and characterized by a point set in a plane with a simple property. This characterization suggests a natural algorithm called Greedy. Next, I will talk about our work which shows that, using forbidden-pattern theory, Greedy almost solves 30-year-old Traversal Conjecture up to a function depending on alpha(n) (inverse-ackerman function). This is based on a joint work with Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, and Kurt Mehlhorn.