# Ng Hiang Kwui黄炫圭

a.k.a.

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.

## 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.