First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
Bender, Mart´ ın Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
verdicts
UNVERDICTED 5representative citing papers
Presents a space-efficient lock-free linear-probing hash table with wait-free lookups, linearizable operations, and amortized complexity matching sequential linear probing under no concurrent same-key insertions.
Aggregation mechanisms for surjective classifications are nearly dictatorial with high probability unless functions are nearly constant, with a full characterization of always-surjective mechanisms.
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
1D translation-invariant Gibbs states at positive temperature exhibit superexponential decay of Belavkin-Staszewski conditional mutual information, enabling efficient learning from local measurements and tensor network approximations.
citing papers explorer
-
Adversarially Robust Approximate Furthest Neighbor
First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
-
Space-Efficient Lock-Free Linear-Probing Hash Table
Presents a space-efficient lock-free linear-probing hash table with wait-free lookups, linearizable operations, and amortized complexity matching sequential linear probing under no concurrent same-key insertions.
-
Classification aggregation: a quantitative impossibility theorem
Aggregation mechanisms for surjective classifications are nearly dictatorial with high probability unless functions are nearly constant, with a full characterization of always-surjective mechanisms.
-
Fast mixing of all-to-all quantum systems at high temperatures
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
-
Conditional Independence of 1D Gibbs States with Applications to Efficient Learning
1D translation-invariant Gibbs states at positive temperature exhibit superexponential decay of Belavkin-Staszewski conditional mutual information, enabling efficient learning from local measurements and tensor network approximations.