5 papers
Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scale
Siddharth Gollapudi, Nilesh Gupta, Prasann Singhal +1
Language models (LMs) raise an intriguing alternative to vector-based retrieval: conditioning on an in-context corpus and directly generating a relevant answer. However, prior work…
Improved Approximations for Hard Graph Problems using Predictions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the…
Learning-Augmented Frequent Directions
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi +2
An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the st…
Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
Given a set of vectors in , the goal of the \emph{determinant maximization} problem is to pick vectors with the maximum volume. Determinant maximization is th…
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints
Varun Suriyanarayana, Varun Sivashankar, Siddharth Gollapudi +1
The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, not…