# Maruth Goyal

 pronounciation: MA-ruth email: maruth@cs.utexas.edu resume: resume blog: blog social: Twitter , GitHub

## About

I am a sophomore majoring in Mathematics, and Computer Science in the Turing Scholars honors program at the University of Texas at Austin. My interests lie in Program Analysis, and Synthesis. I do research as a part of the UToPiA group, advised by Işil Dillig . I also have an interest in complexity theory. 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.

## Teaching

• Teaching Assistant: Honors Discrete Math (CS311H) (Fall 2019)

## Awards

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

## Some Projects

• (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

## Talks

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

## Coursework

• 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