Mandar Juvekar's Homepage

This page is quite out of date, and does not contain my most recent research interests and publications. I am planning to update this page in the next month or so.

A summary of my research by topic. Click black links for descriptions.

Structural Complexity Theory

With Lane Hemaspaandra, Arian Nadjimzadah, and Patrick Phillips, I used the iterative constant-setting method in complexity theory to show broad containments between ambiguity-limited and restricted counting classes.
[see more/less]

We proved two flexible meta-theorems that can be used to prove containments between various ambiguity-limited NP classes and restricted counting classes based on sets with known density bounds. We also applied these meta-theorems to prove containments of that sort. Additionally, as a corollary of our work, we showed that the Lenstra-Pomerance-Wagstaff Conjecture (a widely believed conjecture about the Mersenne primes) implies that all sets with O(log log n)-ambiguity NP sets are in the restricted counting class defined by the primes.

Natural Language Understanding

Unscoped Logical Forms (ULFs) are an underspecified representation for naturally capturing the semantic type structure of language within the framework of Episodic Logic. I have worked on the ULF project as part of Len Schubert's group since my freshman spring.

The ULF type system
I implemented a robust Lisp library to work with ULF semantic types and their composition during the summer of 2019. The libary is available here (admittedly, it is quite different now from when I wrote it a few years ago).
Monotonic inference on ULFs
With Gene Kim, I formulated a theoretical system for performing monotonic inference on ULF, and established a correspondence between inference rules of scope-resolved Episodic Logic and the natural logic treatment by Sánchez Valencia. Subsequently, with Junis Ekmekciu and Viet Duong, we implemented our system and ran experiments.
ULF Sampling
One active research area related to ULF is to build a neural net based parser to parse English sentences into ULF. A major impediment to building such a parser is the lack of a large ULF datasets. The goal of this project (which is planned to be my senior thesis) is to use previously annotated sentences (English-ULF pairs) as a seed to generate random (hopefully coherent) ULFs. The hope is that with such a ULF sampler, one can start with a small hand-annotated dataset, and then automatically grow it via sampling.
The ULF project website maintained by Gene Kim.

Combinatorics

Distinct Distances in Non-Euclidean Metrics
I was part of the Polymath REU where, along with my group, I studied Erdős's distinct distances problem in non-Euclidean metrics. We improved a known bound in the ℓ_p metric setting, and characterized optimal configurations in the ℓ₁ and ℓ_∞ settings.
Analytic Methods in Combinatorics
In 2019, with Alex Iosevich, I studied the polynomial method in combinatorics and its applications to geometric problems like the finite field Kakeya problem and the Erdős distinct distances problem. In 2021, with Nathanael Grand and Maxwell Sun, I studied applications of discrete Fourier analysis in bounding the VC dimension of certain functions in finite-field vector spaces.
The Carbery Rectangle Problem
I did a SURF at Caltech where I applied graph-theoretic methods to the Carbery Rectangle Problem in combinatorics and found a new proof for the known bound for the problem on a class of special cases parameterized by graphs. Details can be found in my final report.

Publications

Distinct Distances with ℓ_p Metrics [link]

Polly Matthews Jr. Computational Geometry, 100:101785, 2022. Written as part of the Polymath REU 2020, and published under a pseudonym.

A (Mostly) Symbolic System for Monotonic Inference with Unscoped Episodic Logical Forms [pdf]

Gene Kim, Mandar Juvekar, Junis Ekmekciu, Viet Duong, and Lenhart Schubert. In Proceedings of the 1st and 2nd Workshops on Natural Logic Meets Machine Learning (NALOMA), pages 71-80. Association for Computational Linguistics, June 2021.

Monotonic Inference for Underspecified Episodic Logic [pdf, slides]

Gene Kim, Mandar Juvekar, Junis Ekmekciu, Viet Duong, and Lenhart Schubert. In Proceedings of the 1st and 2nd Workshops on Natural Logic Meets Machine Learning (NALOMA), pages 26-40. Association for Computational Linguistics, June 2021.

Preprints and Technical Reports

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting [arXiv]

Lane Hemaspaandra, Mandar Juvekar, Arian Nadjimzadah, and Patrick Phillips. Technical Report arXiv:2109.14764 [cs.CC], September 2021. Submitted to conference.

On Arroyo-Figueroa’s Proof that P ≠ NP [arXiv]

Mandar Juvekar, David Narváez, and Melissa Welsh.
Technical Report arXiv:2103.15246 [cs.CC], March 2021.