David P. Woodruff

collaborators

8 papers

cs.DS2025

Combinatorial Optimization using Comparison Oracles

Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7

In linear combinatorial optimization, we aim to find $S^{*} = ar g min_{S \in F} ⟨ w, 1_{S} ⟩$ for a family $F \subseteq 2^{U}$ over a ground set…

cs.DS2025

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams

Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie +1

We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H = (V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$ , an…

cs.DS2025

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph

Gautam Kamath, Alireza F. Pour, Matthew Regehr +1

We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distribu…

cs.DS2025

Multipass Linear Sketches for Geometric LP-Type Problems

N. Efe Çekirge, William Gay, David P. Woodruff

LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…

cs.CG2025

Range Counting Oracles for Geometric Problems

Anne Driemel, Morteza Monemizadeh, Eunjin Oh +2

In this paper, we study estimators for geometric optimization problems in the sublinear geometric model. In this model, we have oracle access to a point set with size $n$ in a disc…

cs.DS2025

Perfect Sampling in Turnstile Streams Beyond Small Moments

David P. Woodruff, Shenghao Xie, Samson Zhou

Given a vector $x \in R^{n}$ induced by a turnstile stream $S$ , a non-negative function $G : R \to R$ , a perfect $G$ -sampler outputs an index $i$ with proba…

cs.LG2025

Communication Bounds for the Distributed Experts Problem

Zhihao Jia, Qi Pang, Trung Tran +3

In this work, we study the experts problem in the distributed setting where an expert's cost needs to be aggregated across multiple servers. Our study considers various communicati…

cs.DS2024

Learning Multiple Secrets in Mastermind

Milind Prabhu, David Woodruff

In the Generalized Mastermind problem, there is an unknown subset $H$ of the hypercube ${0, 1}^{d}$ containing $n$ points. The goal is to learn $H$ by making a few queries to an ora…