CSE Colloquium: Data Structure Lower Bounds: Progress and Frontiers

ZOOM INFORMATION: Join from PC, Mac, Linux, iOS or Android: https://psu.zoom.us/j/98252979303?pwd=V2VNcDh0Z3ZBZHpKNzZEQmJNOXRvUT09 Password: 263310 

or iPhone one-tap (US Toll): +13017158592,98252979303# or +13126266799,98252979303# 

or Telephone: Dial: +1 301 715 8592 (US Toll) +1 312 626 6799 (US Toll) +1 646 876 9923 (US Toll) +1 253 215 8782 (US Toll) +1 346 248 7799 (US Toll) +1 669 900 6833 (US Toll) Meeting ID: 982 5297 9303 Password: 263310 International numbers available: https://psu.zoom.us/u/abVleN8jes 

 ABSTRACT: Data structures are the backbone of algorithm design and information retrieval and underlie the performance of most industry-scale applications, from internet routing and road navigation to machine learning, Cloud storage, search, and compression. As such, understanding what data structures can and cannot compute efficiently, is an important question in both theory and practice. In the past decade, there has been a renewed attention in proving conditional lower bounds (a.k.a. fine-grained complexity and Hardness in P) yet progress on proving unconditional lower bound remains slow. In this talk, I will focus on the progress and obstacles of the renowned Multiphase Program initiated in 2010 by the pioneer of the field, Mihai Patra?cu. 

Patra?cu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving strong lower bounds on the operational time of dynamic data structures for many natural problems. He conjectured that any data structure for the Multiphase problem must make a polynomial number of probes either in the preprocessing or the query phase. He also showed that this conjecture implies strong lower bounds for fundamental dynamic data structure problems such as s-t directed connectivity, Dynamic Shortest Path, Range Mode, and others. 

In this talk, first, I will show that a large family of algorithms, which encompasses all known algorithms for set-disjointness, cannot refute the Multiphase Conjecture, making the first progress in almost a decade since its introduction. Next, I will show a surprisingly deep connection between the Multiphase Conjecture and other long standing open problems in TCS, such as understanding the power of non-linear networks in computing linear operators, offering an explanation for the lack of progress in the past decade. Finally, I propose necessary milestones toward the Multiphase Program with these new connections in mind. 

BIOGRAPHY: Young Kun Ko is an Assistant Professor/Faculty Fellow at NYU Courant supported by Prof. Subhash Khot and Prof. Oded Regev. His Bachelor’s degree is from the University of Chicago. He completed his Ph.D. at Princeton University in 2018 under the supervision of Prof. Mark Braverman. His research interests include Lower Bounds for Algorithms on Massive Data Set, Information Theory and Computational Complexity Theory.