Amir M. Ben-Amram

Publication Activity (10 Years)

Years Active: 1988-2023
Publications (10 Years): 11

Top Topics

Piecewise Affine

Ranking Functions

Polynomially Bounded

Top Venues

Log. Methods Comput. Sci.

Publications

Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen
On representations of real numbers and the computational complexity of converting between such representations. CoRR (2023)
Amir M. Ben-Amram, Geoff W. Hamilton
Tight Polynomial Bounds for Loop Programs in Polynomial Space. Log. Methods Comput. Sci. 17 (4) (2021)
Amir M. Ben-Amram, Geoff W. Hamilton
Tight Polynomial Bounds for Loop Programs in Polynomial Space. CoRR (2020)
Amir M. Ben-Amram, Geoff W. Hamilton
Tight Polynomial Worst-Case Bounds for Loop Programs. Log. Methods Comput. Sci. 16 (2) (2020)
Amir M. Ben-Amram, Jesús J. Doménech, Samir Genaim
Multiphase-Linear Ranking Functions and Their Relation to Recurrent Sets. SAS (2019)
Amir M. Ben-Amram, Geoff W. Hamilton
Tight Polynomial Worst-Case Bounds for Loop Programs. CoRR (2019)
Amir M. Ben-Amram, Geoff W. Hamilton
Tight Worst-Case Bounds for Polynomial Loop Programs. FoSSaCS (2019)
Amir M. Ben-Amram, Jesús Doménech, Samir Genaim
Multiphase-Linear Ranking Functions and their Relation to Recurrent Sets. CoRR (2018)
Amir M. Ben-Amram, Samir Genaim
On Multiphase-Linear Ranking Functions. CAV (2) (2017)
Amir M. Ben-Amram, Samir Genaim
On Multiphase-Linear Ranking Functions. CoRR (2017)
Amir M. Ben-Amram, Aviad Pineles
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate. VPT@ETAPS (2016)
Amir M. Ben-Amram, Samir Genaim
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions. CoRR (2015)
Amir M. Ben-Amram, Samir Genaim
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions. CAV (2) (2015)
Amir M. Ben-Amram
Mortality of iterated piecewise affine functions over the integers: Decidability and complexity. Comput. 4 (1) (2015)
Amir M. Ben-Amram
The Hardness of Finding Linear Ranking Functions for Lasso Programs. GandALF (2014)
Amir M. Ben-Amram, Samir Genaim
Ranking Functions for Linear-Constraint Loops. J. ACM 61 (4) (2014)
Amir M. Ben-Amram
A Comment on Budach's Mouse-in-an-Octant Problem CoRR (2013)
Amir M. Ben-Amram
Ranking Functions for Linear-Constraint Loops. VPT@CAV (2013)
Amir M. Ben-Amram, Samir Genaim
On the linear ranking problem for integer linear-constraint loops. POPL (2013)
Amir M. Ben-Amram
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract). STACS (2013)
Amir M. Ben-Amram, Niels H. Christensen, Jakob Grue Simonsen
Computational Models with No Linear Speedup. Chic. J. Theor. Comput. Sci. 2012 (2012)
Amir M. Ben-Amram, Simon Yoffe
Corrigendum to "A simple and efficient Union-Find-Delete algorithm" [Theoret. Comput. Sci. 412(4-5) 487-492]. Theor. Comput. Sci. 423 (2012)
Amir M. Ben-Amram, Samir Genaim, Abu Naser Masud
On the Termination of Integer Loops. ACM Trans. Program. Lang. Syst. 34 (4) (2012)
Amir M. Ben-Amram, Lars Kristiansen
On the Edge of Decidability in Complexity Analysis of Loop Programs. Int. J. Found. Comput. Sci. 23 (7) (2012)
Amir M. Ben-Amram, Michael Vainer
Bounded Termination of Monotonicity-Constraint Transition Systems CoRR (2012)
Amir M. Ben-Amram, Samir Genaim, Abu Naser Masud
On the Termination of Integer Loops. VMCAI (2012)
Amir M. Ben-Amram, Samir Genaim
On the Linear Ranking Problem for Integer Linear-Constraint Loops CoRR (2012)
Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem
Monotonicity Constraints in Characterizations of PSPACE. J. Log. Comput. 22 (2) (2012)
Amir M. Ben-Amram, Simon Yoffe
A simple and efficient Union-Find-Delete algorithm. Theor. Comput. Sci. 412 (4-5) (2011)
Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl
SAT-based termination analysis using monotonicity constraints over the integers. Theory Pract. Log. Program. 11 (4-5) (2011)
Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl
SAT-Based Termination Analysis Using Monotonicity Constraints over the Integers CoRR (2011)
Amir M. Ben-Amram
Monotonicity Constraints for Termination in the Integer Domain Log. Methods Comput. Sci. 7 (3) (2011)
Amir M. Ben-Amram
On Decidable Growth-Rate Properties of Imperative Programs DICE (2010)
Amir M. Ben-Amram
Size-Change Termination, Monotonicity Constraints and Ranking Functions Log. Methods Comput. Sci. 6 (3) (2010)
Amir M. Ben-Amram
A complexity tradeoff in ranking-function termination proofs. Acta Informatica 46 (1) (2009)
Amir M. Ben-Amram
The Euler Path to Static Level-Ancestors CoRR (2009)
Amir M. Ben-Amram, Chin Soon Lee
Ranking Functions for Size-Change Termination II Log. Methods Comput. Sci. 5 (2) (2009)
Amir M. Ben-Amram
Size-Change Termination, Monotonicity Constraints and Ranking Functions. CAV (2009)
Amir M. Ben-Amram, Michael Codish
A SAT-Based Approach to Size Change Termination with Global Ranking Functions. TACAS (2008)
Amir M. Ben-Amram, Neil D. Jones, Lars Kristiansen
Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time. CiE (2008)
Amir M. Ben-Amram
Size-change termination with difference constraints. ACM Trans. Program. Lang. Syst. 30 (3) (2008)
Amir M. Ben-Amram, Chin Soon Lee
Program termination analysis in polynomial time. ACM Trans. Program. Lang. Syst. 29 (1) (2007)
Amir M. Ben-Amram, Holger Petersen
Backing up in singly linked lists. J. ACM 53 (4) (2006)
Amir M. Ben-Amram
The Church-Turing thesis and its look-alikes. SIGACT News 36 (3) (2005)
Amir M. Ben-Amram
A complexity-theoretic proof of a Recursion-Theoretic Theorem. SIGACT News 35 (2) (2004)
Amir M. Ben-Amram, Omer Berkman, Holger Petersen
Element distinctness on one-tape Turing machines: a complete solution. Acta Informatica 40 (2) (2003)
Amir M. Ben-Amram
Tighter constant-factor time hierarchies. Inf. Process. Lett. 87 (1) (2003)
Amir M. Ben-Amram, Holger Petersen
Improved Bounds for Functions Related to Busy Beavers. Theory Comput. Syst. 35 (1) (2002)
Amir M. Ben-Amram, Zvi Galil
Lower Bounds for Dynamic Data Structures on Algebraic RAMs. Algorithmica 32 (3) (2002)
Amir M. Ben-Amram
General Size-Change Termination and Lexicographic Descent. The Essence of Computation (2002)
Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram
The size-change principle for program termination. POPL (2001)
Amir M. Ben-Amram, Zvi Galil
A Generalization of a Lower Bound Technique due to Fredman and Saks. Algorithmica 30 (1) (2001)
Amir M. Ben-Amram, Zvi Galil
Topological Lower Bounds on Algebraic Random Access Machines. SIAM J. Comput. 31 (3) (2001)
Amir M. Ben-Amram, Neil D. Jones
Computational complexity via programming languages: constant factors do matter. Acta Informatica 37 (2) (2000)
Amir M. Ben-Amram, Neil D. Jones
A Precise Version of a Time Hierarchy Theorem. Fundam. Informaticae 38 (1-2) (1999)
Amir M. Ben-Amram, Holger Petersen
Backing Up in Singly Linked Lists. STOC (1999)
Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). STOC (1999)
Amir M. Ben-Amram
Introducing: Reasonable Complete Programming Languages. Bull. EATCS 64 (1998)
Amir M. Ben-Amram, Holger Petersen
CONS-Free Programs with Tree Input (Extended Abstract). ICALP (1998)
Amir M. Ben-Amram
When Can We Sort in o(n log n) Time? J. Comput. Syst. Sci. 54 (2) (1997)
Amir M. Ben-Amram, Bryant A. Julstrom, Uri Zwick
A Note on Busy Beavers and Other Creatures. Math. Syst. Theory 29 (4) (1996)
Amir M. Ben-Amram
What is a "pointer machine"? SIGACT News 26 (2) (1995)
Amir M. Ben-Amram, Zvi Galil
On Data Structure Tradeoffs and an Application to Union-Find Electron. Colloquium Comput. Complex. 2 (62) (1995)
Amir M. Ben-Amram, Zvi Galil
Lower Bounds on Algebraic Random Access Machines (Extended Abstract). ICALP (1995)
Amir M. Ben-Amram, Zvi Galil
On the Power of the Shift Instruction Inf. Comput. 117 (1) (1995)
Amir M. Ben-Amram
Unit-Cost Pointers versus Logarithmic-Cost Addresses. Theor. Comput. Sci. 132 (2) (1994)
Amir M. Ben-Amram, Omer Berkman, Costas S. Iliopoulos, Kunsoo Park
The Subtree Max Gap Problem with Application to Parallel String Covering. SODA (1994)
Amir M. Ben-Amram, Zvi Galil
When can we sort in o(n log n) time? FOCS (1993)
Amir M. Ben-Amram, Zvi Galil
On Pointers versus Addresses. J. ACM 39 (3) (1992)
Amir M. Ben-Amram, Zvi Galil
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract) FOCS (1991)
Amir M. Ben-Amram
Some notions on notations. SIGACT News 22 (4) (1991)
Amir M. Ben-Amram, Zvi Galil
On Pointers versus Addresses (Extended Abstract) FOCS (1988)