Ng Hiang Kwui黄炫圭

Me

a.k.a. Xuangui HuangIn P.R. China we are forced to use names in Hanyu Pinyin, a romanization system for Mandarin Chinese, as our legal English names, regardless of the actual native languages we speak.

PhD, Northeastern University

Emails: stslxg (at) gmail.com / ccs.neu.edu
Links:

I'm seeking a software engineering job in 2023.

I earned my PhD degree on Spring 2023 at Northeastern University. I worked on approximate degrees and circuit lower bounds, advised by Prof. Emanuele Viola.

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.

Fun Projects

Tech Blogs

My new blog, my very old blog in Chinese

Papers

  • Affine Extractors and AC0-Parity
    • with Peter Ivanov and Emanuele Viola
    • 26th International Conference on Randomization and Computation (RANDOM 2022)
    • manuscript, conference version
    • We show that good affine extractors can be computed by AC0-Xor circuits, by composing a linear transformation with resilient functions. We also show that one-sided extractor can be computed by small DNF-Xor circuits, and separate these circuits from other well-studied classes.
  • Average-case Rigidity Lower Bounds
    • with Emanuele Viola
    • 16th International Computer Science Symposium in Russia (CSR 2021)
    • Invited to the special issue of ACM Transactions on Computer Systems
    • manuscript, conference version, slides
    • We show that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\Pr_{x,y}[f(x,y)\neq M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently small $\delta > 0$.
  • Space Hardness of Solving Structured Linear Systems
    • 31st International Symposium on Algorithms and Computation (ISAAC 2020)
    • manuscript, conference version, slides
    • We show that if the probabilistic logarithmic-space solver or the deterministic nearly logarithmic-space solver for undirected Laplacian matrices can be extended to solve slightly larger subclasses of linear systems, then they can be use to solve all linear systems with similar space complexity.
    • Previously Kyng and Zhang proved similar results in the time complexity setting using reductions between approximate solvers. We prove that their reductions can be implemented using constant-depth, polynomial-size threshold circuits.
  • Approximate Degree, Weight, and Indistinguishability
    • with Emanuele Viola
    • ACM Transactions on Computation Theory, 2022, 14(1)
    • journal version, manuscript, slides for CCC'19 rump session
    • We prove that any symmetric funtions in $\mathsf{SYM}_{n,t}$ can be $\epsilon$-approximated with degree $O(k)$ and weight $2^{O(n(t+\log(1/\epsilon))/k)}$ for any $k \geq \sqrt{n(t+\log(1/\epsilon))}$, and it is tight for $k = (1-\Omega(1))n$.
    • We also prove tight approximatge degree-weight for $\mathsf{OR}$, upper bound for bounded-width $\mathsf{CNF}$, and related results for $(k,\delta)$-indistinguishability.
  • 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.

Other Academic Activities

Other Talks with Slides

2019 Spring Special Topics in Theoretical Computer Science
2018 Spring Machine Learning Project Presentation
2017 Fall Special Topics in Complexity Theory
Foundations of Cryptography
Spring Master's Thesis Defense
2016 Spring Master's Thesis Openning Defense
2015 Fall Holographic Algorithms and Counting Complexity
Spring Communication Complexity
2014 Fall Advanced Topics on Computational Compleixty
Summer Finite Injury Method
Spring Kolmogorov Complexity

Teaching Assistantships

2023 Spring CS 5800 Algorithms, Northeastern, for graduates
2022 Fall CS 5800 Algorithms, Northeastern, for graduates
Summer CS 5800 Algorithms, Northeastern, for graduates
Spring CS 5800 Algorithms, Northeastern, for graduates
2021 Summer CS 5800 Algorithms, Northeastern, for graduates
2020 Fall CS 5800 Algorithms, Northeastern, for graduates
2019 Fall CS 3000 Algorithms and Data, Northeastern, for undergraduates
2018 Summer CS 4800 Algorithms, Northeastern, for undergraduates
2016 Summer Theory of Computation, Fudan, for undergraduates
2015 Summer Advanced Algorithms, Fudan, for graduates
Spring Formal Semantics of Programming Languages, SJTU, for graduates
2014 Summer Advanced Algorithms, Fudan, for graduates
2013 Fall Algorithms, SJTU, for undergraduates

Boring Stuff

Flag Counter

© 2023. All rights reserved.