Sixue Cliff Liu Ph.D. Candidate in Computer Science Princeton University Email: Firstname + L at princeton dot edu Office: 194 Nassau Street 307

Hi! I'm a fourth year PhD student in the Theory Group of Computer Science Department at Princeton University, where I'm extremely fortunate to be advised by Robert Tarjan.

Previously, I obtained my M.S. degree from Institute for Interdisciplinary Information Sciences, Tsinghua University.

My main research interests lie in Algorithmic Graph Theory.

I'm very generously supported by a 2017-18 Gordon Y.S. Wu Fellowship. I was also a research intern at Microsoft Research (Redmond) in the winter of 2016-17.

Recent Papers

1. Sepehr Assadi, S. Cliff Liu, Robert E. Tarjan. An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models.
   SIAM Symposium on Simplicity in Algorithms (SOSA 2021)


2. S. Cliff Liu, Robert E. Tarjan, Peilin Zhong. Connected Components on a PRAM in Log Diameter Time. [arxiv] [slides] [video]
   ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)


3. S. Cliff Liu. Lower Bounds for Small Ramsey Numbers on Hypergraphs. [arxiv] [slides]
   International Computing and Combinatorics Conference (COCOON 2019)


4. S. Cliff Liu, Robert E. Tarjan. Simple Concurrent Labeling Algorithms for Connected Components. [arxiv] [slides]
   Symposium on Simplicity in Algorithms (SOSA 2019)


5. S. Cliff Liu. Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT. [arxiv] [slides]
   International Colloquium on Automata, Languages, and Programming (ICALP 2018)


6. S. Liu, Gerard de Melo. Should Algorithms for Random SAT and MaxSAT be Different? [arxiv] [slides]
   AAAI Conference on Artificial Intelligence (AAAI 2017)


7. S. Liu, Periklis A. Papakonstantinou. Local Search for Hard SAT Formulas: the Strength of the Polynomial Law. [arxiv]
   AAAI Conference on Artificial Intelligence (AAAI 2016)

Updates

• 12/2019: Invited student in Workshop on Parallel Algorithms and Data Structures in Hawaii.
  
• 08/2019: Invited talk on graph algorithms in John Hopcroft Center for Computer Science. [slides]
  
• 02/2019: Assistant in Instruction for COS 423: Theory of Algorithms, Spring 2019.
• 09/2018: Young researcher in the 6th Heidelberg Laureate Forum.
• 08/2018: Assistant in Instruction for COS 521: Advanced Algorithm Design, Fall 2018.
• 07/2016: PolyPower places 4th in the Random track in SAT Competition. [arxiv] [code]