Lower bounds on algebraic random access machines

DOI10.1007/3-540-60084-1_88zbMath1412.68057OpenAlexW69585534MaRDI QIDQ4645192

Amir M. Ben-Amram, Zvi Galil

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_88

zbMATH Keywords

knapsack problemrandom access machinecomputation treememory addresselement distinctness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower time bound for the knapsack problem on random access machines
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Fast exponentiation using the truncation operation
• Lower Bounds for Computations with the Floor Operation
• Lower Bounds for Sorting with Realistic Instruction Sets
• Lower bounds for solving linear diophantine equations on random access machines
• On computations with integer division
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• A lower bound for integer greatest common divisor computations
• On genuinely time bounded computations
• Decision tree complexity and Betti numbers