5 papers
On Extensions of the Unanimous Vote Problem
Evan J. R. Brody, Haya Diwan, Lisa Hellerstein +1
The Unanimous Vote problem is to determine a fixed order in which to flip each of biased coins, where each coin can be flipped only once, such that the expected number of flips…
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
Haya Diwan, Lisa Hellerstein, Nicole Megow +1
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values o…
SimKey: A Semantically Aware Key Module for Watermarking Language Models
Shingo Kodama, Haya Diwan, Lucas Rosenblatt +2
The rapid spread of text generated by large language models (LLMs) makes it increasingly difficult to distinguish authentic human writing from machine output. Watermarking offers a…
Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou +3
Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have…
Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Haya Diwan, Jinrui Gou, Cameron Musco +2
There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional…