default search action
Amir M. Ben-Amram
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 1995
- [b1]Amir M. Ben-Amram:
On the power of random access machines. Tel Aviv University, Israel, 1995
Journal Articles
- 2025
- [j37]Amir M. Ben-Amram, Lars Kristiansen:
A degree structure on representations of irrational numbers. J. Log. Anal. 17 (2025) - 2021
- [j36]Amir M. Ben-Amram, Geoff W. Hamilton
:
Tight Polynomial Bounds for Loop Programs in Polynomial Space. Log. Methods Comput. Sci. 17(4) (2021) - 2020
- [j35]Amir M. Ben-Amram, Geoff W. Hamilton
Tight Polynomial Worst-Case Bounds for Loop Programs. Log. Methods Comput. Sci. 16(2) (2020) - 2015
- [j34]Amir M. Ben-Amram:
Mortality of iterated piecewise affine functions over the integers: Decidability and complexity. Comput. 4(1): 19-56 (2015) - 2014
- [j33]Amir M. Ben-Amram, Samir Genaim
Ranking Functions for Linear-Constraint Loops. J. ACM 61(4): 26:1-26:55 (2014) - 2012
- [j32]Amir M. Ben-Amram, Niels H. Christensen, Jakob Grue Simonsen:
Computational Models with No Linear Speedup. Chic. J. Theor. Comput. Sci. 2012 (2012) - [j31]Amir M. Ben-Amram, Lars Kristiansen:
On the Edge of Decidability in Complexity Analysis of Loop Programs. Int. J. Found. Comput. Sci. 23(7): 1451-1464 (2012) - [j30]Amir M. Ben-Amram, Bruno Loff
Monotonicity Constraints in Characterizations of PSPACE. J. Log. Comput. 22(2): 179-195 (2012) - [j29]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: 75 (2012) - [j28]Amir M. Ben-Amram, Samir Genaim
On the Termination of Integer Loops. ACM Trans. Program. Lang. Syst. 34(4): 16:1-16:24 (2012) - 2011
- [j27]Amir M. Ben-Amram:
Monotonicity Constraints for Termination in the Integer Domain. Log. Methods Comput. Sci. 7(3) (2011) - [j26]Amir M. Ben-Amram, Simon Yoffe:
A simple and efficient Union-Find-Delete algorithm. Theor. Comput. Sci. 412(4-5): 487-492 (2011) - [j25]Michael Codish
SAT-based termination analysis using monotonicity constraints over the integers. Theory Pract. Log. Program. 11(4-5): 503-520 (2011) - 2010
- [j24]Amir M. Ben-Amram:
Size-Change Termination, Monotonicity Constraints and Ranking Functions. Log. Methods Comput. Sci. 6(3) (2010) - 2009
- [j23]Amir M. Ben-Amram:
A complexity tradeoff in ranking-function termination proofs. Acta Informatica 46(1): 57-72 (2009) - [j22]Amir M. Ben-Amram, Chin Soon Lee:
Ranking Functions for Size-Change Termination II. Log. Methods Comput. Sci. 5(2) (2009) - 2008
- [j21]Amir M. Ben-Amram:
Size-change termination with difference constraints. ACM Trans. Program. Lang. Syst. 30(3): 16:1-16:31 (2008) - 2007
- [j20]Amir M. Ben-Amram, Chin Soon Lee:
Program termination analysis in polynomial time. ACM Trans. Program. Lang. Syst. 29(1): 5:1-5:37 (2007) - 2006
- [j19]Amir M. Ben-Amram, Holger Petersen:
Backing up in singly linked lists. J. ACM 53(4): 681-705 (2006) - 2005
- [j18]Amir M. Ben-Amram:
The Church-Turing thesis and its look-alikes. SIGACT News 36(3): 113-114 (2005) - 2004
- [j17]Amir M. Ben-Amram:
A complexity-theoretic proof of a Recursion-Theoretic Theorem. SIGACT News 35(2): 111-112 (2004) - 2003
- [j16]Amir M. Ben-Amram, Omer Berkman, Holger Petersen:
Element distinctness on one-tape Turing machines: a complete solution. Acta Informatica 40(2): 81-94 (2003) - [j15]Amir M. Ben-Amram:
Tighter constant-factor time hierarchies. Inf. Process. Lett. 87(1): 39-44 (2003) - 2002
- [j14]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds for Dynamic Data Structures on Algebraic RAMs. Algorithmica 32(3): 364-395 (2002) - [j13]Amir M. Ben-Amram, Holger Petersen:
Improved Bounds for Functions Related to Busy Beavers. Theory Comput. Syst. 35(1): 1-11 (2002) - 2001
- [j12]Amir M. Ben-Amram, Zvi Galil:
A Generalization of a Lower Bound Technique due to Fredman and Saks. Algorithmica 30(1): 34-66 (2001) - [j11]Amir M. Ben-Amram, Zvi Galil:
Topological Lower Bounds on Algebraic Random Access Machines. SIAM J. Comput. 31(3): 722-761 (2001) - 2000
- [j10]Amir M. Ben-Amram, Neil D. Jones:
Computational complexity via programming languages: constant factors do matter. Acta Informatica 37(2): 83-120 (2000) - 1999
- [j9]Amir M. Ben-Amram, Neil D. Jones:
A Precise Version of a Time Hierarchy Theorem. Fundam. Informaticae 38(1-2): 1-15 (1999) - 1998
- [j8]Amir M. Ben-Amram:
Introducing: Reasonable Complete Programming Languages. Bull. EATCS 64 (1998) - 1997
- [j7]Amir M. Ben-Amram:
When Can We Sort in o(n log n) Time? J. Comput. Syst. Sci. 54(2): 345-370 (1997) - 1996
- [j6]Amir M. Ben-Amram, Bryant A. Julstrom, Uri Zwick:
A Note on Busy Beavers and Other Creatures. Math. Syst. Theory 29(4): 375-386 (1996) - 1995
- [j5]Amir M. Ben-Amram, Zvi Galil:
On the Power of the Shift Instruction. Inf. Comput. 117(1): 19-36 (1995) - [j4]Amir M. Ben-Amram:
What is a "pointer machine"? SIGACT News 26(2): 88-95 (1995) - 1994
- [j3]Amir M. Ben-Amram:
Unit-Cost Pointers versus Logarithmic-Cost Addresses. Theor. Comput. Sci. 132(2): 377-385 (1994) - 1992
- [j2]Amir M. Ben-Amram, Zvi Galil:
On Pointers versus Addresses. J. ACM 39(3): 617-648 (1992) - 1991
- [j1]Amir M. Ben-Amram:
Some notions on notations. SIGACT News 22(4): 60-62 (1991)
Conference and Workshop Papers
- 2019
- [c24]Amir M. Ben-Amram, Geoff W. Hamilton
Tight Worst-Case Bounds for Polynomial Loop Programs. FoSSaCS 2019: 80-97 - [c23]Amir M. Ben-Amram, Jesús J. Doménech, Samir Genaim
Multiphase-Linear Ranking Functions and Their Relation to Recurrent Sets. SAS 2019: 459-480 - 2017
- [c22]Amir M. Ben-Amram, Samir Genaim
On Multiphase-Linear Ranking Functions. CAV (2) 2017: 601-620 - 2016
- [c21]Amir M. Ben-Amram, Aviad Pineles:
Flowchart Programs, Regular Expressions, and Decidability of Polynomial Growth-Rate. VPT@ETAPS 2016: 24-49 - 2015
- [c20]Amir M. Ben-Amram, Samir Genaim
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions. CAV (2) 2015: 304-321 - 2014
- [c19]Amir M. Ben-Amram:
The Hardness of Finding Linear Ranking Functions for Lasso Programs. GandALF 2014: 32-45 - 2013
- [c18]Amir M. Ben-Amram:
Ranking Functions for Linear-Constraint Loops. VPT@CAV 2013: 1-8 - [c17]Amir M. Ben-Amram, Samir Genaim
On the linear ranking problem for integer linear-constraint loops. POPL 2013: 51-62 - [c16]Amir M. Ben-Amram:
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract). STACS 2013: 514-525 - 2012
- [c15]Amir M. Ben-Amram, Samir Genaim
On the Termination of Integer Loops. VMCAI 2012: 72-87 - 2010
- [c14]Amir M. Ben-Amram:
On Decidable Growth-Rate Properties of Imperative Programs. DICE 2010: 1-14 - 2009
- [c13]Amir M. Ben-Amram:
Size-Change Termination, Monotonicity Constraints and Ranking Functions. CAV 2009: 109-123 - 2008
- [c12]Amir M. Ben-Amram, Neil D. Jones, Lars Kristiansen:
Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time. CiE 2008: 67-76 - [c11]Amir M. Ben-Amram, Michael Codish
A SAT-Based Approach to Size Change Termination with Global Ranking Functions. TACAS 2008: 218-232 - 2002
- [c10]Amir M. Ben-Amram:
General Size-Change Termination and Lexicographic Descent. The Essence of Computation 2002: 3-17 - 2001
- [c9]Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram:
The size-change principle for program termination. POPL 2001: 81-92 - 1999
- [c8]Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe:
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). STOC 1999: 499-506 - [c7]Amir M. Ben-Amram, Holger Petersen:
Backing Up in Singly Linked Lists. STOC 1999: 780-786 - 1998
- [c6]Amir M. Ben-Amram, Holger Petersen:
CONS-Free Programs with Tree Input (Extended Abstract). ICALP 1998: 271-282 - 1995
- [c5]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds on Algebraic Random Access Machines (Extended Abstract). ICALP 1995: 360-371 - 1994
- [c4]Amir M. Ben-Amram, Omer Berkman, Costas S. Iliopoulos, Kunsoo Park:
The Subtree Max Gap Problem with Application to Parallel String Covering. SODA 1994: 501-510 - 1993
- [c3]Amir M. Ben-Amram, Zvi Galil:
When can we sort in o(n log n) time? FOCS 1993: 538-546 - 1991
- [c2]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract). FOCS 1991: 622-631 - 1988
- [c1]Amir M. Ben-Amram, Zvi Galil:
On Pointers versus Addresses (Extended Abstract). FOCS 1988: 532-538
Informal and Other Publications
- 2025
- [i13]Amir M. Ben-Amram, Samir Genaim, Joël Ouaknine, James Worrell:
Termination Analysis of Linear-Constraint Programs. CoRR abs/2509.06752 (2025) - 2023
- [i12]Amir M. Ben-Amram, Lars Kristiansen, Jakob Grue Simonsen:
On representations of real numbers and the computational complexity of converting between such representations. CoRR abs/2304.07227 (2023) - 2020
- [i11]Amir M. Ben-Amram, Geoff W. Hamilton:
Tight Polynomial Bounds for Loop Programs in Polynomial Space. CoRR abs/2010.02823 (2020) - 2019
- [i10]Amir M. Ben-Amram, Geoff W. Hamilton:
Tight Polynomial Worst-Case Bounds for Loop Programs. CoRR abs/1906.10047 (2019) - 2018
- [i9]Amir M. Ben-Amram, Jesús Doménech, Samir Genaim:
Multiphase-Linear Ranking Functions and their Relation to Recurrent Sets. CoRR abs/1811.07340 (2018) - 2017
- [i8]Amir M. Ben-Amram, Samir Genaim:
On Multiphase-Linear Ranking Functions. CoRR abs/1703.07547 (2017) - 2015
- [i7]Amir M. Ben-Amram, Samir Genaim:
Complexity of Bradley-Manna-Sipma Lexicographic Ranking Functions. CoRR abs/1504.05018 (2015) - 2013
- [i6]Amir M. Ben-Amram:
A Comment on Budach's Mouse-in-an-Octant Problem. CoRR abs/1305.0911 (2013) - 2012
- [i5]Amir M. Ben-Amram, Michael Vainer:
Bounded Termination of Monotonicity-Constraint Transition Systems. CoRR abs/1202.4281 (2012) - [i4]Amir M. Ben-Amram, Samir Genaim:
On the Linear Ranking Problem for Integer Linear-Constraint Loops. CoRR abs/1208.4041 (2012) - 2011
- [i3]Michael Codish, Igor Gonopolskiy, Amir M. Ben-Amram, Carsten Fuhs, Jürgen Giesl:
SAT-Based Termination Analysis Using Monotonicity Constraints over the Integers. CoRR abs/1107.5980 (2011) - 2009
- [i2]Amir M. Ben-Amram:
The Euler Path to Static Level-Ancestors. CoRR abs/0909.1030 (2009) - 1995
- [i1]Amir M. Ben-Amram, Zvi Galil:
On Data Structure Tradeoffs and an Application to Union-Find. Electron. Colloquium Comput. Complex. TR95 (1995)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-10-28 22:51 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: