Amir M. Ben-Amram

According to our database, Amir M. Ben-Amram authored at least 63 papers between 1988 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

On representations of real numbers and the computational complexity of converting between such representations.

Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen

CoRR, 2023

2021

Tight Polynomial Bounds for Loop Programs in Polynomial Space.

Amir M. Ben-Amram, Geoff W. Hamilton

Log. Methods Comput. Sci., 2021

2020

Tight Polynomial Worst-Case Bounds for Loop Programs.

Amir M. Ben-Amram, Geoff W. Hamilton

Log. Methods Comput. Sci., 2020

2019

Multiphase-Linear Ranking Functions and Their Relation to Recurrent Sets.

Amir M. Ben-Amram, Jesús J. Doménech, Samir Genaim

Proceedings of the Static Analysis - 26th International Symposium, 2019

Tight Worst-Case Bounds for Polynomial Loop Programs.

Amir M. Ben-Amram, Geoff W. Hamilton

Proceedings of the Foundations of Software Science and Computation Structures, 2019

2017

On Multiphase-Linear Ranking Functions.

Amir M. Ben-Amram, Samir Genaim

Proceedings of the Computer Aided Verification - 29th International Conference, 2017

2016

Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate.

Amir M. Ben-Amram, Aviad Pineles

Proceedings of the Fourth International Workshop on Verification and Program Transformation, 2016

2015

Mortality of iterated piecewise affine functions over the integers: Decidability and complexity.

Amir M. Ben-Amram

Comput., 2015

Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions.

Amir M. Ben-Amram, Samir Genaim

Proceedings of the Computer Aided Verification - 27th International Conference, 2015

2014

Ranking Functions for Linear-Constraint Loops.

Amir M. Ben-Amram, Samir Genaim

J. ACM, 2014

The Hardness of Finding Linear Ranking Functions for Lasso Programs.

Amir M. Ben-Amram

Proceedings of the Proceedings Fifth International Symposium on Games, 2014

2013

A Comment on Budach's Mouse-in-an-Octant Problem

Amir M. Ben-Amram

CoRR, 2013

Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract).

Amir M. Ben-Amram

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

On the linear ranking problem for integer linear-constraint loops.

Amir M. Ben-Amram, Samir Genaim

Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2013

Ranking Functions for Linear-Constraint Loops.

Amir M. Ben-Amram

Proceedings of the First International Workshop on Verification and Program Transformation, 2013

2012

On the Termination of Integer Loops.

Amir M. Ben-Amram, Samir Genaim, Abu Naser Masud

ACM Trans. Program. Lang. Syst., 2012

Corrigendum to "A simple and efficient Union-Find-Delete algorithm" [Theoret. Comput. Sci. 412(4-5) 487-492].

Amir M. Ben-Amram, Simon Yoffe

Theor. Comput. Sci., 2012

Monotonicity Constraints in Characterizations of PSPACE.

Amir M. Ben-Amram, Bruno Loff, Isabel Oitavem

J. Log. Comput., 2012

On the Edge of Decidability in Complexity Analysis of Loop Programs.

Amir M. Ben-Amram, Lars Kristiansen

Int. J. Found. Comput. Sci., 2012

Bounded Termination of Monotonicity-Constraint Transition Systems

Amir M. Ben-Amram, Michael Vainer

CoRR, 2012

Computational Models with No Linear Speedup.

Amir M. Ben-Amram, Niels H. Christensen, Jakob Grue Simonsen

Chic. J. Theor. Comput. Sci., 2012

2011

SAT-based termination analysis using monotonicity constraints over the integers.

Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl

Theory Pract. Log. Program., 2011

A simple and efficient Union-Find-Delete algorithm.

Amir M. Ben-Amram, Simon Yoffe

Theor. Comput. Sci., 2011

Monotonicity Constraints for Termination in the Integer Domain

Amir M. Ben-Amram

Log. Methods Comput. Sci., 2011

2010

On Decidable Growth-Rate Properties of Imperative Programs

Amir M. Ben-Amram

Proceedings of the Proceedings International Workshop on Developments in Implicit Computational complExity, 2010

Size-Change Termination, Monotonicity Constraints and Ranking Functions

Amir M. Ben-Amram

Log. Methods Comput. Sci., 2010

2009

The Euler Path to Static Level-Ancestors

Amir M. Ben-Amram

CoRR, 2009

Ranking Functions for Size-Change Termination II

Amir M. Ben-Amram, Chin Soon Lee

Log. Methods Comput. Sci., 2009

A complexity tradeoff in ranking-function termination proofs.

Amir M. Ben-Amram

Acta Informatica, 2009

2008

Size-change termination with difference constraints.

Amir M. Ben-Amram

ACM Trans. Program. Lang. Syst., 2008

A SAT-Based Approach to Size Change Termination with Global Ranking Functions.

Amir M. Ben-Amram, Michael Codish

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2008

Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.

Amir M. Ben-Amram, Neil D. Jones, Lars Kristiansen

Proceedings of the Logic and Theory of Algorithms, 2008

2007

Program termination analysis in polynomial time.

Amir M. Ben-Amram, Chin Soon Lee

ACM Trans. Program. Lang. Syst., 2007

2006

Backing up in singly linked lists.

Amir M. Ben-Amram, Holger Petersen

J. ACM, 2006

2005

The Church-Turing thesis and its look-alikes.

Amir M. Ben-Amram

SIGACT News, 2005

2004

A complexity-theoretic proof of a Recursion-Theoretic Theorem.

Amir M. Ben-Amram

SIGACT News, 2004

2003

Tighter constant-factor time hierarchies.

Amir M. Ben-Amram

Inf. Process. Lett., 2003

Element distinctness on one-tape Turing machines: a complete solution.

Amir M. Ben-Amram, Omer Berkman, Holger Petersen

Acta Informatica, 2003

2002

Improved Bounds for Functions Related to Busy Beavers.

Amir M. Ben-Amram, Holger Petersen

Theory Comput. Syst., 2002

Lower Bounds for Dynamic Data Structures on Algebraic RAMs.

Amir M. Ben-Amram, Zvi Galil

Algorithmica, 2002

General Size-Change Termination and Lexicographic Descent.

Amir M. Ben-Amram

Proceedings of the Essence of Computation, Complexity, Analysis, 2002

2001

Topological Lower Bounds on Algebraic Random Access Machines.

Amir M. Ben-Amram, Zvi Galil

SIAM J. Comput., 2001

A Generalization of a Lower Bound Technique due to Fredman and Saks.

Amir M. Ben-Amram, Zvi Galil

Algorithmica, 2001

The size-change principle for program termination.

Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram

Proceedings of the Conference Record of POPL 2001: The 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2001

2000

Computational complexity via programming languages: constant factors do matter.

Amir M. Ben-Amram, Neil D. Jones

Acta Informatica, 2000

1999

A Precise Version of a Time Hierarchy Theorem.

Amir M. Ben-Amram, Neil D. Jones

Fundam. Informaticae, 1999

Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).

Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Introducing: Reasonable Complete Programming Languages.

Amir M. Ben-Amram

Bull. EATCS, 1998

CONS-Free Programs with Tree Input (Extended Abstract).

Amir M. Ben-Amram, Holger Petersen

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

When Can We Sort in o(n log n) Time?

Amir M. Ben-Amram

J. Comput. Syst. Sci., 1997

1996

A Note on Busy Beavers and Other Creatures.

Amir M. Ben-Amram, Bryant A. Julstrom, Uri Zwick

Math. Syst. Theory, 1996

1995

On the Power of the Shift Instruction

Amir M. Ben-Amram, Zvi Galil

Inf. Comput., February, 1995

On the power of random access machines

Amir M. Ben-Amram

PhD thesis, 1995

What is a "pointer machine"?

Amir M. Ben-Amram

SIGACT News, 1995

On Data Structure Tradeoffs and an Application to Union-Find

Amir M. Ben-Amram, Zvi Galil

Electron. Colloquium Comput. Complex., 1995

Lower Bounds on Algebraic Random Access Machines (Extended Abstract).

Amir M. Ben-Amram, Zvi Galil

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

Unit-Cost Pointers versus Logarithmic-Cost Addresses.

Amir M. Ben-Amram

Theor. Comput. Sci., 1994

The Subtree Max Gap Problem with Application to Parallel String Covering.

Amir M. Ben-Amram, Omer Berkman, Costas S. Iliopoulos, Kunsoo Park

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

When can we sort in o(n log n) time?

Amir M. Ben-Amram, Zvi Galil

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

On Pointers versus Addresses.

Amir M. Ben-Amram, Zvi Galil

J. ACM, 1992

1991

Some notions on notations.

Amir M. Ben-Amram

SIGACT News, 1991

Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)

Amir M. Ben-Amram, Zvi Galil

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1988

On Pointers versus Addresses (Extended Abstract)

Amir M. Ben-Amram, Zvi Galil

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988