8 papers
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
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 probability distribu…
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 with nodes, hyperedges, and rank , an…
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…
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 in a disc…
Perfect Sampling in Turnstile Streams Beyond Small Moments
David P. Woodruff, Shenghao Xie, Samson Zhou
Given a vector induced by a turnstile stream , a non-negative function , a perfect -sampler outputs an index with proba…