David P. Woodruff

collaborators

Showing cs.DSShow all

6 papers · 1 filter

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.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.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…