# Maruth Goyal

 pronounciation: MA-ruth email: maruth@cs.utexas.edu resume: resume blog: blog

## About

I am a senior majoring in Mathematics, and Computer Science in the Turing Scholars honors program at the University of Texas at Austin. I have broad interests in databases, and its intersection with cryptography, privacy-preserving algorithms, and program synthesis. I like working on practical ideas that are strongly rooted in theory. I do research as a part of the UT Networked Systems lab advised by Aditya Akella, and UToPiA group, advised by Işil Dillig . Outside of school, I enjoy playing the guitar a lot, and am a big fan of the Blues, and rock. I really like cooking (and eating) all sorts of food. I also quite like watching NBA.

I grew up in Noida in India, but also spent time living in Hyderabad, Pune, and Mountain View, CA.

## Teaching

#### Teaching Assistant: Honors Discrete Math CS311H Fall 2019, 2020

• Developed curriculum and assignments for Coq assignments (zip)
• Developed assignment to break Vigenere cipher, as application of math to CS.

## Awards

 SIGMOD Student Travel Award 2022 Undergraduate Research Fellow, UT Austin Spring 2020 2nd place, Albert A. Bennett Linear Algebra competition Fall 2019 Ajit B. Ramchandani endowed Presidential Scholarship 2018

## Lecture Notes

### Distributed Algorithms

Slides based on Nancy Lynch's textbook. TeX available on request.

## Talks

 Theory Thing Episode 5: P vs. NP and the Relativization Barrier pdf CS388T Project: Karp-Lipton Style Theorems pdf

## Some Projects

• (Spring 2021) Machine Unlearning
• Surveyed, and setup experiments to evaluate the current state of the art in Machine Unlearning.
• Provided first experimental evaluations for some algorithms, and attempted to compare them to theoretical guarantees.
• Used both toy, and real world data in order to evaluate and understand the settings in which different algorithms worked.
• Found certain algorithms to not be as useful in practice due combinations of poor performance, or extreme time and memory requirements.
• Implemented a general framework-agnostic set of abstractions and interfaces to make any ML model amenable to machine unlearning.
• (Spring 2020) Karp-Lipton Style Theorems
• Wrote a survey on the use of theorems in the style of the Karp-Lipton theorem , connecting lower bounds with non-uniform models of computation with bounds for uniform models.
• Karp and Lipton showed that $$\mathsf{NP} \subseteq \mathsf{P}/{\rm poly} \implies \mathsf{PH} = \Sigma_2$$. This was used by Kannan to show $$\Sigma_2 \not \subset \mathsf{SIZE}(n^k)$$ for all $$k > 0$$. Similarly Vinodachandran showed that $$\mathsf{PP} \not \subset \mathsf{SIZE}(n^k)$$, and utilized the Karp-Lipton style collapse $$\mathsf{NP} \subseteq \mathsf{P}/{\rm poly} \implies \mathsf{AM} = \mathsf{MA}$$ as well as $$\mathsf{NP} \subseteq \mathsf{P}/{\rm poly} \implies \mathsf{PP} = \mathsf{MA}$$.
• Remarkably, this style of theorems extends to the quantum realm as well, with Aaronson using it to show that $$\mathsf{PP}$$ doesn't have poly-size quantum circuits even with quantum advice. They utilize a "Quantum Karp-Lipton theorem", $$\mathsf{PP} \subseteq \mathsf{BQP}/{\rm qpoly} \implies \mathsf{CH} = \mathsf{MA}$$.
• Also investigated recent equivalence between Karp-Lipton collapses and superpolynomial lower bounds for $$\mathsf{P}^{\mathsf{NP}}$$ as shown by Lijie Chen, Dylan McKay, Cody Murray, and Ryan Williams.
• While these theorems generally escape the relativization and natural proofs barrier, they do not cross the algebraization barrier introduced by Aaronson and Wigderson .
• Report   |   slides
• (Fall 2019) Transactional Memory using Intel's TSX for OS
• Implemented an approximation of CxSpinlocks as in Rossbach et al. using TSX .
• Implementation attempts to use transactions to protect critical sections. In case of I/O or transaction start failure, or abort, automagically falls back to an interrupt-safe Spin Lock.
• Integrated into kernel built during the course by protecting the heap using a CxSpinLock.
• Ran experiments to measure fallback rate to spin locks, that demonstrated promise from using transactions.
• (Spring 2019) Static Type Inference
• Implemented an interpreter for a Simply Typed Lambda Calculus (SLTC) in Haskell.
• Implemented a variant of the Hindley-Milner type inference algorithm for static type inference for the SLTC
• Generated type constraints based on semantic rules, and solved using Robinson's unification algorithm.
• Code

## Coursework

### Fall 2021

• CS388H: Cryptography
• CS395T: Specification, Verification, and Specification of Distributed Systems

### Spring 2021

• CS395T: Foundations of Machine Learning and Data Science

### Fall 2020

• CS358H: Honors Quantum Information Science
• CS360V: Virtualization
• M367K: Topology
• Category Theory

### Spring 2020

• CS388T : Graduate Theory of Computation
• CS331: Algorithms and Complexity
• M373K: Algebraic Structures (Abstract Algebra)

### Fall 2019

• CS439H: Honors Operating Systems
• CS353: Theory of Computation
• M362K: Probability

### Spring 2019

• CS389L : Graduate Automated Logical Reasoning
• CS429H: Honors Computer Architecture
• M341H: Honors Linear Algebra
• M427JH: Honors Differential Equations

### Fall 2018

• CS314H : Honors Data Structures
• CS311H : Honors Discrete Mathematics
• M427LH: Honors Vector Calculus