250 citations · 1.1k across the 76 of their papers we have counts for
7 papers · 1 filter
Multi-Party Set Reconciliation Using Characteristic Polynomials
Anudhyan Boral, Michael Mitzenmacher
In the standard set reconciliation problem, there are two parties and , each respectively holding a set of elements and . The goal is for both parties to obta…
Hardness of Peeling with Stashes
Michael Mitzenmacher, Vikram Nathan
The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are remo…
Theoretical Foundations of Equitability and the Maximal Information Coefficient
Yakir A. Reshef, David N. Reshef, Pardis C. Sabeti +1
The maximal information coefficient (MIC) is a tool for finding the strongest pairwise relationships in a data set with many variables (Reshef et al., 2011). MIC is useful because…
Space Lower Bounds for Itemset Frequency Sketches
Edo Liberty, Michael Mitzenmacher, Justin Thaler +1
Given a database, computing the fraction of rows that contain a query itemset or determining whether this fraction is above some threshold are fundamental operations in data mining…
Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket
David Eppstein, Michael T. Goodrich, Michael Mitzenmacher +1
We study wear-leveling techniques for cuckoo hashing, showing that it is possible to achieve a memory wear bound of after the insertion of items into a table…
Coding for Random Projections and Approximate Near Neighbor Search
Ping Li, Michael Mitzenmacher, Anshumali Shrivastava
This technical note compares two coding (quantization) schemes for random projections in the context of sub-linear time approximate near neighbor search. The first scheme is based…