演講時間: 112年11月29日（三） 14:00~16:00

演講地點: E6-A207教室

演講者: 蔡孟宗 助理研究員（中央研究院 資訊科學所）

演講主題: Graph Computations Using Sublinear Space

演講大網: When tackling graph problems involving real-world data, we often encounter a common challenge: input sizes exceed our machine's memory capacity. In such scenarios, textbook algorithms might not have efficient implementations, necessitating alternative algorithm designs. In this talk, we will explore the concept of sparse certificates, enabling us to perform some classical graph computations as if the entire dataset resides in memory. In addition, we will learn how to identify a problem that does not admit a sparse certificate. Finally, a number of research problems suited for exploration by graduate students will be introduced.

請研究所一年級的同學當天準時聽講