Pith. sign in

REVIEW 5 minor 300 references

Learning Partition Trees for Nearest Neighbor Search

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read If a perfect balanced halfspace tree exists for a query distribution with Gaussian-like marginals, a poly-time algorithm learns a data structure that answers exact nearest-neighbor queries in o(nd) time.

desk verdict Solid theory paper: hardness + improper √OPT PTF learner + Dasgupta-style tree charging that yields the first poly-time o(nd) exact NNS under a perfect halfspace-tree promise and Gaussian-like marginals. read the letter →

arxiv 2607.09909 v1 pith:SDIQOYEY submitted 2026-07-10 cs.DS cs.LG

Sanjeev Khanna , Ashwin Padaki , Erik Waingarten This is my paper · ORCID
classification cs.DScs.LG MSC 68W4068Q2568T05
keywords nearestneighborsearchdata-drivenalgorithmdesignbalancedhalfspacetreespolynomialthresholdfunctionsimproperlearninghierarchicalclusteringCheegerroundingsemidefiniteprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Nearest-neighbor search is usually designed for worst-case data and queries. This paper instead treats the problem as data-driven algorithm design: given a fixed dataset and sample access to the actual query distribution, learn a partition tree that is optimized for that distribution. The target class is balanced halfspace trees, a natural abstraction of space-partitioning methods such as locality-sensitive hashing. The central algorithmic primitive is the balanced halfspace cut problem: find a halfspace that separates few query-neighbor pairs while keeping the two sides roughly equal in size. Properly learning the optimal halfspace is NP-hard, so the authors give an improper learner that returns a low-degree polynomial threshold function whose cut error is only the square root of the optimum. Under Gaussian-like anticoncentration and sub-Gaussianity assumptions that let halfspaces (and unions of intersections of halfspaces) be approximated by low-degree polynomials, recursively applying this cut learner produces a tree whose search cost is o(nd) whenever a perfect halfspace tree exists. A sympathetic reader cares because the result supplies the first theoretical guarantee that sample access to queries can be converted into a sublinear exact nearest-neighbor structure for a concrete, practically motivated class of partitions.

What carries the argument

The balanced halfspace cut problem and its improper solver PolyCut: an SDP relaxation of an energy-plus-kurtosis program over degree-k polynomials, followed by Gaussian rounding and Cheeger-style thresholding, that returns a balanced PTF of error O(sqrt(OPT+ε)).

What would settle it

Construct a concrete distribution over nearest-neighbor pairs that admits a perfect balanced halfspace tree yet whose marginals fail the anticoncentration or moment conditions of Definition B.1, then check whether any low-degree PTF tree recovered by the algorithm still achieves o(nd) query cost.

Watch

Extended reading notes

Core claim

Whenever a dataset of size n in polylogarithmic dimension admits a perfect 1/3-balanced halfspace tree for a nearest-neighbor pair distribution whose marginals satisfy Gaussian-like anticoncentration and sub-Gaussianity, there is a polynomial-time algorithm that, from samples of that distribution, builds an O(nd)-space data structure returning the true nearest neighbor in o(nd) query time with high probability.

Load-bearing premise

Both the query and dataset marginals must be sufficiently anticoncentrated and sub-Gaussian so that every relevant union of intersections of halfspaces can be approximated, in low moments, by a polynomial of degree polynomial in 1/ε.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies data-driven nearest-neighbor search: given a fixed dataset P of size n and sample access to a query–nearest-neighbor distribution D, learn a data structure competitive with the best balanced halfspace tree for that D. The main result (Theorem 4 / informal Theorem 1) states that if d = polylog(n), D admits a perfect 1/3-balanced halfspace tree, and both marginals of D satisfy Gaussian-like anticoncentration and sub-Gaussianity (so that (R,J)-halfspace functions admit poly(1/ε)-degree moment approximations), then a polynomial-time algorithm outputs an O(nd)-space structure that answers exact nearest-neighbor queries in o(nd) time with high probability over D. The technical core is the balanced halfspace cut problem: proper learning is NP-hard even when OPT = 0 (Theorem 2), while an improper learner based on an SDP relaxation of an energy-plus-kurtosis program, followed by Cheeger-style rounding, produces a balanced low-degree PTF of error O(√(OPT + ε)) (Theorem 3). Recursive application of the cut learner, charged against the perfect tree via a Dasgupta-style sparsest-cut argument that accounts for unions-of-intersections of halfspaces, yields the final tree.

Significance. The work supplies a clean theoretical foundation for data-driven nearest-neighbor data structures that exploit the query distribution rather than remaining worst-case with respect to queries. The hardness of proper learning, the matching √OPT lower bound under SSEH, the SDP-plus-rounding analysis for improper learning under moment-approximability, and the hierarchical charging argument are all fully proved and self-contained. The Gaussian-like marginal hypothesis is standard in learning theory and is made fully explicit (Definition B.1, Theorem 5). While the final query time is only barely sublinear (o(nd) rather than O(d log n)), the result is the first polynomial-time guarantee that converts the existence of a perfect halfspace tree into a concrete sublinear data structure under natural distributional assumptions. The paper therefore advances both the theory of data-driven algorithm design and the understanding of geometric cut problems.

minor comments (5)
  1. Remark 1.1 and the parameter settings in the proof of Theorem 4 make the degradation from O(d log n) to o(nd) clear, but a short explicit calculation of the concrete exponents (how large C must be for d^{poly(log n)} + n d / (log n)^Ω(C) to be o(nd)) would help readers gauge practicality.
  2. The open question in Footnote 5 (whether a poly(d,1/ε)-time algorithm exists even for a single perfect halfspace under Gaussian marginals) is important; elevating it to a short “Open Problems” paragraph would improve visibility.
  3. In Definition 6.6 the conditional mixture D^{(u)} replaces out-of-region queries by self-pairs; a one-sentence intuition why this does not inflate the cut error relative to the true conditional would aid readability.
  4. Appendix B repeatedly uses the phrase “sufficiently large constant c”; collecting the concrete dependence of the degree on L, B, R, J, ε into a single displayed bound would make Theorem 5 easier to cite.
  5. A few typographical inconsistencies appear (e.g., “eO” vs. “Õ”, occasional missing spaces around math operators). A light copy-edit pass would polish the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: self-contained reduction from perfect halfspace tree + moment approximability to an explicit poly-time o(nd) data structure.

full rationale

The derivation chain is algorithmic and non-circular. Theorem 2 is a standard NP-hardness reduction from 3-Set-Split (via explicit pair construction and Claims 4.2–4.5). Theorem 3 minimizes an energy-plus-kurtosis program over degree-k polynomials via SDP (Definition 5.5, Claims 5.6–5.7) followed by Cheeger-style threshold rounding (Lemma 5.1); the competitive guarantee R_D(A*) = O((OPT_β + ε)/β) follows from the external F-approximation-degree hypothesis (Definition 5.1 / Lemma 5.4), not from any fitted parameter or self-referential definition of OPT. The tree construction (GreedyTree + Lemma 6.4) charges cost_D(T) to a perfect 1/3-balanced halfspace tree by producing (R,J)-halfspace certificates that are again approximable under the same hypothesis (Claim 6.5, Theorem 5). Appendix B derives the approximation degree from explicit anticoncentration/sub-Gaussianity (Definition B.1) via the external univariate sign approximation of DGJ+10; no uniqueness theorem, ansatz, or self-citation is load-bearing for the final o(nd) claim. All quantities (err, bal, cost, OPT) are defined independently of the learner’s output.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on three external pillars: (1) the existence of a perfect balanced halfspace tree (realizability), (2) Gaussian-like anticoncentration and sub-Gaussianity of the marginals that enable low-degree polynomial approximation of geometric regions, and (3) standard SDP and VC tools. No numerical parameters are fitted; all constants are absolute or polynomial in 1/ε, β.

assumptions (5)
  • domain assumption Existence of a perfect 1/3-balanced halfspace tree for the pair distribution D (realizable regime).
    Stated as the hypothesis of Theorems 1 and 4; without it the cost bound of GreedyTree need not be o(1).
  • domain assumption Both marginals of D are (L,Δ)-anticoncentrated and (B,r)-subgaussian (Definition B.1), so that every (R,J)-halfspace function admits a degree-(R·2^J/ε)^O(1) polynomial approximation in L1/L2/L4 (Theorem 5).
    Invoked throughout Sections 5–6 and Appendix B to guarantee that the SDP objective is O(OPT+ε) and that recursive certificates remain approximable.
  • standard math Standard SDP solvers return an approximate optimum of a size-(d+k)^k PSD matrix in poly time (JKL+20).
    Used in Claim 5.6 to solve the vector-valued relaxation of the energy-plus-kurtosis program.
  • standard math VC-dimension of degree-k PTFs is O((d+k)^k) and of slabs is O(d), enabling uniform convergence (Lemma 5.3, Facts A.2–A.4).
    Controls sample complexity of PolyCut and TestMass.
  • domain assumption Small-Set Expansion Hypothesis implies √α hardness for balanced cut (RST12), used only for tightness of Theorem 3.
    Corollary 5.9; not needed for the positive algorithmic claims.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Partition Trees for Nearest Neighbor Search." pith.science (2026). https://pith.science/paper/SDIQOYEY

@misc{pith2026260709909,
  author       = {Pith},
  title        = {Pith review of: Learning Partition Trees for Nearest Neighbor Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SDIQOYEY}},
  note         = {Machine review of arXiv:2607.09909}
}
abstract

We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset \mathbb{R}^d$ of size $n$ and sample access to a query distribution over $\mathbb{R}^d$, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving $o(nd)$ query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over $\mathbb{R}^d \times \mathbb{R}^d$ and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an $\alpha$ fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree $\tilde{O}(1/\varepsilon^2)$ that cuts at most an $O(\sqrt{\alpha+\varepsilon})$ fraction.

Figures

Figures reproduced from arXiv: 2607.09909 by the authors.

Figure 1
Figure 1. A perfect balanced halfspace tree in ℝ2 for a nearest neighbor pair distribution D over 32 pairs. The black points are the dataset, and each query 𝒒 is connected to its nearest neighbor 𝒑 ★ with a dotted line. The thick diagonal is the hyperplane at the root, and lines get thinner with depth. The Class C of Balanced Halfspace Trees. We study the class of balanced halfspace tree data structures, which is a natural ab… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

300 extracted references

  1. [1]

    High-Dimensional Computational Geometry , url =

    Alexandr Andoni , bibsource =. High-Dimensional Computational Geometry , url =. Handbook of Big Data. , crossref =. 2016 , bdsk-url-1 =

    2016

  2. [2]

    2021 , date-added =

    Deepanshu Kush and Aleksandar Nikolov and Haohua Tang , booktitle = SOCG2021, title =. 2021 , date-added =

    2021

  3. [3]

    Extremum problems with inequalities as subsidiary conditions , year =

    Fritz John , booktitle =. Extremum problems with inequalities as subsidiary conditions , year =

  4. [4]

    Spectral Approaches to Nearest Neighbor Search , year =

    Amirali Abdullah and Alexandr Andoni and Ravindran Kannan and Robert Krauthgamer , booktitle = FOCS2014, pages =. Spectral Approaches to Nearest Neighbor Search , year =

  5. [5]

    A Directed Isoperimetric Inequality with application to

    Amirali Abdullah and Suresh Venkatasubramanian , booktitle = STOC2015, pages =. A Directed Isoperimetric Inequality with application to

  6. [6]

    Approximate Bregman near neighbors in sublinear time: beyond the triangle inequality , year =

    Amirali Abdullah and John Moeller and Suresh Venkatasubramanian , booktitle = SOCG2012, organization =. Approximate Bregman near neighbors in sublinear time: beyond the triangle inequality , year =

  7. [7]

    Ahle and Rasmus Pagh and Ilya Razenshteyn and Francesco Silvestri , booktitle = PODS2016, note =

    Thomas D. Ahle and Rasmus Pagh and Ilya Razenshteyn and Francesco Silvestri , booktitle = PODS2016, note =. On the Complexity of Inner Product Similarity Join , year =

  8. [8]

    The Fast

    Nir Ailon and Bernard Chazelle , journal = SICOMP, number =. The Fast

Show all 300 references
  1. [9]

    Fast and

    Nir Ailon and Holger Rauhut , journal = DCG, number =. Fast and

  2. [10]

    Restricted Isometry Property for General p-Norms , year =

    Zeyuan. Restricted Isometry Property for General p-Norms , year =

  3. [11]

    Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters , year =

    Zeyuan. Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusters , year =

  4. [12]

    Chan and Ryan Williams , booktitle = FOCS2016, pages =

    Josh Alman and Timothy M. Chan and Ryan Williams , booktitle = FOCS2016, pages =. Polynomial Representations of Threshold Functions with Applications , year =

  5. [13]

    Nearest Neighbor Search: the Old, the New, and the Impossible , year =

    Alexandr Andoni , school =. Nearest Neighbor Search: the Old, the New, and the Impossible , year =

  6. [14]

    Hardness of Nearest Neighbor under

    Alexandr Andoni and Dorian Croitoru and Mihai Patrascu , booktitle = FOCS2008, pages =. Hardness of Nearest Neighbor under

  7. [15]

    Mirrokni , booktitle =

    Alexandr Andoni and Mayur Datar and Nicole Immorlica and Piotr Indyk and Vahab S. Mirrokni , booktitle =. Locality-sensitive hashing using stable distributions , year =

  8. [16]

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions , volume =

    Alexandr Andoni and Piotr Indyk , journal = CACM, number =. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions , volume =

  9. [17]

    Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions , year =

    Alexandr Andoni and Piotr Indyk , booktitle = FOCS2006, pages =. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions , year =

  10. [18]

    Alexandr Andoni and Piotr Indyk , howpublished =

  11. [19]

    Practical and Optimal

    Alexandr Andoni and Piotr Indyk and Thijs Laarhoven and Ilya Razenshteyn and Ludwig Schmidt , booktitle = NIPS2015, note =. Practical and Optimal

  12. [20]

    2025 , booktitle =

    Andoni, Alexandr and Jiang, Shunhua and Weinstein, Omri , title =. 2025 , booktitle =

    2025

  13. [21]

    SIAM Journal on Computing , volume =

    Gupta, Rishi and Roughgarden, Tim , title =. SIAM Journal on Computing , volume =

  14. [22]

    Nguyen and Ilya Razenshteyn , booktitle = SODA2014, pages =

    Alexandr Andoni and Piotr Indyk and Huy L. Nguyen and Ilya Razenshteyn , booktitle = SODA2014, pages =. Beyond Locality-Sensitive Hashing , year =

  15. [23]

    On the Optimality of the Dimensionality Reduction Method , year =

    Alexandr Andoni and Piotr Indyk and Mihai Patrascu , booktitle = FOCS2006, pages =. On the Optimality of the Dimensionality Reduction Method , year =

  16. [24]

    Sketching and Embedding are Equivalent for Norms , year =

    Alexandr Andoni and Robert Krauthgamer and Ilya Razenshteyn , booktitle = STOC2015, pages =. Sketching and Embedding are Equivalent for Norms , year =

  17. [25]

    34th International Symposium on Computational Geometry (SoCG 2018) , year=

    Graph-Based Time-Space Trade-Offs for Approximate Near Neighbors , author=. 34th International Symposium on Computational Geometry (SoCG 2018) , year=

    2018

  18. [26]

    Optimal Hashing-based Time--Space Trade-offs for Approximate Near Neighbors , year =

    Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten , booktitle = SODA2017, pages =. Optimal Hashing-based Time--Space Trade-offs for Approximate Near Neighbors , year =

  19. [27]

    Lower Bounds on Time--Space Trade-Offs for Approximate Near Neighbors , year =

    Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten , note =. Lower Bounds on Time--Space Trade-Offs for Approximate Near Neighbors , year =

  20. [28]

    Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing , year =

    Alexandr Andoni and Ilya Razenshteyn , booktitle = SOCG2016, note =. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing , year =

  21. [29]

    Optimal Data-Dependent Hashing for Approximate Near Neighbors , year =

    Alexandr Andoni and Ilya Razenshteyn , booktitle = STOC2015, pages =. Optimal Data-Dependent Hashing for Approximate Near Neighbors , year =

  22. [30]

    Alexandr Andoni and Ilya Razenshteyn and Negev

  23. [31]

    Woodruff , booktitle = SODA2016, note =

    Arturs Backurs and Piotr Indyk and Ilya Razenshteyn and David P. Woodruff , booktitle = SODA2016, note =. Nearly-optimal bounds for sparse recovery in generic norms, with applications to k -median sketching , year =

  24. [32]

    Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model , volume =

    Omer Barkol and Yuval Rabanit , journal = JCSS, number =. Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model , volume =

  25. [33]

    Jayram and Ravi Kumar and D

    Ziv Bar-Yossef and T.S. Jayram and Ravi Kumar and D. Sivakumar , journal = JCSS, number =. An information statistics approach to data stream and communication complexity , volume =

  26. [34]

    Mayank Bawa and Tyson Condie and Prasanna Ganesan , booktitle = WWW2005, pages =

  27. [35]

    New directions in nearest neighbor searching with applications to lattice sieving , year =

    Anja Becker and L. New directions in nearest neighbor searching with applications to lattice sieving , year =

  28. [36]

    A neural probabilistic language model , volume =

    Yoshua Bengio and R\'. A neural probabilistic language model , volume =

  29. [37]

    Multidimensional binary search trees used for associative searching , volume =

    Jon Bentley , journal = CACM, number =. Multidimensional binary search trees used for associative searching , volume =

  30. [38]

    Computational Geometry: Algorithms and Applications , year =

    Mark de Berg and Otfried Cheong and Marc van Kreveld and Mark Overmars , edition =. Computational Geometry: Algorithms and Applications , year =

  31. [39]

    Erik Bernhardsson , note =

  32. [40]

    Cover trees for nearest neighbor , year =

    Alina Beygelzimer and Sham Kakade and John Langford , booktitle = ICML2006, pages =. Cover trees for nearest neighbor , year =

  33. [41]

    Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems , year =

    Allan Borodin and Rafail Ostrovsky and Yuval Rabani , booktitle = STOC1999, pages =. Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems , year =

  34. [42]

    Broder , booktitle = SEQUENCES97, pages =

    Andrei Z. Broder , booktitle = SEQUENCES97, pages =. On the Resemblance and Containment of Documents , year =

  35. [43]

    Broder and Steven C

    Andrei Z. Broder and Steven C. Glassman and Mark S. Manasse and Geoffrey Zweig , journal = COMPNET, number =. Syntactic clustering of the Web , volume =

  36. [44]

    Provably Sensitive Indexing Strategies for Biosequence Similarity Search , volume =

    Jeremy Buhler , journal = JCB, number =. Provably Sensitive Indexing Strategies for Biosequence Similarity Search , volume =

  37. [45]

    Searching in metric spaces , volume =

    Edgar Ch. Searching in metric spaces , volume =

  38. [46]

    A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube , year =

    Amit Chakrabarti and Bernard Chazelle and Benjamin Gum and Alexey Lvov , booktitle = STOC1999, pages =. A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube , year =

  39. [47]

    An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching , volume =

    Amit Chakrabarti and Oded Regev , journal = SICOMP, number =. An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching , volume =

  40. [48]

    Similarity estimation techniques from rounding algorithms , year =

    Moses Charikar , booktitle = STOC2002, pages =. Similarity estimation techniques from rounding algorithms , year =

  41. [49]

    Finding Frequent Items in Data Streams , volume =

    Moses Charikar and Kevin Chen and Martin Farach. Finding Frequent Items in Data Streams , volume =

  42. [50]

    Krzysztof Choromanski and Francois Fagan and Cedric Gouy

  43. [51]

    Clarkson , booktitle =

    Kenneth L. Clarkson , booktitle =. Nearest-Neighbor Searching and Metric Space Dimensions , year =

  44. [52]

    Clarkson , journal = SICOMP, number =

    Kenneth L. Clarkson , journal = SICOMP, number =. A Randomized Algorithm for Closest-Point Queries , volume =

  45. [53]

    Frontiers in Massive Data Analysis , year =

    National Research Council , isbn =. Frontiers in Massive Data Analysis , year =

  46. [54]

    Random projection trees and low dimensional manifolds , year =

    Sanjoy Dasgupta and Yoav Freund , booktitle = STOC2008, pages =. Random projection trees and low dimensional manifolds , year =

  47. [55]

    Randomized partition trees for exact nearest neighbor search , year =

    Sanjoy Dasgupta and Kaushik Sinha , booktitle = COLT2013, pages =. Randomized partition trees for exact nearest neighbor search , year =

  48. [56]

    Mirrokni , booktitle = SOCG2004, pages =

    Mayur Datar and Nicole Immorlica and Piotr Indyk and Vahab S. Mirrokni , booktitle = SOCG2004, pages =. Locality-sensitive hashing scheme based on p-stable distributions , year =

  49. [57]

    Dhillon and Pradeep Ravikumar and Ambuj Tewari , booktitle = NIPS2011, pages =

    Inderjit S. Dhillon and Pradeep Ravikumar and Ambuj Tewari , booktitle = NIPS2011, pages =. Nearest Neighbor based Greedy Coordinate Descent , year =

  50. [58]

    Wei Dong , howpublished =

  51. [59]

    Fredman and J\'

    Michael L. Fredman and J\'. Storing a Sparse Table with

  52. [60]

    Johnson , journal = IEEEP, number =

    Matteo Frigo and Steven G. Johnson , journal = IEEEP, number =. The Design and Implementation of

  53. [61]

    Similarity Search in High Dimensions via Hashing , year =

    Aristides Gionis and Piotr Indyk and Rajeev Motwani , booktitle = VLDB1999, pages =. Similarity Search in High Dimensions via Hashing , year =

  54. [62]

    Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality , volume =

    Sariel Har. Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality , volume =

  55. [63]

    Variance Reduced Stochastic Gradient Descent with Neighbors , year =

    Thomas Hofmann and Aur. Variance Reduced Stochastic Gradient Descent with Neighbors , year =

  56. [64]

    Stable distributions, pseudorandom generators, embeddings, and data stream computation , volume =

    Piotr Indyk , journal = JACM, number =. Stable distributions, pseudorandom generators, embeddings, and data stream computation , volume =

  57. [65]

    On Approximate Nearest Neighbors under _

    Piotr Indyk , journal = JCSS, number =. On Approximate Nearest Neighbors under _

  58. [66]

    High-Dimensional Computational Geometry , year =

    Piotr Indyk , school =. High-Dimensional Computational Geometry , year =

  59. [67]

    Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality , year =

    Piotr Indyk and Rajeev Motwani , booktitle = STOC1998, pages =. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality , year =

  60. [68]

    Nearest-neighbor-preserving embeddings , volume =

    Piotr Indyk and Assaf Naor , journal = TALG, number =. Nearest-neighbor-preserving embeddings , volume =

  61. [69]

    On Model-Based

    Piotr Indyk and Ilya Razenshteyn , booktitle = ICALP2013, note =. On Model-Based

  62. [70]

    T. S. Jayram and Subhash Khot and Ravi Kumar and Yuval Rabani , journal = JCSS, number =. Cell-probe lower bounds for the partial match problem , volume =

  63. [71]

    Extensions of

    William Johnson and Joram Lindenstrauss , booktitle =. Extensions of

  64. [72]

    Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search , year =

    Michael Kapralov , booktitle = PODS2015, pages =. Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search , year =

  65. [73]

    Michael Kapralov and Rina Panigrahy , booktitle = ICALP2012, pages =

  66. [74]

    Karger and Matthias Ruhl , booktitle = STOC2002, pages =

    David R. Karger and Matthias Ruhl , booktitle = STOC2002, pages =. Finding nearest neighbors in growth-restricted metrics , year =

  67. [75]

    A Faster Subquadratic Algorithm for Finding Outlier Correlations , year =

    Matti Karppa and Petteri Kaski and Jukka Kohonen , booktitle = SODA2016, pages =. A Faster Subquadratic Algorithm for Finding Outlier Correlations , year =

  68. [76]

    Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time , volume =

    Karppa, Matti and Kaski, Petteri and Kohonen, Jukka and. Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time , volume =

  69. [77]

    Fast Polynomial Factorization and Modular Composition , volume =

    Kiran Kedlaya and Christopher Umans , journal = SICOMP, number =. Fast Polynomial Factorization and Modular Composition , volume =

  70. [78]

    Fast Cross-Polytope Locality-Sensitive Hashing , year =

    Christopher Kennedy and Rachel Ward , note =. Fast Cross-Polytope Locality-Sensitive Hashing , year =

  71. [79]

    Lee , booktitle = SODA2004, pages =

    Robert Krauthgamer and James R. Lee , booktitle = SODA2004, pages =. Navigating nets: simple algorithms for proximity search , year =

  72. [80]

    Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces , volume =

    Eyal Kushilevitz and Rafail Ostrovsky and Yuval Rabani , journal = SICOMP, number =. Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces , volume =

  73. [81]

    Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing , year =

    Thijs Laarhoven , booktitle = CRYPTO2015, pages =. Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing , year =

  74. [82]

    Tradeoffs for nearest neighbors on the sphere , year =

    Thijs Laarhoven , note =. Tradeoffs for nearest neighbors on the sphere , year =

  75. [83]

    Search problems in cryptography: From fingerprinting to lattice sieving , year =

    Thijs Laarhoven , school =. Search problems in cryptography: From fingerprinting to lattice sieving , year =

  76. [84]

    Mining of Massive Datasets , year =

    Jure Lescovec and Anand Rajaraman and Jeffrey David Ullman , edition =. Mining of Massive Datasets , year =

  77. [85]

    The geometry of graphs and some of its algorithmic applications , volume =

    Nathan Linial and Eran London and Yuri Rabinovich , journal = COMBINATORICA, number =. The geometry of graphs and some of its algorithmic applications , volume =

  78. [86]

    A strong lower bound for approximate nearest neighbor searching , volume =

    Ding Liu , journal = IPL, number =. A strong lower bound for approximate nearest neighbor searching , volume =

  79. [87]

    Randomized Approximate Nearest Neighbor Search with Limited Adaptivity , year =

    Mingmou Liu and Xiaoyin Pan and Yitong Yin , booktitle = SPAA2016, pages =. Randomized Approximate Nearest Neighbor Search with Limited Adaptivity , year =

  80. [88]

    Multi-Probe

    Qin Lv and William Josephson and Zhe Wang and Moses Charikar and Kai Li , booktitle = VLDB2007, pages =. Multi-Probe

  81. [89]

    On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes , year =

    Alexander May and Ilya Ozerov , booktitle = EUROCRYPT2015, pages =. On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes , year =

  82. [90]

    A fast nearest-neighbor algorithm based on a principal axis search tree , volume =

    James McNames , journal = TPAMI, number =. A fast nearest-neighbor algorithm based on a principal axis search tree , volume =

  83. [91]

    Point Location in Arrangements of Hyperplanes , volume =

    Stefan Meiser , journal = INFCOMP, number =. Point Location in Arrangements of Hyperplanes , volume =

  84. [92]

    Cell probe complexity -- a survey , year =

    Peter Bro Miltersen , booktitle =. Cell probe complexity -- a survey , year =

  85. [93]

    On data structures and asymmetric communication complexity , year =

    Peter Bro Miltersen and Noam Nisan and Shmuel Safra and Avi Wigderson , booktitle = STOC1995, pages =. On data structures and asymmetric communication complexity , year =

  86. [94]

    Lower Bounds on Locality Sensitive Hashing , volume =

    Rajeev Motwani and Assaf Naor and Rina Panigrahy , journal = SIDM, number =. Lower Bounds on Locality Sensitive Hashing , volume =

  87. [95]

    Lowe , booktitle = VISAPP2009, pages =

    Marius Muja and David G. Lowe , booktitle = VISAPP2009, pages =. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration , year =

  88. [96]

    Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny) , volume =

    Ryan O'Donnell and Yi Wu and Yuan Zhou , journal = TOCT, number =. Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny) , volume =

  89. [97]

    Overmars and Jan van Leeuwen , journal = IPL, number =

    Mark H. Overmars and Jan van Leeuwen , journal = IPL, number =. Some principles for dynamizing decomposable searching problems , volume =

  90. [98]

    Locality-sensitive Hashing without False Negatives , year =

    Rasmus Pagh , booktitle = SODA2016, pages =. Locality-sensitive Hashing without False Negatives , year =

  91. [99]

    Entropy based nearest neighbor search in high dimensions , year =

    Rina Panigrahy , booktitle = SODA2006, pages =. Entropy based nearest neighbor search in high dimensions , year =

  92. [100]

    Lower Bounds on Near Neighbor Search via Metric Expansion , year =

    Rina Panigrahy and Kunal Talwar and Udi Wieder , booktitle = FOCS2010, pages =. Lower Bounds on Near Neighbor Search via Metric Expansion , year =

  93. [101]

    A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match , year =

    Rina Panigrahy and Kunal Talwar and Udi Wieder , booktitle = FOCS2008, pages =. A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match , year =

  94. [102]

    Unifying the Landscape of Cell-Probe Lower Bounds , volume =

    Mihai Patrascu , journal = SICOMP, number =. Unifying the Landscape of Cell-Probe Lower Bounds , volume =

  95. [103]

    Higher Lower Bounds for Near-Neighbor and Further Rich Problems , volume =

    Mihai Patrascu and Mikkel Thorup , journal = SICOMP, number =. Higher Lower Bounds for Near-Neighbor and Further Rich Problems , volume =

  96. [104]

    Ilya Razenshteyn and Ludwig Schmidt , howpublished =

  97. [105]

    Woodruff , booktitle = STOC2016, pages =

    Ilya Razenshteyn and Zhao Song and David P. Woodruff , booktitle = STOC2016, pages =. Weighted low rank approximations with provable guarantees , year =

  98. [106]

    Guibas , journal = IJCV, number =

    Yossi Rubner and Carlo Tomasi and Leonidas J. Guibas , journal = IJCV, number =. The

  99. [107]

    Semantic Hashing , volume =

    Ruslan Salakhutdinov and Geoffrey Hinton , journal = IJAR, number =. Semantic Hashing , volume =

  100. [108]

    Nearest-Neighbor Methods in Learning and Vision: Theory and Practice , year =

    Gregory Shakhnarovich and Trevor Darrell and Piotr Indyk , publisher =. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice , year =

  101. [109]

    Optimised

    Chanop Silpa. Optimised

  102. [110]

    Scalable and Sustainable Deep Learning via Randomized Hashing , year =

    Ryan Spring and Anshumali Shrivastava , note =. Scalable and Sustainable Deep Learning via Randomized Hashing , year =

  103. [111]

    Sproull , journal = ALGORITHMICA, number =

    Robert F. Sproull , journal = ALGORITHMICA, number =. Refinements to nearest-neighbor searching in k -dimensional trees , volume =

  104. [112]

    Weighted Low-Rank Approximations , year =

    Nathan Srebro and Tommi Jaakkola , booktitle = ICML2003, owner =. Weighted Low-Rank Approximations , year =

  105. [113]

    Spherical

    Kengo Terasawa and Yuzuru Tanaka , booktitle = WADS2007, pages =. Spherical

  106. [114]

    Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem , volume =

    Gregory Valiant , journal = JACM, number =. Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem , volume =

  107. [115]

    Nakul Verma and Samory Kpotufe and Sanjoy , booktitle = UAI2009, title =

  108. [116]

    Sequential Projection Learning for Hashing with Compact Codes , year =

    Jun Wang and Sanjiv Kumar and Shih. Sequential Projection Learning for Hashing with Compact Codes , year =

  109. [117]

    Learning to Hash for Indexing Big Data - A Survey , year =

    Jun Wang and Wei Liu and Sanjiv Kumar and Shih-Fu Chang , note =. Learning to Hash for Indexing Big Data - A Survey , year =

  110. [118]

    Hashing for Similarity Search: a Survey , year =

    Jingdong Wang and Heng Tao Shen and Kingkuan Song and Jianqiu Ji , note =. Hashing for Similarity Search: a Survey , year =

  111. [119]

    Feature Hashing for Large Scale Multitask Learning , year =

    Kilian Weinberger and Anirban Dasgupta and John Langford and Alex Smola and Josh Attenberg , booktitle = ICML2009, pages =. Feature Hashing for Large Scale Multitask Learning , year =

  112. [120]

    Spectral Hashing , year =

    Yair Weiss and Antonio Torralba and Rob Fergus , booktitle = NIPS2008, pages =. Spectral Hashing , year =

  113. [121]

    Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk) , year =

  114. [122]

    Jay Yagnik and Dennis Strelow and David Ross and Ruei-Sung Lin , booktitle = ICCV2011, title =

  115. [123]

    Locally Decodable Codes , volume =

    Sergey Yekhanin , number =. Locally Decodable Codes , volume =

  116. [124]

    Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities , year =

    Yitong Yin , note =. Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities , year =

  117. [125]

    K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance , year =

    Piotr Indyk and Eric Price , booktitle = STOC2011, pages =. K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance , year =

  118. [126]

    Lower Bounds for Sparse Recovery , year =

    Khanh. Lower Bounds for Sparse Recovery , year =

  119. [127]

    Candes and Justin K

    Emmanuel J. Candes and Justin K. Romberg and Terence Tao , journal = TIT, number =. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information , volume =

  120. [128]

    Overcoming the _1 Non-Embeddability Barrier: Algorithms for Product Metrics , year =

    Alexandr Andoni and Piotr Indyk and Robert Krauthgamer , booktitle = SODA2009, pages =. Overcoming the _1 Non-Embeddability Barrier: Algorithms for Product Metrics , year =

  121. [129]

    Marshall and Ingram Olkin and Barry C

    Albert W. Marshall and Ingram Olkin and Barry C. Arnold , publisher =. Inequalities: theory of majorization and its applications , year =

  122. [130]

    Approximate nearest neighbor algorithms for Fr

    Piotr Indyk , booktitle = SOCG2002, pages =. Approximate nearest neighbor algorithms for Fr

  123. [131]

    An Elementary Introduction to Modern Convex Geometry , volume =

    Keith Ball , publisher =. An Elementary Introduction to Modern Convex Geometry , volume =

  124. [132]

    Approximate Nearest Neighbor under edit distance via product metrics , year =

    Piotr Indyk , booktitle = SODA2004, pages =. Approximate Nearest Neighbor under edit distance via product metrics , year =

  125. [133]

    Zero-one frequency laws , year =

    Vladimir Braverman and Rafail Ostrovsky , booktitle = STOC2010, pages =. Zero-one frequency laws , year =

  126. [134]

    Sparse Prediction with the k -Support Norm , year =

    Andreas Argyriou and Rina Foygel and Nathan Srebro , booktitle = NIPS2012, pages =. Sparse Prediction with the k -Support Norm , year =

  127. [135]

    McDonald and Massimiliano Pontil and Dimitris Stamos , booktitle = NIPS2014, pages =

    Andrew M. McDonald and Massimiliano Pontil and Dimitris Stamos , booktitle = NIPS2014, pages =. Spectral k -Support Norm Regularization , year =

  128. [136]

    S. J. Dilworth and S. J. Montgomery-Smith , journal = AOP, number =. The distribution of vector-valued

  129. [137]

    A Unified Framework for Linear Dimensionality Reduction in

    Felix Krahmer and Rachel Ward , journal =. A Unified Framework for Linear Dimensionality Reduction in

  130. [138]

    On randomized one-round communication complexity , year =

    Ilan Kremer and Noam Nisan and Dana Ron , journal = JCC, pages =. On randomized one-round communication complexity , year =

  131. [139]

    Banach Spaces for Analysts , year =

    Przemys. Banach Spaces for Analysts , year =

  132. [140]

    2016 , bdsk-url-1 =

    Handbook of Big Data , url =. 2016 , bdsk-url-1 =

    2016

  133. [141]

    Ken Clarkson , journal =

  134. [142]

    , booktitle = FOCS2003, pages =

    Gupta, Anupam and Krauthgamer, Robert and Lee, James R. , booktitle = FOCS2003, pages =. Bounded Geometries, Fractals, and Low-Distortion Embeddings , year =

  135. [143]

    Interpolation of Operators , volume =

    Colin Bennett and Robert Sharpley , publisher =. Interpolation of Operators , volume =

  136. [144]

    Mount and Nathan S

    Sunil Arya and David M. Mount and Nathan S. Netanyahu and Ruth Silverman and Angela Y. Wu , journal = JACM, number =. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions , volume =

  137. [145]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff , booktitle = SODA2015, pages =. Sketching for M -Estimators: A Unified Approach to Robust Regression , year =

  138. [146]

    Planar Earthmover is not in

    Assaf Naor and Gideon Schechtman , journal = sicomp, note =. Planar Earthmover is not in

  139. [147]

    On approximate nearest neighbor search in _p , p > 2 , year =

    Assaf Naor and Yuval Rabani , note =. On approximate nearest neighbor search in _p , p > 2 , year =

  140. [148]

    On the distortion required for embedding finite metric spaces into normed spaces , volume =

    Ji. On the distortion required for embedding finite metric spaces into normed spaces , volume =. Israel Journal of Mathematics , pages =

  141. [149]

    Tolerant junta testing and the connection to submodular optimization and function isomorphism , year =

    Eric Blais and Cl. Tolerant junta testing and the connection to submodular optimization and function isomorphism , year =

  142. [150]

    Adaptivity helps for testing juntas , year =

    Rocco A Servedio and Li-Yang Tan and John Wright , booktitle = CCC2015, pages =. Adaptivity helps for testing juntas , year =

  143. [151]

    On monotonicity testing and boolean isoperimetric type theorems , year =

    Subhash Khot and Dor Minzer and Muli Safra , booktitle = FOCS2015, organization =. On monotonicity testing and boolean isoperimetric type theorems , year =

  144. [152]

    Testing juntas nearly optimally , year =

    Eric Blais , booktitle = STOC2009, pages =. Testing juntas nearly optimally , year =

  145. [153]

    Improved bounds for testing juntas , year =

    Eric Blais , booktitle = APPROXRANDOM2008, pages =. Improved bounds for testing juntas , year =

  146. [154]

    A lower bound for testing juntas , year =

    Hana Chockler and Dan Gutfreund , journal =. A lower bound for testing juntas , year =

  147. [155]

    On the Structure, CovCover, and Learning of Poisson Multinomial Distributions , year =

    Constantinos Daskalakis and Gautam Kamath and Christos Tzamos , booktitle = FOCS2015, organization =. On the Structure, CovCover, and Learning of Poisson Multinomial Distributions , year =

  148. [156]

    Seshadhri , journal = ARXIV #

    Deeparnab Chakrabarty and C. Seshadhri , journal = ARXIV #. A. 2016 , bdsk-url-1 =

    2016

  149. [157]

    Fast GPU-based locality sensitive hashing for k-nearest neighbor computation , year =

    Jia Pan and Dinesh Manocha , booktitle = SIGSPATIAL, organization =. Fast GPU-based locality sensitive hashing for k-nearest neighbor computation , year =

  150. [158]

    Lower bounds for 2-query LCCs over large alphabet , year =

    Arnab Bhattacharyya and Sivakanth Gopi , journal = ECCC #. Lower bounds for 2-query LCCs over large alphabet , year =

  151. [159]

    Assaf Naor , journal = SOCG2017, title =

  152. [160]

    Exact Kolmogorov and total variation distances between some familiar discrete distributions , volume =

    Adell, Jos. Exact Kolmogorov and total variation distances between some familiar discrete distributions , volume =. Journal of Inequalities and Applications , number =

  153. [161]

    A polynomial lower bound for testing monotonicity , year =

    Aleksandrs Belovs and Eric Blais , booktitle = STOC2016, pages =. A polynomial lower bound for testing monotonicity , year =

  154. [162]

    Emiris and Ioannis Psarros and Georgios Samaras , journal = ARXIV #

    Georgia Avarikioti and Ioannis Z. Emiris and Ioannis Psarros and Georgios Samaras , journal = ARXIV #. Practical linear-space approximate near neighbor in high dimension , year =

  155. [163]

    Exponential lower bound for 2-query locally decodable codes via a quantum argument , volume =

    Iordanis Kerenidis and Ronald de Wolf , journal =. Exponential lower bound for 2-query locally decodable codes via a quantum argument , volume =

  156. [164]

    Tobias Christiani , booktitle = SODA2017, title =

  157. [165]

    Planar 1-in-3 Satisfiability is NP-complete , volume =

    Philippe Laroche , journal =. Planar 1-in-3 Satisfiability is NP-complete , volume =

  158. [166]

    Probabilistic clustering of high dimensional norms , year =

    Assaf Naor , booktitle = SODA2017, pages =. Probabilistic clustering of high dimensional norms , year =

  159. [167]

    Lensch , booktitle = CVPR2016, title =

    Patrick Wieschollek and Oliver Wang and Alexander Sorkine-Hornung and Hendrik P.A. Lensch , booktitle = CVPR2016, title =

  160. [168]

    Shrinkage of de Morgan Formulae by Spectral Techniques , year =

    Avishay Tal , booktitle = FOCS2014, pages =. Shrinkage of de Morgan Formulae by Spectral Techniques , year =

  161. [169]

    Subexponential algorithms for unique games and related problems , volume =

    Sanjeev Arora and Boaz Barak and David Steurer , journal =. Subexponential algorithms for unique games and related problems , volume =

  162. [170]

    Klivans , booktitle = STOC2008, pages =

    Parikshit Gopalan and Adam Tauman Kalai and Adam R. Klivans , booktitle = STOC2008, pages =. Agnostically learning decision trees , year =

  163. [171]

    Agnostically learning juntas from random walks , year =

    Jan Arpe and Elchanan Mossel , journal = ARXIV #. Agnostically learning juntas from random walks , year =

  164. [172]

    On the degree of boolean functions as real polynomials , volume =

    Noam Nisan and Mario Szegedy , journal = CC, month = dec, number =. On the degree of boolean functions as real polynomials , volume =

  165. [173]

    Servedio and Avishay Tal and Avi Wigderson , booktitle = CCC2016, title =

    Parikshit Gopalan and Rocco A. Servedio and Avishay Tal and Avi Wigderson , booktitle = CCC2016, title =

  166. [174]

    Robust Sensitivity , year =

    Shachar Lovett and Avishay Tal and Jiapeng Zhang , journal = ECCC #. Robust Sensitivity , year =

  167. [175]

    Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten , booktitle = STOC2017, title =

    Alexandr Andoni and Huy L. Nguyen and Aleksandar Nikolov and Ilya Razenshteyn and Erik Waingarten , booktitle = STOC2017, title =

  168. [176]

    Xi Chen and Erik Waingarten and Jinyu Xie , booktitle = STOC2017, pages =. Beyond

  169. [177]

    Yevgeniy Dodis and Oded Goldreich and Eric Lehman and Sofya Raskhodnikova and Dana Ron and Alex Samorodnitsky , booktitle = APPROXRANDOM1999, title =

  170. [178]

    Testing Monotonicity , volume =

    Oded Goldreich and Shafi Goldwasser and Eric Lehman and Dana Ron and Alex Samordinsky , journal =. Testing Monotonicity , volume =

  171. [179]

    Monotonicity testing over general poset domains , year =

    Eldar Fischer and Eric Lehman and Ilan Newman and Sofya Raskhodnikova and Ronitt Rubinfeld and Alex Samorodnitsky , booktitle = STOC2002, pages =. Monotonicity testing over general poset domains , year =

  172. [180]

    On the strength of comparisons in property testing , volume =

    Eldar Fischer , journal =. On the strength of comparisons in property testing , volume =

  173. [181]

    Sublinear algorithms for testing monotone and unimodal distributions , year =

    Tugkan Batu and Ravi Kumar and Ronitt Rubinfeld , booktitle = STOC2004, pages =. Sublinear algorithms for testing monotone and unimodal distributions , year =

  174. [182]

    Estimating the distance to a monotone function , volume =

    Nir Ailon and Bernard Chazelle and Seshadhri Comandur and Ding Liu , journal =. Estimating the distance to a monotone function , volume =

  175. [183]

    Testing monotonicity over graph products , volume =

    Shirley Halevy and Eyal Kushilevitz , journal =. Testing monotonicity over graph products , volume =

  176. [184]

    Servedio , journal =

    Ronitt Rubinfeld and Rocco A. Servedio , journal =. Testing monotone high-dimensional distributions , volume =

  177. [185]

    Property testing lower bounds via communication complexity , volume =

    Eric Blais and Joshua Brody and Kevin Matulef , journal = CC, number =. Property testing lower bounds via communication complexity , volume =

  178. [186]

    Monotonicity testing and shortest-path routing on the cube , volume =

    Jop Bri. Monotonicity testing and shortest-path routing on the cube , volume =. Combinatorica , number =

  179. [187]

    Approximating the influence of monotone boolean functions in

    Dana Ron and Ronitt Rubinfeld and Muli Safra and Alex Samorodnitsky and Omri Weinstein , journal = TOCT, number =. Approximating the influence of monotone boolean functions in

  180. [188]

    An o(n) monotonicity tester for boolean functions over the hypercube , volume =

    Deeparnab Chakrabarty and Seshadhri Comandur , journal = SICOMP, number =. An o(n) monotonicity tester for boolean functions over the hypercube , volume =

  181. [189]

    Lower bounds for testing properties of functions over hypergrid domains , year =

    Eric Blais and Sofya Raskhodnikova and Grigory Yaroslavtsev , booktitle = CCC2014, pages =. Lower bounds for testing properties of functions over hypergrid domains , year =

  182. [190]

    Servedio and Li-Yang Tan , booktitle = STOC2015, pages =

    Xi Chen and Anindya De and Rocco A. Servedio and Li-Yang Tan , booktitle = STOC2015, pages =. Boolean function monotonicity testing requires (almost)

  183. [191]

    Chestnut and Robert Krauthgamerand Lin F

    Jaroslaw Blasiok and Vladimir Braverman and Stephen R. Chestnut and Robert Krauthgamerand Lin F. Yang , booktitle = STOC2017, title =

  184. [192]

    Servedio and Li-Yang Tan , booktitle = FOCS2014, pages =

    Xi Chen and Rocco A. Servedio and Li-Yang Tan , booktitle = FOCS2014, pages =. New algorithms and lower bounds for monotonicity testing , year =

  185. [193]

    Pallavoor and Sofya Raskhodnikova , journal = ARXIV #

    Roksana Baleshzar and Meiram Murzabulatov and Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova , journal = ARXIV #. Testing unateness of real-valued functions , year =

  186. [194]

    Subhash Khot and Igor Shinkar , booktitle = APPROXRANDOM2016, pages =. An

  187. [195]

    Information theory in property testing and monotonicity testing in higher dimension , volume =

    Nir Ailon and Bernard Chazelle , journal =. Information theory in property testing and monotonicity testing in higher dimension , volume =

  188. [196]

    Quantum algorithm for monotonicity testing on the hypercube , volume =

    Eric Blais and Aleksandrs Belovs , journal = TOC, number =. Quantum algorithm for monotonicity testing on the hypercube , volume =

  189. [197]

    Piotr Berman and Sofya Raskhodnikova and Grigory Yaroslavtsev , booktitle = STOC2014, title =

  190. [198]

    Monotonicity Testing , year =

    Deeparnab Chakrabarty , booktitle =. Monotonicity Testing , year =

  191. [199]

    Seshadhri , journal = TALG, number =

    Deeparnab Chakrabarty and Kashyap Dixit and Madhav Jha and C. Seshadhri , journal = TALG, number =. Property testing on product distributions: optimal testers for bounded derivative properties , volume =

  192. [200]

    Seshadhri , booktitle = STOC2013, pages =

    Deeparnab Chakrabarty and C. Seshadhri , booktitle = STOC2013, pages =. Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids , year =

  193. [201]

    Seshadhri , journal = TOC, number =

    Deeparnab Chakrabarty and C. Seshadhri , journal = TOC, number =. An optimal lower bound for monotonicity testing over hypergrids , volume =

  194. [202]

    Property testing and its connection to learning and approximation , volume =

    Oded Goldreich and Shafi Goldwasser and Dana Ron , journal = JACM, number =. Property testing and its connection to learning and approximation , volume =

  195. [203]

    Testing and reconstruction of Lipschitz functions with applications to data privacy , volume =

    Madhav Jha and Sofya Raskhodnikova , journal = SICOMP, number =. Testing and reconstruction of Lipschitz functions with applications to data privacy , volume =

  196. [204]

    Ravi Kumar and Ronitt Rubinfeld and Mahesh Vishwanthan , journal =

    Funda Erg\"un and Sampath Kannan and S. Ravi Kumar and Ronitt Rubinfeld and Mahesh Vishwanthan , journal =. Spot-checkers , volume =

  197. [205]

    Testing k -monotonicity , year =

    Cl\'. Testing k -monotonicity , year =

  198. [206]

    Servedio and Li-Yang Tan and Erik Waingarten and Jinyu Xie , booktitle = CCC2017, title =

    Xi Chen and Rocco A. Servedio and Li-Yang Tan and Erik Waingarten and Jinyu Xie , booktitle = CCC2017, title =

  199. [207]

    An adaptivity hierarchy theorem for property testing , year =

    Cl\'. An adaptivity hierarchy theorem for property testing , year =

  200. [208]

    Property testing: A learning theory perspective , volume =

    Dana Ron , journal = FTML, number =. Property testing: A learning theory perspective , volume =

  201. [209]

    Algorithmic and analysis techniques in property testing , volume =

    Dana Ron , journal = FTTCS, number =. Algorithmic and analysis techniques in property testing , volume =

  202. [210]

    How much are increasing sets positively correlated? , volume =

    Michel Talagrand , journal = COMBINATORICA, number =. How much are increasing sets positively correlated? , volume =

  203. [211]

    On the noise sensitivity of monotone functions , volume =

    Elchanan Mossel and Ryan O'Donnell , journal =. On the noise sensitivity of monotone functions , volume =

  204. [212]

    Property Testing: Current Research and Surveys , volume =

  205. [213]

    Testing Monotonicity , year =

    Oded Goldreich and Shafi Goldwasser and Eric Lehman and Dana Ron , booktitle = FOCS1998, pages =. Testing Monotonicity , year =

  206. [214]

    Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence , volume =

    Anna Gal and Parikshit Gopalan , journal =. Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence , volume =

  207. [215]

    Lecture notes on metric embeddings , year =

    Ji. Lecture notes on metric embeddings , year =

  208. [216]

    Pallavoor and Sofya Raskhodnikova and C

    Roksana Baleshzar and Deeparnab Chakrabarty and Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and C. Seshadhri , booktitle = ICALP2017, title =

  209. [217]

    Crossing the logarithmic barrier for dynamic boolean data structure lower bounds , year =

    Kasper Green Larsen and Omri Weinstein and Huacheng Yu , journal = ECCC #. Crossing the logarithmic barrier for dynamic boolean data structure lower bounds , year =

  210. [218]

    Timothy Naumovitz and Michael Saks , booktitle = SODA2014, title =

  211. [219]

    Pallavoor and Sofya Raskhodnikova and C

    Roksana Baleshzar and Deeparnab Chakrabarty and Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and C. Seshadhri , journal = ARXIV #. A lower bound for nonadaptive, one-sided error testing of unateness of Boolean functions over the hypercube , year =

  212. [220]

    Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem , volume =

    Michel Talagrand , journal =. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem , volume =

  213. [221]

    Efficient sketches for earth-mover distance, with applications , year =

    Alexandr Andoni and Khanh Do Ba and Piotr Indyk and David Woodruff , booktitle = FOCS2009, pages =. Efficient sketches for earth-mover distance, with applications , year =

  214. [222]

    Optimal approximations of the frequency moments of data streams , year =

    Piotr Indyk and David Woodruff , booktitle = STOC2005, pages =. Optimal approximations of the frequency moments of data streams , year =

  215. [223]

    Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak , booktitle = FOCS2010, title =

  216. [224]

    Ran Raz and Amir Shpilka , journal = SICOMP, title =

  217. [225]

    Earth mover distance over high-dimensional spaces , year =

    Alexandr Andoni and Piotr Indyk and Robert Krauthgamer , booktitle = SODA2008, pages =. Earth mover distance over high-dimensional spaces , year =

  218. [226]

    Alexandr Andoni and Haitham Hassanieh and Piotr Indyk and Dina Katabi , booktitle = SODA2013, title =

  219. [227]

    Alexandr Andoni and Assaf Goldberger and Andrew McGregor and Ely Porat , booktitle = STOC2013, title =

  220. [228]

    On a class of degenerate extremal graph problems , year =

    Ralph J Faudree and Mikl. On a class of degenerate extremal graph problems , year =

  221. [229]

    Testing probability distributions using conditional samples , volume =

    Cl\'. Testing probability distributions using conditional samples , volume =

  222. [230]

    On the power of conditional samples in distribution testing , volume =

    Sourav Chakraborty and Eldar Fischer and Yonatan Goldhirsh and Arie Matsliah , journal = SICOMP, number =. On the power of conditional samples in distribution testing , volume =

  223. [231]

    Themistoklis Gouleakis and Christos Tzamos and Manolis Zampetakis , booktitle = SODA2017, title =

  224. [232]

    On sample-based testers , volume =

    Oded Goldreich and Dana Ron , journal = TOCT, number =. On sample-based testers , volume =

  225. [233]

    Tolerant versus intolerant testing for Boolean properties , volume =

    Eldar Fischer and Lance Fortnow , journal = TOC, number =. Tolerant versus intolerant testing for Boolean properties , volume =

  226. [234]

    Servedio and Li-Yang Tan , booktitle = FOCS2017, title =

    Rocco A. Servedio and Li-Yang Tan , booktitle = FOCS2017, title =

  227. [235]

    Generalized Uniformity Testing , year =

    Tugkan Batu and Cl\'. Generalized Uniformity Testing , year =

  228. [236]

    Hashing-based-estimators for kernel density in high dimensions , year =

    Moses Charikar and Paris Siminelakis , booktitle = FOCS2017, pages =. Hashing-based-estimators for kernel density in high dimensions , year =

  229. [237]

    Servedio and Li-Yang Tan and Erik Waingarten , booktitle = APPROXRANDOM2017, title =

    Xi Chen and Rocco A. Servedio and Li-Yang Tan and Erik Waingarten , booktitle = APPROXRANDOM2017, title =

  230. [238]

    Xi Chen and Erik Waingarten and Jinyu Xie , booktitle = FOCS2017, title =

  231. [239]

    Tolerant property testing and distance approximation , volume =

    Michal Parnas and Dana Ron and Ronitt Rubinfeld , journal = JCSS, number =. Tolerant property testing and distance approximation , volume =

  232. [240]

    Robust characterization of polynomials with applications to program testing , volume =

    Ronitt Rubinfeld and Madhu Sudan , journal = SICOMP, number =. Robust characterization of polynomials with applications to program testing , volume =

  233. [241]

    High-Dimensional Similarity Search and Sketching: Algorithms and Hardness , year =

    Ilya Razenshteyn , school =. High-Dimensional Similarity Search and Sketching: Algorithms and Hardness , year =

  234. [242]

    Nearest neighbors in high-dimensional spaces , year =

    Alexandr Andoni and Piotr Indyk , booktitle =. Nearest neighbors in high-dimensional spaces , year =

  235. [243]

    Lecture notes on the ARV algorithm for spsparse cut , year =

    Thomas Rothvoss , journal = ARXIV #. Lecture notes on the ARV algorithm for spsparse cut , year =

  236. [244]

    Comparison of metric spectral gaps , volume =

    Assaf Naor , journal = AGMS, number =. Comparison of metric spectral gaps , volume =

  237. [245]

    Low distortion embeddings for edit distance , volume =

    Rafail Ostrovsky and Yuval Rabani , journal = JACM, number =. Low distortion embeddings for edit distance , volume =

  238. [246]

    Lee , booktitle = SODA2005, title =

    James R. Lee , booktitle = SODA2005, title =

  239. [247]

    Small distortion and volume preserving embeddings for planar and Euclidean metrics , year =

    Satish Rao , booktitle = SOCG1999, pages =. Small distortion and volume preserving embeddings for planar and Euclidean metrics , year =

  240. [248]

    On expressing majority as a majority of majorities , year =

    Christian Engels and Mohit Garg and Kazuhisa Makino and Anup Rao , journal = ECCC #. On expressing majority as a majority of majorities , year =

  241. [249]

    Kulikov and Vladimir Podolskii , booktitle = STACS2017, title =

    Alexander S. Kulikov and Vladimir Podolskii , booktitle = STACS2017, title =

  242. [250]

    Yoav Benyamini and Joram Lindenstrauss , publisher = AMS, title =

  243. [251]

    Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication , year =

    Diptarka Chakraborty and Lior Kamma and Kasper Green Larsen , journal = ARXIV #. Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication , year =

  244. [252]

    Seshadhri , booktitle = SODA2013, title =

    Michael Saks and C. Seshadhri , booktitle = SODA2013, title =

  245. [253]

    Seshadhri , booktitle = FOCS2010, title =

    Michael Saks and C. Seshadhri , booktitle = FOCS2010, title =

  246. [254]

    Michael Kapralov and Sanjeev Khanna and Madhu Sudan and Ameya Velingker , booktitle = SODA2017, title =

  247. [255]

    Nguyen and David Woodruff , booktitle = STOC2016, title =

    Mark Braverman and Ankit Garg and Tengyu Ma and Huy L. Nguyen and David Woodruff , booktitle = STOC2016, title =

  248. [256]

    Nguyen and David Woodruff , booktitle = STOC2014, title =

    Yi Li and Huy L. Nguyen and David Woodruff , booktitle = STOC2014, title =

  249. [257]

    Alexandr Andoni and Robert Krauthgamer and Krzysztof Onak , booktitle = FOCS2011, title =

  250. [258]

    Nguyen , booktitle = FOCS2011, title =

    Alexandr Andoni and Moses Charikar and Ofer Neiman and Huy L. Nguyen , booktitle = FOCS2011, title =

  251. [259]

    Assaf Naor and Gilles Pisier and Gideon Schechtman , booktitle = SODA2018, title =

  252. [260]

    Optimality of the

    Kasper Green Larsen and Jelani Nelson , booktitle = FOCS2017, pages =. Optimality of the

  253. [261]

    Adapt or die: polynomial lower bounds for non-adaptive dynamic data structures , volume =

    Joshua Brody and Kasper Green Larsen , journal = TOC, number =. Adapt or die: polynomial lower bounds for non-adaptive dynamic data structures , volume =

  254. [262]

    Nguyen , booktitle = STOC2015, title =

    Kasper Green Larsen and Jelani Nelson and Huy L. Nguyen , booktitle = STOC2015, title =

  255. [263]

    Omri Weinstein and Huacheng Yu , booktitle = FOCS2016, title =

  256. [264]

    Huacheng Yu , booktitle = STOC2016, title =

  257. [265]

    Wang and Huacheng Yu , journal = ARXIV #

    Josh Alman and Joshua R. Wang and Huacheng Yu , journal = ARXIV #. Cell-probe lower bounds from online communication complexity , year =

  258. [266]

    Lee and Assaf Naor , journal = GAFA, number =

    James R. Lee and Assaf Naor , journal = GAFA, number =. Embedding the diamond graph in Lp and dimension reduction in L1 , volume =

  259. [267]

    Introduction to property testing , year =

    Oded Goldreich , publisher =. Introduction to property testing , year =

  260. [268]

    Alexandr Andoni and Robert Krauthgamer , title =

  261. [269]

    Kasper Green Larsen and Ryan Williams , booktitle = SODA2017, title =

  262. [270]

    Alexandr Andoni and Robert Krauthgamer , booktitle = FOCS2007, title =

  263. [271]

    Partition Expanders , volume =

    Dmitry Gavinsky and Pavel Pudl\'. Partition Expanders , volume =

  264. [272]

    Ilan Newman and Yuri Rabinovich and Deepak Rajendraprasad and Christian Sohler , booktitle = SODA2017, title =

  265. [273]

    Interpolation Spaces , year =

    J\". Interpolation Spaces , year =

  266. [274]

    Lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers , year =

    Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao , journal = ECCC #. Lower bounds on non-adaptive data structures maintaining sets of numbers, from sunflowers , year =

  267. [275]

    Tight bounds for testing bipartiteness in general graphs , volume =

    Tali Kaufman and Michael Krivelevich and Dana Ron , journal = SICOMP, number =. Tight bounds for testing bipartiteness in general graphs , volume =

  268. [276]

    Testing the diameter of graphs , volume =

    Michal Parnas and Dana Ron , journal = RSA, number =. Testing the diameter of graphs , volume =

  269. [277]

    Property testing in bounded degree graphs , volume =

    Oded Goldreich and Dana Ron , journal = ALGORITHMICA, pages =. Property testing in bounded degree graphs , volume =

  270. [278]

    Ultrametric skeletons , volume =

    Mandel Manor and Assaf Naor , journal = PNAS, number =. Ultrametric skeletons , volume =

  271. [279]

    Testing juntas , volume =

    Eldar Fischer and Guy Kindler and Dana Ron and Shmuel Safra and Alex Samordinsky , journal = JCSS, number =. Testing juntas , volume =

  272. [280]

    The non-adaptive query complexity of testing k -parities , volume =

    Harry Buhrman and David Garc\'. The non-adaptive query complexity of testing k -parities , volume =

  273. [281]

    Seshadhri , month =

    C. Seshadhri , month =. Property Testing Review: Open Problem for February 2014 , url =. 2014 , bdsk-url-1 =

    2014

  274. [282]

    Tobias Christiani , title =

  275. [283]

    Sean Moran , title =

  276. [284]

    Maxim Raginsky and Svetlana Lazebnik , booktitle = NIPS2009, title =

  277. [285]

    Jayram and David P

    Thathachar S. Jayram and David P. Woodruff , journal = TALG, number =. Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error , volume =

  278. [286]

    Grigory Yaroslavtsev , title =

  279. [287]

    Hoza and Adam R

    William M. Hoza and Adam R. Klivans , journal = ARXIV #. Preserving Randomness for Adaptive Algorithms , year =

  280. [288]

    Alexandr Andoni and Jayram, T. S. and Mihai Patrascu , booktitle = SODA2010, pages =. Lower bounds for edit distance and product metrics via Poincar\'

  281. [289]

    Yi Li and David Woodruff , booktitle = ICALP2017, title =

  282. [290]

    Yi Li and David Woodruff , booktitle = APPROXRANDOM2016, title =

  283. [291]

    Jayram and David Woodruff , booktitle = FOCS2009, title =

    Thathachar S. Jayram and David Woodruff , booktitle = FOCS2009, title =

  284. [292]

    Pythagorean power of hypercubes , year =

    Assaf Naor and Gideon Schechtman , journal = ARXIV #. Pythagorean power of hypercubes , year =

  285. [293]

    Statistical query algorithms for mean vector estimation and stochastic convex optimization , year =

    Vitaly Feldman and Crist\'. Statistical query algorithms for mean vector estimation and stochastic convex optimization , year =

  286. [294]

    Type, cotype, and convexity properties of Orlicz spaces , year =

    Anna Kami\'. Type, cotype, and convexity properties of Orlicz spaces , year =

  287. [295]

    Asymptotic theory of finite dimensional normed spaces , year =

    Vitali Milman and Gideon Schechtman , publisher =. Asymptotic theory of finite dimensional normed spaces , year =

  288. [296]

    Jacob Steinhardt and Gregory Valiant and Stefan Wager , booktitle = COLT2016, title =

  289. [297]

    Yu and Sanjiv Kumar and H

    Ananda Theertha Suresh and Felix X. Yu and Sanjiv Kumar and H. Brendan McMahan , booktitle = ICML2017, pages =. Distributed Mean Estimation with Limited Communication , year =

  290. [298]

    The Design of Competitive Online Algorithms via a Primal-Dual Approach , volume =

    Niv Buchbinder and Joseph (Seffi) Naor , journal = FTTCS, number =. The Design of Competitive Online Algorithms via a Primal-Dual Approach , volume =

  291. [299]

    MohammadTaghi HajiAghayi and Masoud Seddighin and Saeed Seddighin and Xiaorui Sun , title =

  292. [300]

    William Kuszmaul , title =

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.