Qizheng He

I am a fifth-year CS Ph.D. student at University of Illinois Urbana-Champaign. My advisor is Timothy M. Chan.

I graduated from Yao Class, Institute for Interdisciplinary Information Sciences, Tsinghua University in 2018.

I was a research intern at Megvii Inc. (Face++), Jan. 2015 - Jul. 2018, and also interned as a Software Engineer at Google's Geo team, May. 2022 - Aug. 2022.


My main research interests lie in computational geometry, algorithms and data structures, and fine-grained complexity.

My CV can be found here.

PUBLICATIONS

See also DBLP's listing.


In Submission

Simple and Faster Algorithms for Knapsack

Qizheng He and Zhean Xu

[arXiv]


Improved Algorithms for Integer Complexity

Qizheng He

[arXiv]


Min-Cut and Min-k-Cut in Disk Hypergraphs

Calvin Beideman and Qizheng He


Range Sampling Re-Re-Revisited

Pingan Cheng, Qizheng He, and Zhengcheng Huang


Conference Papers

On the FPT Status of Monotone Convex Chain Cover

Qizheng He

CCCG 2023

[PDF] [slides]


On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k

Timothy M. Chan, Qizheng He, and Yuancheng Yu

ICALP 2023

[PDF] [arXiv] [YRF version] [YRF slides]


Logical Entity Representation in Knowledge-Graphs for Differentiable Rule Learning

Chi Han, Qizheng He, Charles Yu, Xinya Du, Hanghang Tong, and Heng Ji

ICLR 2023

[PDF] [arXiv]


Dynamic Geometric Set Cover, Revisited

Timothy M. Chan, Qizheng He, Subhash Suri, and Jie Xue

SODA 2022

[PDF] [arXiv] [slides]


More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

Timothy M. Chan and Qizheng He

SoCG 2021

[PDF] [arXiv] [slides]


More on Change-Making and Related Problems

Timothy M. Chan and Qizheng He

ESA 2020

[PDF] [arXiv]


Faster Approximation Algorithms for Geometric Set Cover

Timothy M. Chan and Qizheng He

SoCG 2020

[PDF] [arXiv] [slides]


Further Results on Colored Range Searching

Timothy M. Chan, Qizheng He, and Yakov Nekrich

SoCG 2020

[PDF] [arXiv] [slides]


Reducing 3SUM to Convolution-3SUM

Timothy M. Chan and Qizheng He

SOSA 2020 (Best Paper Award)

[PDF] [slides]


On the Change-Making Problem

Timothy M. Chan and Qizheng He

SOSA 2020

[PDF] [slides]


The Energy Complexity of Broadcast 

Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie

PODC 2018

[PDF] [arXiv]


The Complexity of Distributed Edge Coloring with Small Palettes

Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto

SODA 2018 

[PDF] [arXiv]


Journal Articles

More Dynamic Data Structures for Geometric Set Cover with Sublinear Update Time

Timothy M. Chan and Qizheng He

Journal of Computational Geometry (JoCG), 2022 (SoCG special issue)

[PDF]


More on Change-Making and Related Problems

Timothy M. Chan and Qizheng He

Journal of Computer and System Sciences (JCSS), 2021 (ESA special issue)

[PDF]


Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma

Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto

ACM Transactions on Algorithms (TALG), 2019

[PDF]


Manuscripts

Thesis: Geometric Set Cover and Related Geometric Optimization Problems

(to be updated)

[slides]


SOT for MOT

Qizheng He, Jianan Wu, Gang Yu, and Chi Zhang

preprint, 2017

[arXiv]


Patents


Teaching

Intro to Algorithms & Models of Computation (CS374), UIUC  Spring 2022, Fall 2022

My email: