# Ng Hiang Kwui黄炫圭

a.k.a.

PhD Student
College of Computer and Information Science
Northeastern University

I have great enthusiasm for theoretical computer science, especially computational complexity. Currently I'm working on approximate degrees and data-structure lower bounds, advised by Prof. Emanuele Viola. I will visit the Simons Institute for the "Lower Bounds in Computational Complexity" program this fall.

Previously I earned my bachelor's and master's degrees from Shanghai Jiao Tong University, advised by Prof. Yijia Chen. During that period, I did research on parameterized complexity, circuit complexity, and descriptive complexity. I love to explore a wide range of , to learn some latest big results/frameworks, and to attack challenging open problems.

## Papers

• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank
• with Yijia Chen and Joerg Flum, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
• manuscript, conference version
• Using color-coding we demonstrate that some parameterized (hyper)graph problems can be slicewise-defined in $\mathrm{FO}_q$ where $q$ is independent of the parameter $k$, and prove the strictness of $\big(\mathrm{XFO}_{q} \big)_{q \in \mathbb{N}}$ by proving that $\mathrm{FO}_{q} \subsetneq \mathrm{FO}_{q+1}$ on arithmetical structures for every $q\in \mathbb{N}$
• Algorithm for Relatively Small Planted Clique with Small Edge Probability
• Ladner Theorem in Parameterized Complexity Theory
• Undergraduate Thesis, supervised by Prof. Yijia Chen, 2014
• We use finite injury priority method to prove that there are infinitely many $\mathrm{W[1]}$ problems that are neither $\mathrm{W[1]}$-Complete nor $\mathrm{FPT}$ if $\mathrm{FPT} \neq \mathrm{W[1]}$, presenting a "complete" proof which is more accessible to people not well-versed in recursion theory, compared with the original proof by Downey and Fellows

### Talks Given

 2017 Autumn Special Topics in Complexity Theory Foundations of Cryptography Spring Master's Thesis Defense 2016 Spring Master's Thesis Openning Defense 2015 Autumn Holographic Algorithms and Counting Complexity Spring Communication Complexity 2014 Autumn Advanced Topics on Computational Compleixty Summer Finite Injury Method Spring Kolmogorov Complexity

### Summer Schools, Conferences, and Workshops Participated

 2018 Feb. Workshop on Probabilistic and Extremal Combinatorics, Harvard Jan. Innovations in Theoretical Computer Science, MIT 2017 Nov. Workshop on Algebraic Methods in Combinatorics, Harvard Oct. Workshop on Additive Combinatorics, Harvard July Swedish Summer School in Computer Science, KTH 2016 Aug. China Theory Week, CUHK Summer School on Quantum Algorithms and Quantum Programming, GZU July Coalgebraic Methods for Automata, ECNU Highlights of Theoretical Computer Science, SHUFE May Chinese Mathematical Logic Conference, Fudan 2015 Aug. China Theory Week, SJTU July Logic Summer School in China, ZNU 2014 Aug. BASICS Summer School and Logic Summer School in China, SJTU June IMS Graduate Summer School in Logic, NUS May Annual Meeting of Asian Association for Algorithms and Computation, ZJU 2013 Sept. Asian Logic Conference, SYSU Aug. Summer School on Verification on Infinite State Systems, SJTU July Asian Initiative for Infinity (AII) Graduate Summer School, NUS