Biography

I am a fifth-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.

During the time when I am not occupied with my main research, I tend to participate in Kaggle's Competitions on different types of 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.

Teaching Experience

• Teaching Fellow
  • CS630 - Graduates Algorithms (Fall 2021)
  • CS332 - Theory of Computation (Spring 2023, Fall 2023, 2024)
  • CS235 - Algebraic Algorithms (Spring 2021)
  • CS237 - Probability in Computing (Summer 2024)
  • CS132 - Geometric Algorithms (Summer 2022)
  • CS131 - Combinatoric Structures (Summer 2022, 2023)
• Grader
  • CS535 - Complexity Theory (Fall 2023)

Research Projects

• Algorithm Design
  • Finding Circuit Extensions For XOR in Polynomial Time. 2024
    • Joint work with Marco Carmosino and Tim Jackman
    • Description: we say an extension g of a total Boolean function f with m extra variables is simple, if we can take an optimal Boolean circuit C computing f and add m extra variables and logic gates to C in some way to construct an optimal circuit computing g. For this work, we consider the DeMorgan Basis (which allows AND, OR, and NOT gates only), and NOT-gates can be used for free. When f = XOR, the exclusive-OR function, then the decision problem of finding a simple extension for XOR is conjectured to be intractable which implies that this decision problem is a plausible candidate for proving NP-hardness of MCSP. In this work, we showed an efficient algorithm that decides the simple extension problem for XOR and ultimately rules out this decision problem as a candidate for solving the hardness mystery of MCSP once and for all. Thus, our algorithm formally raised another barrier on proving such hardness.
    • Under Submission to Computational Complexity Conference 2025 (CCC' 25). A set of slides presenting this work can be found here.
• Circuit Complexity
• A 2n + O(√n) tight-bound for the Multiplexer function. 2024
  • Joint work with Marco Carmosino and Tim Jackman
  • Description: In the early 19070s, the circuit lower-bound of 2n - O(1) was shown for the Multiplexer function (MUX), a Boolean function that commonly appears in practice, by Wolfgang Paul. In this work, we aim to improve this lower-bound to 2n + O(√n) which matches the best known upper-bound for Multiplexer shown by Peter Klein and M.S. Paterson in 1978.
  • Work in progress.
• Minimal XOR Circuits: The One True Shape is a Binary Tree. 2023
  • Joint work with: Marco Carmosino and Tim Jackman
  • Description: The Exclusive-OR function is one of the most fundamental Boolean functions that has appeared in many different contexts in both theory and practice. The circuit lower-bound of 3n - O(1) was shown for XOR by Claus-Peter Schnorr in 1974 under the DeMorgan Basis (which allows AND, OR, and NOT gates only), and NOT-gates can be used for free, and in this setting, XOR has a trivial matching upper-bound. In this work, we push our understanding of XOR further by characterizing the structure of optimal circuits computing XOR.
  • Unpublished Manuscript. This work was integrated with Finding Circuit Extensions For XOR in Polynomial Time. A set of slides presenting this work can be found here.
• Other Publications & Manuscripts
  • 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.

Selected Personal Projects

• Human Activity Recognition Using Deep Learning: Built a deep learning pipeline using Python and PyTorch to classify human activities from Wi-Fi CSI data, achieving 0.98 accuracy score with a custom CNN-LSTM model. The Dataset for Human Activity Recognition using Wi-Fi Channel State Information (CSI) data can be found here. Github Link
• Churn Predictor for Subscription Services: 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 : 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

• Neural Networks and Deep Learning
• IBM Data Science Professional Certificate

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