cs.CC

Papers

• Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors (2016)
  Alexandr Andoni et al.
  —
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors (2019)
  Alexandr Andoni and Thijs Laarhoven and Ilya Razenshteyn and Erik Waingarten
  —
• Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube (2016)
  Paul Beame and Cyrus Rashtchian
  —
• Similarity preserving compressions of high dimensional sparse data (2016)
  Raghav Kulkarni et al.
  —
• Hypercube LSH for approximate near neighbors (2017)
  Thijs Laarhoven
  —
• Combinatorial and Asymptotical Results on the Neighborhood Grid (2023)
  Martin Skrodzki et al.
  —
• Graph-based time-space trade-offs for approximate near neighbors (2019)
  Thijs Laarhoven
  —
• Hardness of Approximate Nearest Neighbor Search (2018)
  Aviad Rubinstein
  —
• Wormhole: A Fast Ordered Index for In-memory Data Management (2019)
  Xingbo Wu et al.
  —
• An Algorithm for Reducing Approximate Nearest Neighbor to Approximate Near Neighbor with O(logn) Query Time (2018)
  Hengzhao Ma et al.
  —
• Nearest neighbor decoding for Tardos fingerprinting codes (2019)
  Thijs Laarhoven
  —
• Polytopes, lattices, and spherical codes for the nearest neighbor problem (2020)
  Thijs Laarhoven
  —
• Optimal In-place Algorithms for Basic Graph Problems (2019)
  Sankardeep Chakraborty et al.
  —
• "Sliced" Subwindow Search: a Sublinear-complexity Solution to the Maximum Rectangle Problem (2023)
  Max Reuter et al.
  —
• Hardness of Approximate Nearest Neighbor Search under L-infinity (2020)
  Young Kun Ko and Min Jae Song
  —
• The Query Complexity of Local Search and Brouwer in Rounds (2025)
  Simina Br\^anzei and Jiawei Li
  —
• Quantum walk-based search algorithms with multiple marked vertices (2022)
  G. A. Bezerra et al.
  —
• Minmax-optimal list searching with $O(\log_2\log_2 n)$ average cost (2021)
  I. F. D. Oliveira and R. H. C. Takahashi
  —
• Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr\'echet Distance (2021)
  Karl Bringmann et al.
  —
• Non-uniform quantization with linear average-case computation time (2021)
  Oswaldo Cadenas and Graham M. Megson
  —
• Paired compressed cover trees guarantee a near linear parametrized complexity for all $k$-nearest neighbors search in an arbitrary metric space (2022)
  Yury Elkin et al.
  —
• Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search (2026)
  Bar{\i}\c{s} Can Esmer et al.
  —
• Search-Space Reduction via Essential Vertices (2022)
  Benjamin Merlin Bumpus et al.
  —
• Can You Solve Closest String Faster than Exhaustive Search? (2023)
  Amir Abboud et al.
  —
• Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut (2024)
  Lukas Michel et al.
  —
• Complexity of Local Search for Euclidean Clustering Problems (2025)
  Bodo Manthey et al.
  —
• Graph Search Trees and the Intermezzo Problem (2024)
  Jesse Beisegel et al.
  —
• Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees (2024)
  Anas Al-okaily
  —
• Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times (2025)
  Kaja Balzereit et al.
  —
• Neural Networks and (Virtual) Extended Formulations (2026)
  Christoph Hertrich et al.
  —
• Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding (2026)
  Amin Shiraz Gilani et al.
  —
• Quantum Search with In-Place Queries (2025)
  Blake Holman et al.
  —
• Ineffectiveness for Search and Undecidability of PCSP Meta-Problems (2026)
  Alberto Larrauri
  —
• An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem (2025)
  Yang Yang
  —
• Finding One Local Optimum Is Easy -- but What About Two? (2025)
  Yasuaki Kobayashi et al.
  —
• Attractors Is All You Need: Parity Games In Polynomial Time (2025)
  Rick van der Heijden
  —
• The Query Complexity of Local Search in Rounds on General Graphs (2026)
  Simina Br\^anzei and Ioannis Panageas and Dimitris Paparas
  —
• Learning Decision-Sufficient Representations for Linear Optimization (2026)
  Yuhan Ye et al.
  —
• Breadth-First Search Trees with Many or Few Leaves (2026)
  Jesse Beisegel et al.
  —
• Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses (2026)
  Yuhan Ye
  —
• The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems (2026)
  Dongxin Guo
  —
• A computational phase transition for learning-to-sample from Ising models (2026)
  Andrej Risteski et al.
  —
• Approximate Algorithms for Chamfer Distance Under Translation (2026)
  Gil Halevi et al.
  —
• A Note on Approximability of Densest At-Least-k-Subgraph (2026)
  Bundit Laekhanukit et al.
  —
• Low Soundness Linearity Testing on the Half-Slice (2026)
  Haakon Larsen et al.
  —
• The Complexity of Verifying Feedforward Neural Networks in Quantised Settings (2026)
  Eric Alsmann et al.
  —
• Elfs, transducers and quantum walks (2026)
  Simon Apers et al.
  —
• Low-degree estimation thresholds in planted hypergraphs and tensor PCA (2026)
  Daniel Fu et al.
  —