Clustered Integer 3SUM via Additive Combinatorics
From MaRDI portal
Publication:2941486
DOI10.1145/2746539.2746568zbMath1321.68299arXiv1502.05204OpenAlexW2031683606MaRDI QIDQ2941486
Timothy M. Chan, Moshe Lewenstein
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.05204
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (32)
Weighted prefix normal words: mind the gap ⋮ Permuted scaled matching ⋮ Inside the binary reflected gray code: flip-swap languages in 2-gray code order ⋮ Extreme Witnesses and Their Applications ⋮ Fast algorithms for abelian periods in words and greatest common divisor queries ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Unnamed Item ⋮ Longest common substring with approximately \(k\) mismatches ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Flip-swap languages in binary reflected Gray code order ⋮ Improved bounds for rectangular monotone min-plus product and applications ⋮ General space-time tradeoffs via relational queries ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ A polyhedral perspective on tropical convolutions ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ Hardness of RNA folding problem with four symbols ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ A subquadratic algorithm for 3XOR ⋮ Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ Unnamed Item ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ On prefix normal words and prefix normal forms ⋮ Extreme witnesses and their applications ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ On infinite prefix normal words ⋮ Smallest k-enclosing rectangle revisited ⋮ On Integer Programming and Convolution. ⋮ On Multidimensional and Monotone k-SUM ⋮ Bubble-flip -- a new generation algorithm for prefix normal words
Uses Software
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
This page was built for publication: Clustered Integer 3SUM via Additive Combinatorics
