next up previous
Next: Accepted Up: Publications: Previous: Theses

Journals

  1. S. Moran, General Approximation Algorithms for some Arithmetical Combinatorial Problems, Theoretical Computer Science 14 (1981), pp. 289-303. pdf file
  2. A. Paz and S. Moran, NP Optimization Problems and Their Approximation, Theoretical Computer Science 15 (1981), pp. 251-277. pdf file
  3. S. Moran and Y. Perl, The Complexity of Identifying Essential and Redundant Elements, Journal of Algorithms 2 (1981), pp. 22-30. pdf file
  4. S. Moran, Some Results on Relativized Deterministic and Nondeterministic Time Hierarchies, Journal of Computer and System Sciences 22:1 (1981), pp. 1-8. pdf file
  5. O. Ibarra, B. Leininger and S. Moran, On the Complexity of Simple Arithmetic Expressions, Theoretical Computer Science 19 (1982), pp. 17-28. pdf file
  6. O. Ibarra, S. Moran and L Rosier, A Note On the Parallel Complexity of Computing the Rank, Information Processing Letters 11:4 (1980), pp. 162.
  7. S. Moran, On the Accepting Density Hierarchy in NP, SIAM Journal of Computing 11:2 (1982), pp. 344-349.
  8. O. Ibarra and S. Moran, Probabilistic Algorithms for Deciding Equivalence of Straight Line Programs, Journal of the ACM 30:1 (1983), pp. 217-228. pdf file
  9. O. Ibarra and S. Moran, On some Decision Problems for RAM Programs, Journal of Computer and System Sciences 24:1 (1982), pp. 69-81.
  10. O. Ibarra, S. Moran and L. Rosier, Probabilistic Algorithms and Straight line Programs for Some Rank Decision Problems, Information Processing Letters 12:5 (1981), pp. 227-231.
  11. O. Ibarra, S. Moran and R. Hui, A Generalization of the Fast LUP Matrix Decomposition Algorithm and Applications, Journal of Algorithms 3 (1982), pp. 45-56. pdf file
  12. O. Ibarra and S. Moran, Deterministic and Probabilistic Algorithms for Maximum Bipartite Matching via Fast Matrix Multiplication, Information Processing Letters 13:1 (1981), pp. 12-15.
  13. O. Ibarra, S. Moran and L. Rosier, On the Control Power of Integer Division, Theoretical Computer Science 24:1 (1983), pp. 35-52.
  14. O. Ibarra and S. Moran, Some Time-Space Trade-Off Results Concerning Single Tape and Off-Line TM's, SIAM Journal of Computing 12:2 (1983), pp. 388-394.
  15. W. Franta, Y. Gold and S. Moran, An Efficient Distributed Channel Access Protocol for Packet-Radio Networks with Many Mobile Nodes, IEEE Transactions on Computers 32:2 (1983) pp. 133-146.
  16. S. Moran, A Note on ``Is Shortest Path Problem not Harder than Matrix Multiplication?'', Information Processing Letters 13:2 (1981), pp. 85-86.
  17. S. Porat, N. Fransez S. Moran and S. Zaks, Fair Derivations in Context Free Grammars, Information and Control Vol. 55:(1-3) (1982), pp. 108-116.
  18. S. Moran, On the Complexity of Designing Optimal Partial Match Retrieval Systems, pdf file ACM Transactions on Database Systems Vol. 8:4 (1983), pp. 543-551.
  19. S. Even, O. Goldreich, S. Moran and P. Tong, On the NP Completeness of some Network Testing Problems, Networks, Vol. 14 (1984), pp.1-24. pdf file
  20. R. Bar-Yehuda and S. Moran, On Approximation Problems related to the Independent Set and Vertex Cover Problems, Discrete Applied Mathematics Vol. 9:1 (1984), pp. 1-10.
  21. S. Moran, On the Length of Optimal TSP Circuits in Sets of Bounded Diameter, Journal of Combinatorial Theory, Series B Vol. 37:2 (1984), pp. 113-141. pdf file
  22. O. Ibarra, S. M. Kim and S. Moran, Sequential Machine Characterizations of Trellis and Cellular Automata and Applications, SIAM J. of Computing 14 (2), May 1985.
  23. O. Ibarra and S. Moran, Some Independence Results in Complexity Theory, International Journal of Computer Mathematics 17:2 (1985), pp. 113-122.
  24. S. Moran, M. Snir and U. Manber, Applications of Ramsey's Theorem to Decision Trees Complexity, Journal of the ACM 32:4 (1985), pp. 938-949. pdf file
  25. E. Korach, S. Moran and S. Zaks, The Optimality of Distributive Construction of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors, SIAM Journal of Computing 16:2 (1987), pp. 231-236.
  26. P. Erdos, N. Linial and S. Moran, Extremal Problems on Permutations under Cyclic Equivalence, Discrete Mathematics 64 (1987), pp. 1-11.
  27. S. Moran, Generalized Lower Bounds Derived From Hastad's Main Lemma, Information Processing Letters 25 (1987), pp. 383-388.
  28. A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. Wilber Geometric Applications of a Matrix-Searching Algorithm, Algorithmica 2 (1987) (special issue of selected papers from the $2 ^{nd}$ ACM symposium on Computational Geometry, 1986), pp. 195-208.
  29. S. Moran and Y. Wolfstahl, Extended Impossibility Results for Asynchronous Complete Networks, Information Processing Letters 26 (1987), pp. 145-151. pdf file
  30. Y. I. Gold and S. Moran, Distributed Algorithms for Constructing a Minimum-Weight Spanning Tree in a Broadcast Network, Distributed Computing 2 (1987), pp. 139-148.
  31. L. Babai and S. Moran, Arthur Merlin Games: a Randomized Proof System, and a Hierarchy of Complexity Classes, Journal of Computer and System Sciences 36 (1988) (special issue of selected papers from 17$^{th} $ ACM symposium on Theory of Computing, 1985), pp. 254-276. This paper won the Gödel Award on 1993. pdf file
  32. Y. Gold and S. Moran, Estimating Metrical Change in Fully Connected Mobile Networks - A Least Upper Bound on the Worst Case, IEEE Transactions on Computers 37:9 (1988) pp. 1156-1162.
  33. P. Erdos, I. Koren, S. Moran, G. Silberman and S. Zaks, Minimum Diameter Cyclic Arrangements in Mapping Data Flow Graphs onto VLSI Arrays, Mathematical Systems Theory 21 (1988), pp. 85-98
  34. B. Schieber and S. Moran, Parallel Algorithms for finding Maximum Bipartite Matchings and Maximum Flows in 0-1 Networks, Journal of Parallel and Distributed Computing 6 (1989), pp. 20-38.
  35. E. Korach, S. Moran and S. Zaks, Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors, Theoretical Computer Science 64 (1989) pp. 125-132.
  36. L. Babai and S. Moran, Proving Properties of Interactive Proofs by a Generalized Counting Technique, Information and Computation 82:2 (1989), pp. 185-197.
  37. S. Moran, Message Complexity Versus Space Complexity in Fault Tolerant Broadcast Protocols, Networks, Vol. 19 (1989), pp. 505-519. pdf file
  38. Y. Gold and S. Moran, A Correction Algorithm for Token Passing Sequences in Mobile Communication Networks, Algorithmica 4 (1989) (special issue on algorithmic aspects of communication), pp. 329-341.
  39. S. Moran, I. Newman and Y. Wolfstahl, Approximation Algorithms for Covering Graph by Vertex-disjoint Paths of Maximum Total Weight, Networks, Vol. 20 (1990), 55-64. pdf file
  40. E. Korach, S. Kutten and S. Moran, A Modular Technique For the Design of Efficient Leader Finding Algorithms, ACM Transactions on Programming Languages and Systems 12:1 (1990), pp. 84-101. Pdf file
  41. G. Taubenfeld, S. Katz and S. Moran, Initial failures in Distributed Computations, International Journal on Parallel Programming 18:4 (1989), pp. 255-275. pdf file
  42. O. Biran, S. Moran and S. Zaks, A Combinatorial Characterization of the Distributed 1-Solvable Tasks, Journal of Algorithm 11 (1990) (special issue of selected papers from 7$^{th} $ ACM symposium on Principles of Distributed Computing, 1988), pp. 420-440. pdf file from October 89
  43. S. Moran and Y. Wolfstahl, One-Page Book Embedding under Vertex-Neighborhood Constraints, SIAM J. Disc. Math. Vol. 3, No. 3, 1990, pp. 376-390.
  44. S. Moran and Y. Wolfstahl, Optimal Cover of Cacti by Vertex Disjoint Paths, Theoretical Computer Science 84 (1991), pp. 179-197.
  45. R. Bar Yehuda, T. Etzion and S. Moran, Rotating-Table Games and Derivatives of Words, Theoretical Computer Science 108 (1993), pp. 311-329. Pdf file
  46. S. Moran and M. Warmuth, Gap Theorems in Distributed Computing, SIAM Journal of Computing 22:2 (1993), pp. 379-394. postscript file
  47. M. Fischer, S. Moran and G. Taubenfeld, Space-Efficient Asynchronous Consensus Without Shared Memory Initialization, Information Processing Letters 45 (1993), pp. 101-105. postscript file
  48. S. Moran and Y. Wolfstahl, Two-Page Book Embedding of Trees under Vertex-Neighborhood Constraints, Discrete Applied Mathematics 43 (1993), pp. 233-241.
  49. Y. Malka, S. Moran and S. Zaks A Lower Bound on the Period Length of a Distributed Scheduler, Algorithmica 10 (1993), pp. 383-398.
  50. S. Dolev, A. Israeli and S. Moran, Self Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity, Distributed Computing 7:1 (1993), (special issue on self stabilizing systems) pp. 3-16. Pdf file
  51. H. Bodlaender, S. Moran and M. Warmuth, The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case, Information and Computation 108:1 (1994), pp. 34-50. postscript file
  52. G. Taubenfeld, S. Katz and S. Moran, Impossibility Results in the Presence of Multiple Faulty Processes, Information and Computation Vol. 114:2 (1994), pp. 173-198.
  53. Dolev, S., Israeli, A. and Moran, S., Analyzing Expected Time by Scheduler-Luck Games, IEEE Transactions on Software Engineering Vol. 21 no. 5 (1995), pp. 429-439. postscript file
  54. O. Biran, S. Moran and S. Zaks, Tight Bounds on the Round Complexity of Distributed 1-solvable Tasks, Theoretical Computer Science 145 (1995), pp. 271-290. pdf file
  55. R. Lubitch and S. Moran, Closed Schedulers: a Novel Technique for Analyzing Asynchronous Protocols, Distributed Computing, 8:4 (1995), pp. 203-210. pdf file
  56. H. Brit and S. Moran, Wait-freedom vs. Bounded Wait-freedom in Public Data Structures, Universal Journal of Computer Science, Vol. 2, no. 1 (1996), pp. 2-19. postscript file
  57. G. Taubenfeld and S. Moran, Possibility and Impossibility Results in a Shared Memory Environment, Acta Informatica, Vol. 33, (1996), pp. 1-20. pdf file, without a figure
  58. S. Moran, G. Taubenfeld and I. Yadin, Concurrent Counting, Journal of Computer and System Sciences 53:1 (1996), pp. 61-78. postscript file
  59. S. Dolev, A. Israeli, A and S. Moran, Resource Bounds for Self Stabilizing Message Driven Protocols, SIAM Journal of Computing 26:1 (1997), pp. 273-290. pdf file
  60. N. Allenberg-Navony, A. Itai, and S. Moran, Average and Randomized Complexity of Distributed Problems, SIAM Journal of Computing 25:6 (1996), pp. 1254-1267. pdf file
  61. M. J. Fischer, S. Moran, S. Rudich and G. Taubenfeld, The Wakeup Problem, SIAM Journal of Computing 25:6 (1996), pp. 1332-1357. postscript file
  62. S. Dolev, A. Israeli and S. Moran Uniform Dynamic Self-Stabilizing Leader Election, IEEE Transactions on Parallel and Distributed Systems, Vol. 8 No. 4, pp. 424-440, April 1997. Pdf file
  63. S. Moran and G. Taubenfeld, A Lower Bound on Wait-free Counting, Journal of Algorithms 24 (1997), pp. 1-19. postscript file
  64. T. Eilam, S. Moran and S. Zaks, A Lower Bound for Linear Interval Routing, Networks 34 (1999), pp. 37-46. postscript file
  65. S. Moran and S. Snir, Simple and Efficient Network Decomposition and Synchronization, Theoretical Computer Science 243(1-2), pp. 217-241, August 2000. pdf file
  66. Y. Dinitz, T. Eilam, S. Moran and S. Zaks, On the Total$_k$-Diameter of Connection Networks, Theoretical Computer Science vol. 247(1-2) pp. 213-228, September 2000. postscript file
  67. M. Alekhnovich, S. Buss, S. Moran and T. Pitassi, Minimal Propositional Proof Lengths is NP-hard to Linearly Approximate, Journal of Symbolic Logic 66(1), pp. 171-191, March 2001. postscript file

  68. R. Lempel and S. Moran, SALSA: The Stochastic Approach for Link-Structure Analysis, ACM Transactions on Information Systems 19(2), pp. 131-160, April 2001. postcript file
  69. T. Eilam, S. Moran and S. Zaks, Lightpath arrangements in Survivable Rings to Minimize the Switching Cost, IEEE Journal on Selected Areas in Communications, volume 20, Issue 1, Jan 2002, pp 172-182. pdf file

  70. H. Attiya, A. Gorbach and S. Moran, Computing in totally anonymous asynchronous shared memory systems, Information and Computation, No. 173, pp. 1-22, 2002. postscript file
  71. H. Brit, S. Moran and G. Taubenfeld, Public Data Structures: Counters as a Special Case, Theoretical Computer Science Vol. 289/1, , pp 401-423, November 2002. postscript file
  72. T. Eilam, S. Moran and S. Zaks, The Complexity of the Characterization of Networks Supporting Shortest-Path Interval Routing, Theoretical Computer Science, Volume 289/1, pp. 85-104, November 2002. postscript file
  73. Y. Dinitz, S. Moran and S. Rajsbaum, Exact communication costs for Consensus and Leader in a tree, Journal of Discrete Algorithms 1(2) pp. 167 - 183 (special edition of selected papers from the 7th International Colloquium on Structural Information and Communication Complexity) April 2003. postcript file
  74. R. Lempel and S. Moran, Optimizing Result Prefetching in Web Search Engines with Segmented Indices, ACM Transactions On Internet Technologies 4(1), pp. 31-59, February 2004. pdf file
  75. R. Lempel and S. Moran, Competitive Caching of Query Results in Search Engines, Theoretical Computer Science 324 (special issue on online algorithms), pp. 253-271, 2004. pdf file
  76. R. Lempel and S. Moran, Rank Stability and Rank Similarity of Link-Based Web Ranking Algorithms in Authority Connected Graphs, Information Retrieval 8 (special issue on advances in mathematics/formal methods in information retrieval), pp. 245-264, 2005. pdf file
  77. I. Gronau and S. moran, Neighbor Joining Algorithms for Inferring Phylogenies via LCA-Distances, Journal of Computational Biology 14(1) pp. 1-15 (2007). pdf file
  78. S. Moran and S. Snir, Efficient Approximation of Convex Recoloring, Journal of Computer and System Sciences 73:7, pp. 1078-1089, (2007). pdf file
  79. I. Gronau and S. moran, Optimal Implementations of UPGMA and Other Common Clustering Algorithms, Information Processing Letters 104:6, pp. 205-210 (December 2007). pdf file
  80. I. Gronau and S. moran, On The Hardness of Inferring Phylogenies from Triplet-Dissimilarities. Theoretical Computer Science 389(1-2), December 2007, pp. 44-55. pdf file
  81. Y. Dinitz, S. Moran and S. Rajsbaum, Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings, JACM 55(1), February 2008. pdf file
  82. S. Moran and S. Snir, Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms. JCSS 74, (special issue on computational biology) pp. 850-869 (2008). pdf file
  83. I. Gronau, S. Moran and I. Yavneh, Towards Optimal Distance Functions for Stochastic Substitution Models, Journal of Theoretical Biology 260 pp. 294-307 (2009). pdf file

  84. I. Gronau, S. Moran and I. Yavneh, Adaptive Distance Measures for Resolving K2P Quartets: Metric Separation versus Stochastic Noise, Journal of Computational Biology 17(11) pp. 1509-1518 (2010). pdf file

  85. I. Gronau, S. Moran and S. Snir, Fast and Reliable Reconstruction of Phylogenetic Trees with Indistinguishable Edges, Random Structures and Algorithms 40(3) pp. 350-384, May 2011. pdf file

  86. Shlomo Moran, Sagi Snir and Wing-Kin Sung, Partial Convex Recolorings of Trees and Galled Networks: Tight Upper and Lower bounds, ACM Transactions on Algorithms 7(4), September 2011. pdf file

  87. D. Doerr, I. Gronau, S. Moran and I. Yavneh, Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstruction, Algorithms in Molecular Biology 7:22, special issue of invited papers from WABI 2011, August 2012.

  88. B. Doerr, C. Doerr, S. Moran and S. Moran, Simple and Optimal Randomized Fault-Tolerant Rumor Spreading. Distributed Computing , 29(2), 89-104, April 2016. pdf file
  89. Y. Damti, I. Gronau, S. Moran and I. Yavneh, Comparing evolutionary distances via adaptive distance methods, Journal of Theoretical Biology 440, 88 - 99, 2018. pdf file
  90. B. Charron-Bost and S. Moran, The Firing Squad Problem Revisited, Theoretical Computer Science 793, 100 - 112 November 2019. pdf file

next up previous
Next: Accepted Up: Publications: Previous: Theses
Shlomo Moran 2020-07-23