About

Aditya Bhaskara is an Associate Professor at the Kahlert School of Computing at the University of Utah. His research interests include algorithms, specifically approximation and online algorithms, as well as graph algorithms. He also focuses on artificial intelligence, particularly machine learning theory and modeling. His work involves developing and analyzing algorithms to solve complex computational problems, contributing to the fields of theoretical computer science and artificial intelligence.

Research topics

• Computer Science
• Machine Learning
• Artificial Intelligence
• Algorithm
• Computational biology
• Biology
• Mathematics
• Genetics
• Statistics
• Theoretical computer science
• Mathematical optimization

Selected publications

• Guessing Efficiently for Constrained Subspace Approximation

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  In this paper we study constrained subspace approximation problem. Given a set of n points {a₁,…,a_n} in ℝ^d, the goal of the subspace approximation problem is to find a k dimensional subspace that best approximates the input points. More precisely, for a given p ≥ 1, we aim to minimize the pth power of the 𝓁_p norm of the error vector (‖a₁-Pa₁‖,…,‖a_n-Pa_n‖), where P denotes the projection matrix onto the subspace and the norms are Euclidean. In constrained subspace approximation (CSA), we additionally have constraints on the projection matrix P. In its most general form, we require P to belong to a given subset 𝒮 that is described explicitly or implicitly. We introduce a general framework for constrained subspace approximation. Our approach, that we term coreset-guess-solve, yields either (1+ε)-multiplicative or ε-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to fair subspace approximation, k-means clustering, and projected non-negative matrix factorization, among others. Specifically, while we reconstruct the best known bounds for k-means clustering in Euclidean spaces, we improve the known results for the remainder of the problems.

  PublisherOA PDFDOI

• Online Distributed Queue Length Estimation

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapter1st authorCorresponding

  Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server’s real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes.

  PublisherDOI

• An Efficient Sparse Fine-Tuning with Low Quantization Error via Neural Network Pruning

  arXiv (Cornell University) · 2025-02-17

  preprintOpen accessSenior author

  Fine-tuning is an important step in adapting foundation models such as large language models to downstream tasks. To make this step more accessible to users with limited computational budgets, it is crucial to develop fine-tuning methods that are memory and computationally efficient. Sparse Fine-tuning (SpFT) and Low-rank adaptation (LoRA) are two frameworks that have emerged for addressing this problem and have been adopted widely in practice. In this work, we develop a new SpFT framework, based on ideas from neural network pruning. At a high level, we first identify ``important'' neurons/nodes using feature importance metrics from network pruning (specifically, we use the structural pruning method), and then perform fine-tuning by restricting to weights involving these neurons. Experiments on common language tasks show our method improves SpFT's memory efficiency by 20-50\% while matching the accuracy of state-of-the-art methods like LoRA's variants.

  PublisherOA PDFDOI

• Online Distributed Queue Length Estimation

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapter1st authorCorresponding

  Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server’s real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes.

  PublisherDOI

• Online Distributed Queue Length Estimation

  ArXiv.org · 2025-04-25

  preprintOpen access1st authorCorresponding

  Queue length monitoring is a commonly arising problem in numerous applications such as queue management systems, scheduling, and traffic monitoring. Motivated by such applications, we formulate a queue monitoring problem, where there is a FIFO queue with arbitrary arrivals and departures, and a server needs to monitor the length of a queue by using decentralized pings from packets in the queue. Packets can send pings informing the server about the number of packets ahead of them in the queue. Via novel online policies and lower bounds, we tightly characterize the trade-off between the number of pings sent and the accuracy of the server's real time estimates. Our work studies the trade-off under various arrival and departure processes, including constant-rate, Poisson, and adversarial processes.

  PublisherOA PDFDOI

• Bridging Data Gaps: Enhancing Wireless Localization with Physics-Informed Data Augmentation

  Proceedings of the ACM on Networking · 2025-11-24

  articleOpen access

  Machine learning (ML) models have emerged as the state-of-the-art approach for wireless applications such as transmitter localization. One of the challenges for ML models, however, is their reliance on the abundance of high quality data. Specifically for localization, a significant challenge is to obtain training data that ''covers'' the entire landscape, in order to ensure a high accuracy for the ML approaches. This issue is compounded when trying to localize multiple transmitters. To address this problem, we introduce a new data augmentation pipeline, termed Physics-informed Augmentation and RF Modeling (PhARMNet), that can combine existing data with a physics-based simulation model, producing a larger dataset with an improved coverage of the landscape of interest. Our results show that PhARMNet offers significant advantages over traditional path loss models. For localization, we demonstrate that augmenting training data with PhARMNet-produced samples improves localization accuracy, particularly in out-of-distribution regions and multi-transmitter settings.

  PublisherDOI

• New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries

  arXiv (Cornell University) · 2024-05-02

  preprintOpen access1st authorCorresponding

  We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by polynomials of a few underlying base random variables. This setting captures a core technical challenge for obtaining smoothed analysis guarantees in many algorithmic settings. Least singular value bounds often involve showing strong anti-concentration inequalities that are intricate and much less understood compared to concentration (or large deviation) bounds. First, we introduce a general technique involving a hierarchical $ε$-nets to prove least singular value bounds. Our second tool is a new statement about least singular values to reason about higher-order lifts of smoothed matrices, and the action of linear operators on them. Apart from getting simpler proofs of existing smoothed analysis results, we use these tools to now handle more general families of random matrices. This allows us to produce smoothed analysis guarantees in several previously open settings. These include new smoothed analysis guarantees for power sum decompositions, subspace clustering and certifying robust entanglement of subspaces, where prior work could only establish least singular value bounds for fully random instances or only show non-robust genericity guarantees.

  PublisherOA PDFDOI

• On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models

  arXiv (Cornell University) · 2024-12-18

  preprintOpen access1st authorCorresponding

  In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from certain probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify classes of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in these classes spectral bisection with the _normalized_ Laplacian outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.

  PublisherOA PDFDOI

• Applications of Exosomes in Cancer Therapy

  2024-01-06

  preprintOpen access1st authorCorresponding

  This systematic review explores the field of utilizing exosomes for cancer therapy, providing a comprehensive analysis of their mechanisms, applications, advantages, and limitations.Exosomes, specialized extracellular vesicles, demonstrate promising attributes as potential vehicles for drug delivery due to their biocompatibility, immunotolerance, and ability to traverse biological barriers.The review categorizes exosomes based on their in vivo sources, including milk, dendritic cells, mesenchymal stem cells, erythrocytes, and tumor cells, elucidating the unique advantages and challenges associated with each type.Additionally, the study delves into various exosome-loading techniques such as transfection, incubation, and electroporation.The clinical implications of exosomes as cancer biomarkers are detailed, including their role in early detection and diagnosis through exosomal RNA and protein analysis.Despite the promising potential, the review also highlights existing challenges in industrial-scale production, standardization, and long-term biosafety.Finally, the paper outlines future research directions aimed at refining exosome-based therapies, addressing existing limitations, and realizing their full therapeutic potential against cancer.

  PublisherOA PDFDOI

• Optimizing Probabilistic Propagation in Graphs by Adding Edges

  arXiv (Cornell University) · 2024-07-02 · 1 citations

  preprintOpen access1st authorCorresponding

  Probabilistic graphs are an abstraction that allow us to study randomized propagation in graphs. In a probabilistic graph, each edge is "active" with a certain probability, independent of the other edges. For two vertices $u,v$, a classic quantity of interest, that we refer to as the proximity $\mathcal{P}_{G}(u, v)$, is the probability that there exists a path between $u$ and $v$ all of whose edges are active. For a given subset of vertices $V_s$, the reach of $V_s$ is defined as the minimum over pairs $u \in V_s$ and $v \in V$ of the proximity $\mathcal{P}_{G}(u,v)$. This quantity has been studied in the context of multicast in unreliable communication networks and in social network analysis. We study the problem of improving the reach in a probabilistic graph via edge augmentation. Formally, given a budget $k$ of edge additions and a set of source vertices $V_s$, the goal of Reach Improvement is to maximize the reach of $V_s$ by adding at most $k$ new edges to the graph. The problem was introduced in earlier empirical work in the algorithmic fairness community. We provide the first approximation guarantees and hardness results for Reach Improvement. We prove that the existence of a good augmentation implies a cluster structure for the graph. We use this structural result to analyze a novel algorithm that outputs a $k$-edge augmentation with an objective value that is poly($β^*$), where $β^*$ is the objective value for the optimal augmentation. We also give an algorithm that adds $O(k \log n)$ edges and yields a multiplicative approximation to $β^*$. Our arguments rely on new probabilistic tools for analyzing proximity, inspired by techniques in percolation theory; these tools may be of broader interest. Finally, we show that significantly better approximations are unlikely, under known hardness assumptions related to gap variants of the classic Set Cover problem.

  PublisherOA PDFDOI

Recent grants

• AF: Small: Online Algorithms and Approximation Methods in Learning

  NSF · $350k · 2020–2024

Frequent coauthors

• Aravindan Vijayaraghavan

  26 shared

• Moses Charikar

  Stanford University

  16 shared

• Sneha Kumar Kasera

  12 shared

• Ashok Cutkosky

  9 shared

• Morteza Zadimoghaddam

  9 shared

• Frost Mitchell

  University of Utah

  9 shared

• Manish Purohit

  Google (United States)

  9 shared

• Neal Patwari

  Washington University in St. Louis

  8 shared