Topological Lower Bounds on Algebraic Random Access Machines

DOI10.1137/S0097539797329397zbMath1017.68057OpenAlexW2071301548MaRDI QIDQ2784478

Amir M. Ben-Amram, Zvi Galil

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797329397

zbMATH Keywords

knapsackalgebraic computation treeselement distinctnesscomponent counting arguments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Optimally computing all solutions of Stackelberg with parametric prices and of general monotonous gain functions on a tree