Lower bounds on algebraic random access machines

DOI10.1007/3-540-60084-1_88zbMATH Open1412.68057OpenAlexW69585534MaRDI QIDQ4645192FDOQ4645192

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

Recommendations

• Topological lower bounds on algebraic random access machines
• On the complexity of functions for random access machines
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• Lower bounds for RAMs and quantifier elimination
• Feasible real random access machines

zbMATH Keywords

knapsack problemrandom access machinecomputation treeelement distinctnessmemory address

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• A nonlinear lower bound for random-access machines under logarithmic cost
• Topological lower bounds on algebraic random access machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds for dynamic data structures on algebraic RAMs
• A problem that is easier to solve on the unit-cost algebraic RAM
• Lower bounds for solving linear diophantine equations on random access machines
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• Title not available (Why is that?)

This page was built for publication: Lower bounds on algebraic random access machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645192)