Biography
I am a sixth-year Ph.D. student at the Department of Computer Science at Boston University, currently advised by Prof. Steven Homer. In general, I am interested in Computational Complexity Theory and Algorithm Design. My research focuses on Circuit Complexity and Meta-Complexity. In particular, I study the mysterious Minimum Circuit Size Problem (MCSP) and focus on proving some barriers on proving its hardness as well as its connections with other topics in Theoretical Computer Science.
I am expected to graduate in May 2026 and on the job market. I am open to postdoc as well as lecturer positions. You can find my Research Statement here, and my Teaching Statement here.
During the time when I am not occupied with my main research, I tend to participate in Kaggle's and Coursera's challenges on different types of problems such as regression, text classifying, etc. to self-study and enhance my basic knowledge in Machine Learning and Data Science. Visit my Github (link above) for the full collection of side projects I have done. Some are listed below.
In May 2020, I received a B.A. with Summa Cum Laude and High Honors in Computer Science from Clark University where I was advised by
Prof. Frederick Green. I did some research on Human-Computer Interaction (HCI) during
my undergraduate study under the guidance of Prof. John Magee.
Research Projects
- Work In Progress
- On tightening the Lower bound of Multiplexer (MUX). 2024
- Description: In the early 19070s, the circuit lower-bound of 2n - O(1) was shown for the single-output Multiplexer function (MUX), a Boolean function that commonly appears in practice, by Wolfgang Paul.
In this work, we aim to improve this lower-bound as close as possible to 2n + O(√n), the best known upper-bound for Multiplexer shown by Peter Klein and M.S. Paterson in 1978.
- Work in progress. Joint with Marco Carmosino and Tim Jackman.
- A preprint of what we have discovered so far about MUX can be found here.
- Characterizing the Minimal Circuits for Equality Testing (EQ) function. 2025
- Description: given two input strings x and y, both of length n, we define EQ_n(x, y) = 1 iff x = y, the Boolean function that tests the equality of x and y. This function has a lower bound of 4n - 1 and a matching upper bound (Wegener, 1987). In this work, we aim to characterize the optimal circuits computing EQ_n that obeys its known tight bound.
- Work in progress. Joint with Tim Jackman.
- A preprint will be available soon.
- Publications & Manuscripts
- Marco Carmosino, Ngu Dang, Tim Jackman. 2024. Simple Circuit Extensions for XOR in PTIME.
To appear in STACS 2026. A preprint is available here.
- Marco Carmosino, Ngu Dang, Tim Jackman. 2023. Formalizing Gate Elimination via Term Graphs Rewriting
. To be submitted to FSCD 2026. A preprint is available here.
- Marco Carmosino, Ngu Dang, Fabian Spaeh. 2021. A Survey on Hardness of MCSP. A preprint is available here.
- Mariah Papy, Duncan Calder, Ngu Dang, Aidan McLaughlin, Breanna Desrochers, and John Magee.
2019. Simulation of Motor Impairment with “Reversed Angle Mouse”
in Head-Controlled Pointer Fitts’ Law Task. In Proceedings of the 21st International ACM SIGACCESS
Conference on Computers and Accessibility (ASSETS’19). ACM, Pittsburgh, PA, USA, 545-547.
Teaching Experience
- Teaching Fellow
- CS630 - Graduates Algorithms (Fall 2021)
- CS332 - Theory of Computation (Spring 2023, Fall 2023, 2024)
- CS237 - Probability in Computing (Summer 2024)
- CS235 - Algebraic Algorithms (Spring 2021, Fall 2025)
- CS132 - Geometric Algorithms (Summer 2022)
- CS131 - Combinatoric Structures (Summer 2022, 2023)
- Grader
- CS535 - Complexity Theory (Fall 2023)
Selected Personal Projects
- Tweet Dialect Classifier: Built a dialect classifying pipeline in Python with BERTweet-based model that distinguishes African American Vernacular English from Standard and regular African American English and achieved 0.95, 0.99, and 0.97 for accuracy, recall, and F1 score respectively. Integrated the classifier into a bias-aware sentiment analysis pipeline, with statistical analysis to provide insights on fairness in interpretation of social media text across different models (i.e. RoBERTa, RoBERTa-Latest, BERTweet). Github Link.
- Human Activity Recognition Using Deep Learning: Built a deep learning pipeline using Python and PyTorch to classify human activities from Wi-Fi Channel State Information (CSI) data, achieving 0.98 accuracy score with a custom CNN-LSTM model. The Human Activities via Wi-Fi CSI dataset can be found here. Github Link.
- Churn Predictor for Subscription Services (Coursera's Challenge): Implemented an end-to-end churn prediction pipeline in Python for a video streaming service using a real-world imbalanced subscription dataset using an ensemble of three models — a neural network, XGBoost, and Random Forest — using weighted soft voting to optimize class ranking and maximize AUC. Github Link.
- Edible Mushroom Classifier (Kaggle's Challenge): Implemented a Random Forest model classifying edible mushrooms from toxic ones based on physical characteristics. The dataset used in this project (train and test) was generated from a deep learning model trained on the UCI Mushroom dataset . The training set contains 3116945 data points; the test set contains 2077964 data points, with 22 features. The model achieved an accuracy score of 0.987. Github Link .
Certifications
Academic Awards
- Outstanding Academic Achivement. Issued by Department of Mathematics & Computer Science
- Clark University, May 2020
- Phi Beta Kappa Membership. Issued by Phi Beta Kappa
- Lambda of Massachusetts at Clark University, May 2020
