Sixue Liu will present his General Exam "Faster and Simpler Concurrent Algorithms for Graph Problems" on May 13, 2019 at 2pm in CS 105. The members of his committee are Robert Tarjan (adviser), Bernard Chazelle, Matt Weinberg. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract : Many classical graph problems have efficient sequential algorithms, with some of them even running in linear time in the input size, which is best possible. But linear time is not fast enough for massive datasets, for which we turn to concurrency. We study concurrent algorithms for two classic problems: the connected components of an undirected graph, and the strongly connected components of a directed graph. The first problem has been extensively studied in the concurrent setting, especially on the classical Parallel Random Access Machines (PRAM). However, many fast PRAM algorithms are hard to implement due to the complications in the algorithms. Our first result is several new elegant PRAM algorithms for the connected components problem, which achieve the same time complexity comparing to the existing best ones but are significantly simpler. Our algorithms are deterministic, use linear number of processors, and run in $O(\log n)$ time. This is joint work with Robert Tarjan. Our second result is a simple PRAM algorithm for connected components and spanning forest that runs faster than any existing ones when the input graph has small diameter, which is usually the case in real-world applications. The algorithm is randomized, uses linear number of processors, and runs in $O(\log d \log\log n)$ time with high probability where $d$ is the diameter of the input graph. This is joint work with Robert Tarjan and Peilin Zhong. We also examine the strongly connected components problem, for which a truly sublinear time and nearly linear work concurrent algorithm is only known recently. We show that the current time bound $\tilde{O}(n^{2/3})$ for this algorithm is tight by constructing a hard example. It is possible to design new algorithms to improve this upper bound. This is joint work with Sepehr Assadi and Robert Tarjan. Reading list : [1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. [2] B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for shuffle-exchange network and PRAM. IEEE Trans. Computers, 36(10):1258–1263, 1987. [3] R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), pages 869–942. 1990. [4] J. H. Reif. Optimal parallel algorithms for graph connectivity. Technical report, HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB, 1984. [5] Y. Shiloach and U. Vishkin. An O(log n) parallel connectivity algorithm. J. Algorithms, 3(1):57–67, 1982. [6] R. E. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. J. ACM, 31(2):245–281, 1984. [7] A. Andoni, Z. Song, C. Stein, Z. Wang, and P. Zhong. Parallel graph connectivity in log diameter rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 674–685, 2018. [8] K. W. Chong and T. W. Lam. Finding connected components in O(log n log log n) time on the EREW PRAM. J. Algorithms, 18(3):378–402, 1995. [9] J. T. Fineman. Nearly work-efficient parallel algorithm for digraph reachability. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 457–470, 2018. [10] D. B. Johnson and P. T. Metaxas. Connected components in O (logˆ3/2 n) parallel time for the CREW PRAM. J. Comput. Syst. Sci., 54(2):227–242, 1997. [11] S. Halperin and U. Zwick. An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM. J. Comput. Syst. Sci., 53(3):395–416, 1996.