Publications (32)
Streaming Algorithms for Support-Aware Histograms
Justin Y. Chen, Piotr Indyk, Tal Wagner
Histograms, i.e., piece-wise constant approximations, are a popular tool used to represent data distributions. Traditionally, the difference between the histogram and the underlyin…
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5
We consider the problem of determining the maximal such that every matching of size (or at most ) in a bipartite graph contains an induced matching of…
Towards Resistance Sparsifiers
Michael Dinitz, Robert Krauthgamer, Tal Wagner
We study resistance sparsification of graphs, in which the goal is to find a sparse subgraph (with reweighted edges) that approximately preserves the effective resistances between…
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3
An -approximate quantile sketch over a stream of inputs approximates the rank of any query point - that is, the number of input points less than - up to an…
Frustratingly Simple Black-Box Adaptation of Language Models via Logit Bias
Ofek I. Cohen, Lior Shani, Aviv Rosenberg +3
Many organizations aim to adapt language models for internal use, both to improve performance on domain-specific tasks and to address privacy concerns around sensitive data. Howeve…
Scalable Nearest Neighbor Search for Optimal Transport
Arturs Backurs, Yihe Dong, Piotr Indyk +2
The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity…