Ng Hiang Kwui黄炫圭

I'm an AI Developer Technology Engineer at NVIDIA.

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

• Recently I'm porting the discontinued duolingo status GNOME shell extension (which I also contributed to some time ago) to GNOME 42: repo.
• In 2019, with David Stalfa, for our CS7610 course project we implemented Raft in Python 3.6 to build a distributed, replicated key-value store: repo, proposal, report, presentation. I implemented most of the server-side functionalities, and we made some nice demo videos: general demo, voted as runners-up in the presentations. I believe at that time this was the second Python implementation of Raft that supports membership changes and uses asyncio.
• In 2019 I modified the code from the openweather extension in GNOME shell to add support for showing hourly forecasts for the next 12 hours using data from DarkSky: repo.
• In 2014 for my E-commerce course project and also to learn Javascript I wrote a small demo website using AngularJS and AngularFire: repo.
• In 2012, based on TORCS (The Open Racing Car Simulator), I developed CyberTORCS, an autonomous driving simulation platform with scoring systems for racing, chasing, and parking: release version, report (in Chinese). It is still being used on undergraduate control theory labs in 2022: video.
• In 2011, together with two teammates I built an autonomous model racing car, using mini camera to capture image of the track and microprocessor to process and control the car: photo, source codesIDE: CodeWarrior for DSC56800E v8.3
  MCU+DSP: MC56F8366
  TVP5146, SN74V235, BTS7960, MAX6954, etc., utility programs (C, Python), repo, report (in Chinese), video 1, 2. We won the first prize in the national competition. I took full responsibility for the final drifting!

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
  • in Chinese, Journal of Shanghai Jiao Tong University, 2017, 51(10)
  • introductory slides, Chinese manuscriptUnfortunately due to rights restriction, I cannot put my Chinese manuscript here, English draft
  • Using the generalized planted model $\mathcal{G}(n, p(n), k(n))$, we extend the analysis in the paper of Feige and Ron to the cases where $p(n) = o(1)$ but not-that-smallIf we write $p(n)$ as $p(n) = n^{-\alpha(n)}$, then we require $\lim_{n \to \infty} \alpha(n) = 0$. (otherwise the problem becomes trivial), proving that in such cases we can find the planted clique of size $\Theta(\sqrt{n \cdot p(n) \cdot (1-p(n))}) = o(\sqrt{n})$.
  • This result is a by-product of my research on circuit lower bounds for generalized planted clique problem against $\mathrm{AC}^0[p]$.
• 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

Teaching Assistantships

Boring Stuff

• Born and grown up in Swatow, I'm very proud to be TeochewFor ambiguities of the term "Chinese", see this paper. . I can speak TeochewTeochew is also very different from Mandarin Chinese., Cantonese, Mandarin Chinese, English, and some French.
• I love painting. Here are some of my paintings (Chinese Painting, Gouache) in my early years: 1, 2, 3, 4, 5, 6, 7, 8 (However, as you can see, I'm not good at Chinese Calligraphy); some handcraftings: 1, 2.
• I have been a fan of Jamie Oliver since secondary school: thanks to TVB Pearl, I watched the interesting Oliver's Twist TV show.
• I used to be very active in programming contests in my secondary schools. I had won first prizes in NOIp for four times.

Boring Links

• A bad day writing code in Scheme is better than a good day writing code in C. by David Stigant, spread by Matthias Felleisen
• Graphical Linear Algebra, The Logic Blog front-end
• Lisp Machine, Lisp Machine Manual, Symbolics, Stack Computers, Homebrew Computers
• Oskar's Puzzles
• It's Robot Fighting Time! 3,2,1,Activate! Robomaster
• My Correct Views on Everything
• A Time for Choosing