2009 |
34 | EE | Amir M. Ben-Amram:
A complexity tradeoff in ranking-function termination proofs.
Acta Inf. 46(1): 57-72 (2009) |
33 | EE | Amir M. Ben-Amram,
Chin Soon Lee:
Ranking Functions for Size-Change Termination II
CoRR abs/0903.4382: (2009) |
2008 |
32 | EE | Amir M. Ben-Amram,
Neil D. Jones,
Lars Kristiansen:
Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.
CiE 2008: 67-76 |
31 | EE | Amir M. Ben-Amram,
Michael Codish:
A SAT-Based Approach to Size Change Termination with Global Ranking Functions.
TACAS 2008: 218-232 |
30 | EE | Amir M. Ben-Amram:
Size-change termination with difference constraints.
ACM Trans. Program. Lang. Syst. 30(3): (2008) |
2007 |
29 | EE | Amir M. Ben-Amram,
Chin Soon Lee:
Program termination analysis in polynomial time.
ACM Trans. Program. Lang. Syst. 29(1): (2007) |
2006 |
28 | EE | Amir M. Ben-Amram,
Holger Petersen:
Backing up in singly linked lists.
J. ACM 53(4): 681-705 (2006) |
2005 |
27 | EE | Amir M. Ben-Amram:
The Church-Turing thesis and its look-alikes.
SIGACT News 36(3): 113-114 (2005) |
2004 |
26 | EE | Amir M. Ben-Amram:
A complexity-theoretic proof of a Recursion-Theoretic Theorem.
SIGACT News 35(2): 111-112 (2004) |
2003 |
25 | EE | Amir M. Ben-Amram,
Omer Berkman,
Holger Petersen:
Element distinctness on one-tape Turing machines: a complete solution.
Acta Inf. 40(2): 81-94 (2003) |
24 | EE | Amir M. Ben-Amram:
Tighter constant-factor time hierarchies.
Inf. Process. Lett. 87(1): 39-44 (2003) |
2002 |
23 | EE | Amir M. Ben-Amram:
General Size-Change Termination and Lexicographic Descent.
The Essence of Computation 2002: 3-17 |
22 | EE | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds for Dynamic Data Structures on Algebraic RAMs.
Algorithmica 32(3): 364-395 (2002) |
21 | EE | Amir M. Ben-Amram,
Holger Petersen:
Improved Bounds for Functions Related to Busy Beavers.
Theory Comput. Syst. 35(1): 1-11 (2002) |
2001 |
20 | EE | Chin Soon Lee,
Neil D. Jones,
Amir M. Ben-Amram:
The size-change principle for program termination.
POPL 2001: 81-92 |
19 | EE | Amir M. Ben-Amram,
Zvi Galil:
A Generalization of a Lower Bound Technique due to Fredman and Saks.
Algorithmica 30(1): 34-66 (2001) |
18 | EE | Amir M. Ben-Amram,
Zvi Galil:
Topological Lower Bounds on Algebraic Random Access Machines.
SIAM J. Comput. 31(3): 722-761 (2001) |
2000 |
17 | EE | Amir M. Ben-Amram,
Neil D. Jones:
Computational complexity via programming languages: constant factors do matter.
Acta Inf. 37(2): 83-120 (2000) |
1999 |
16 | EE | Stephen Alstrup,
Amir M. Ben-Amram,
Theis Rauhe:
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
STOC 1999: 499-506 |
15 | EE | Amir M. Ben-Amram,
Holger Petersen:
Backing Up in Singly Linked Lists.
STOC 1999: 780-786 |
14 | | Amir M. Ben-Amram,
Neil D. Jones:
A Precise Version of a Time Hierarchy Theorem.
Fundam. Inform. 38(1-2): 1-15 (1999) |
1998 |
13 | EE | Amir M. Ben-Amram,
Holger Petersen:
CONS-Free Programs with Tree Input (Extended Abstract).
ICALP 1998: 271-282 |
12 | | Amir M. Ben-Amram:
Introducing: Reasonable Complete Programming Languages.
Bulletin of the EATCS 64: (1998) |
1997 |
11 | | Amir M. Ben-Amram:
When Can We Sort in o(n log n) Time?
J. Comput. Syst. Sci. 54(2): 345-370 (1997) |
1996 |
10 | | Amir M. Ben-Amram,
Bryant A. Julstrom,
Uri Zwick:
A Note on Busy Beavers and Other Creatures.
Mathematical Systems Theory 29(4): 375-386 (1996) |
1995 |
9 | | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds on Algebraic Random Access Machines (Extended Abstract).
ICALP 1995: 360-371 |
8 | EE | Amir M. Ben-Amram,
Zvi Galil:
On Data Structure Tradeoffs and an Application to Union-Find
Electronic Colloquium on Computational Complexity (ECCC) 2(62): (1995) |
7 | | Amir M. Ben-Amram,
Zvi Galil:
On the Power of the Shift Instruction
Inf. Comput. 117(1): 19-36 (1995) |
1994 |
6 | | 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 |
5 | | Amir M. Ben-Amram:
Unit-Cost Pointers versus Logarithmic-Cost Addresses.
Theor. Comput. Sci. 132(2): 377-385 (1994) |
1993 |
4 | | Amir M. Ben-Amram,
Zvi Galil:
When can we sort in o(n log n) time?
FOCS 1993: 538-546 |
1992 |
3 | EE | Amir M. Ben-Amram,
Zvi Galil:
On Pointers versus Addresses.
J. ACM 39(3): 617-648 (1992) |
1991 |
2 | | Amir M. Ben-Amram,
Zvi Galil:
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
FOCS 1991: 622-631 |
1988 |
1 | | Amir M. Ben-Amram,
Zvi Galil:
On Pointers versus Addresses (Extended Abstract)
FOCS 1988: 532-538 |