Ng Hiang Kwui黄炫圭

a.k.a.

Former MSc. Student
Department of Computer Science and Engineering
Shanghai Jiao Tong University

Recently I obtained my master's degree advised by Prof. Yijia Chen. I will join Northeastern University this fall to pursuit my Ph.D. with Prof. Emanuele Viola. I have great enthusiasm for theoretical computer science, especially computational complexity. Currently, my research focuses on parameterized complexity, circuit complexity, and descriptive complexity. Besides, I had done some research work on correlation decay, recursion theory, and equivalence checking. I love to explore a wide range of , to learn some latest big results/frameworks such as SoS, and to attack challenging open problems.

Papers

• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank
• with Yijia Chen and Joerg Flum, Manuscirpt
• 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

Reading Seminars Attended and Talks Given

 2016 Autumn Quantum Computation and Quantum Information Sum of Squares Algorithms and Lower Bounds Spring An Average-Case Depth Hierarchy Theorem for Boolean Circuits 2015 Autumn Holographic Algorithms and Counting Complexity Spring Communication Complexity 2014 Autumn Advanced Topics on Computational Compleixty Analysis of Boolean Functions Summer Finite Injury Method Spring Kolmogorov Complexity 2013 Autumn Statistical Physics and Algorithms 2012 Autumn Approximation Algorithms Summer Formal Verification and Automata Theory

Summer Schools and Conferences Participated

 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