Towards polynomial lower bounds for dynamic problems
From MaRDI portal
Publication:2875187
DOI10.1145/1806689.1806772zbMath1293.68153WikidataQ56288892 ScholiaQ56288892MaRDI QIDQ2875187
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806772
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Faster All-Pairs Shortest Paths via Circuit Complexity, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, From Circuit Complexity to Faster All-Pairs Shortest Paths, The minrank of random graphs, A subquadratic algorithm for 3XOR, Improved Time and Space Bounds for Dynamic Range Mode, Smallest k-enclosing rectangle revisited, On Multidimensional and Monotone k-SUM, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Exact Weight Subgraphs and the k-Sum Conjecture, Unnamed Item, Unnamed Item, Parameterized aspects of triangle enumeration, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Deterministic dynamic matching in worst-case update time, On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, Internal masked prefix sums and its connection to fully internal measurement queries, How fast can we play Tetris greedily with rectangular pieces?, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Improved Merlin-Arthur protocols for central problems in fine-grained complexity, Communication and information complexity, 3SUM, 3XOR, triangles, Improved subquadratic 3SUM, Quantum algorithm for triangle finding in sparse graphs, Capturing points with a rotating polygon (and a 3D extension), Smallest \(k\)-enclosing rectangle revisited, Dynamic data structures for timed automata acceptance, A comparative study of dictionary matching with gaps: limitations, techniques and challenges, Online recognition of dictionary with one gap, Linear-space data structures for range mode query in arrays, Improved analysis of the online set cover problem with advice, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, Mind the gap!, Subquadratic algorithms for algebraic 3SUM, Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy, Upper and Lower Bounds on the Power of Advice, Dynamic Set Intersection
