Shlomo Moran

  • Technion - Israel Institute of Technology, Haifa, Israel

According to our database1, Shlomo Moran authored at least 124 papers between 1977 and 2021.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:



Elementary Derivations of the Euclidean Hurwitz Algebras Adapted from Gadi Moran's last paper.
Am. Math. Mon., 2021

MinMax algorithms for stabilizing consensus.
Distributed Comput., 2021

Adjustable Coins.
CoRR, 2020

The firing squad problem revisited.
Theor. Comput. Sci., 2019

Synchronization in Dynamic Networks.
CoRR, 2017

Simple and optimal randomized fault-tolerant rumor spreading.
Distributed Comput., 2016

Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges.
Random Struct. Algorithms, 2012

Fast Fault Tolerant Rumor Spreading with Minimum Message Complexity
CoRR, 2012

Stochastic errors vs. modeling errors in distance based phylogenetic reconstructions.
Algorithms Mol. Biol., 2012

Partial convex recolorings of trees and galled networks: Tight upper and lower bounds.
ACM Trans. Algorithms, 2011

Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstructions - (Extended Abstract).
Proceedings of the Algorithms in Bioinformatics - 11th International Workshop, 2011

Adaptive Distance Measures for Resolving K2P Quartets: Metric Separation versus Stochastic Noise.
J. Comput. Biol., 2010

Convex recolorings of strings and trees: Definitions, hardness results and algorithms.
J. Comput. Syst. Sci., 2008

Bit complexity of breaking and achieving symmetry in chains and rings.
J. ACM, 2008

Fast and reliable reconstruction of phylogenetic trees with very short edges.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On the hardness of inferring phylogenies from triplet-dissimilarities.
Theor. Comput. Sci., 2007

Efficient approximation of convex recolorings.
J. Comput. Syst. Sci., 2007

Neighbor Joining Algorithms for Inferring Phylogenies via LCA Distances.
J. Comput. Biol., 2007

Optimal implementations of UPGMA and other common clustering algorithms.
Inf. Process. Lett., 2007

Rank-Stability and Rank-Similarity of Link-Based Web Ranking Algorithms in Authority-Connected Graphs.
Inf. Retr., 2005

Using Semi-definite Programming to Enhance Supertree Resolvability.
Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

Optimizing result prefetching in web search engines with segmented indices.
ACM Trans. Internet Techn., 2004

Competitive caching of query results in search engines.
Theor. Comput. Sci., 2004

Exact communication costs for consensus and leader in a tree.
J. Discrete Algorithms, 2003

Predictive caching and prefetching of query results in search engines.
Proceedings of the Twelfth International World Wide Web Conference, 2003

The complexity of the characterization of networks supporting shortest-path interval routing.
Theor. Comput. Sci., 2002

Public data structures: counters as a special case.
Theor. Comput. Sci., 2002

Lightpath arrangement in survivable rings to minimize the switching cost.
IEEE J. Sel. Areas Commun., 2002

Computing in Totally Anonymous Asynchronous Shared Memory Systems.
Inf. Comput., 2002

Introducing regulated bias into co-citation ranking schemes on the Web.
Proceedings of the Information, Connetcitons and Community, 2002

SALSA: the stochastic approach for link-structure analysis.
ACM Trans. Inf. Syst., 2001

Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log., 2001

Simple and efficient network decomposition and synchronization.
Theor. Comput. Sci., 2000

On the totalk-diameter of connection networks.
Theor. Comput. Sci., 2000

The stochastic approach for link-structure analysis (SALSA) and the TKC effect.
Comput. Networks, 2000

Approximation Algorithms for Survivable Optical Networks.
Proceedings of the Distributed Computing, 14th International Conference, 2000

Lower bounds for linear interval routing.
Networks, 1999

Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Uniform Dynamic Self-Stabilizing Leader Election.
IEEE Trans. Parallel Distributed Syst., 1997

Resource Bounds for Self-Stabilizing Message-Driven Protocols.
SIAM J. Comput., 1997

A Lower Bound on Wait-Free Counting.
J. Algorithms, 1997

A Simple DFS-Based Algorithm for Linear Interval Routing.
Proceedings of the Distributed Algorithms, 11th International Workshop, 1997

On the total<sub>k</sub>-diameter of connection networks.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

The Wakeup Problem.
SIAM J. Comput., 1996

Average and Randomized Complexity of Distributed Problems.
SIAM J. Comput., 1996

Wait-Freedom vs. Bounded-Freedom in Public Data Structures.
J. Univers. Comput. Sci., 1996

Concurrent Counting.
J. Comput. Syst. Sci., 1996

Possibility and Impossibility Results in a Shared Memory Environment.
Acta Informatica, 1996

On the Robustness of h^r_m.
Proceedings of the Distributed Algorithms, 10th International Workshop, 1996

A Lower Bound for Linear Interval Routing.
Proceedings of the Distributed Algorithms, 10th International Workshop, 1996

Analyzing Expected Time by Scheduler-Luck Games.
IEEE Trans. Software Eng., 1995

Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks.
Theor. Comput. Sci., 1995

Closed Schedulers: A Novel Technique for Analyzing Asynchronous Protocols.
Distributed Comput., 1995

Using Approximate Agreement to Obtain Complete Disagreement: The Output Structure of Input-Free Asynchronous Computations.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Public Data Structures: Counters as a Special Case (Abridged Version).
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Impossibility Results in the Presence of Multiple Faulty Processes
Inf. Comput., September, 1994

The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case
Inf. Comput., January, 1994

Exotic Behaviour of Consensus Numbers.
Proceedings of the Distributed Algorithms, 8th International Workshop, 1994

Wait-Freedom vs. Bounded Wait-Freedom in Public Data Structures (Extended Abstract).
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

Rotating-Table Games and Derivatives of Words.
Theor. Comput. Sci., 1993

Gap Theorems for Distributed Computation.
SIAM J. Comput., 1993

Space-Efficient Asynchronous Consensus Without Shared Memory Initialization.
Inf. Process. Lett., 1993

Self-Stabilization of Dynamic Systems Assuming Only Read/Write Atomicity.
Distributed Comput., 1993

Two-Page Book Embedding of Trees under Vertex-Neighborhood Constraints.
Discret. Appl. Math., 1993

A Lower Bound on the Period Length of a Distributed Scheduler.
Algorithmica, 1993

Closed Schedulers: Constructions and Applications to Consensus Protocols.
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Concurrent Counting (Extended Abstract).
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Optimal Covering of Cacti by Vertex-Disjoint Paths.
Theor. Comput. Sci., 1991

Uniform Dynamic Self-Stabilizing Leader Election (Extended Absrtact).
Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

On the Limitation of the Global Time Assumption in Distributed Systems (Extended Abstract).
Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms.
ACM Trans. Program. Lang. Syst., 1990

One-Page Book Embedding Under Vertex-Neighborhood Constraints.
SIAM J. Discret. Math., 1990

Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight.
Networks, 1990

A Combinatorial Characterization of the Distributed 1-Solvable Tasks.
J. Algorithms, 1990

Deciding 1-sovability of distributed task is NP-hard.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1990

The Wakeup Problem (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Proving Properties of Interactive Proofs by a Generalized Counting Technique
Inf. Comput., August, 1989

Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors.
Theor. Comput. Sci., 1989

Message complexity versus space complexity in fault tolerant broadcast protocols.
Networks, 1989

Parallel Algorithms for Maximum Bipartite Matchings and Maximum 0-1 Flows.
J. Parallel Distributed Comput., 1989

Initial failures in distributed computations.
Int. J. Parallel Program., 1989

A Correction Algorithm for Token-Passing Sequences in Mobile Communication Networks.
Algorithmica, 1989

Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version).
Proceedings of the Algorithms and Data Structures, 1989

Impossibility Results in the Presence of Multiple Faulty Processes (Preliminary Version).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

Estimating Metrical Change in Fully Connected Mobile Networks - A Least Upper Bound on the Worst Case.
IEEE Trans. Computers, 1988

Minimum-Diameter Cyclic Arrangements in Mapping Data-Flow Graphs onto VLSI Arrays.
Math. Syst. Theory, 1988

Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.
J. Comput. Syst. Sci., 1988

A Combinatorial Characterization of the Distributed Tasks Which Are Solvable in the Presence of One Faulty Processor.
Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Analysis of a Distributed Scheduler for Communication Networks.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors.
SIAM J. Comput., 1987

Extended Impossibility Results for Asynchronous Complete Networks.
Inf. Process. Lett., 1987

Generalized Lower Bounds Derived from Hastad's Main Lemma.
Inf. Process. Lett., 1987

Extremal problems on permutations under cyclic equivalence.
Discret. Math., 1987

Distributed Algorithms for Constructing a Minimum-Weight Spaning Tree in a Broadcast Network.
Distributed Comput., 1987

Geometric Applications of a Matrix-Searching Algorithm.
Algorithmica, 1987

Slowing Sequential Algorithms for Obtaining Fast Distributed and Parallel Algorithms: Maximum Matchings.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

Applications of Ramsey's Theorem to Decision Tree Complexity
J. ACM, October, 1985

Sequential Machine Characterizations of Trellis and Cellular Automata and Applications.
SIAM J. Comput., 1985

The Optimality of Distributed Constructions of Minimum Weigth and Degree Restricted Spanning Trees in a Complete Network of Processors.
Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

On the np-completeness of certain network testing problems.
Networks, 1984

On the length of optimal TSP circuits in sets of bounded diameter.
J. Comb. Theory, Ser. B, 1984

On approximation problems related to the independent set and vertex cover problems.
Discret. Appl. Math., 1984

Tight Lower and Upper Bounds for Some Distributed Algorithms for a Complete Network of Processors.
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
J. ACM, January, 1983

On the Complexity of Designing Optimal Partial-Match Retrieval Systems.
ACM Trans. Database Syst., 1983

On the Control Power of Integer Division.
Theor. Comput. Sci., 1983

A Distributed Channel-Access Protocol for Fully-Connected Networks with Mobile Nodes.
IEEE Trans. Computers, 1983

Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM's.
SIAM J. Comput., 1983

Dynamic selection of a performance-effective transmission sequence for token-passing networks with mobile nodes.
Proceedings of the Eighth Symposium on Data Communications, 1983

On the Complexity of Simple Arithmetic Expressions.
Theor. Comput. Sci., 1982

On the Accepting Density Hierarchy in NP.
SIAM J. Comput., 1982

On Some Decision Problems for RAM Programs.
J. Comput. Syst. Sci., 1982

A Generalization of the Fast LUP Matrix Decomposition Algorithm and Applications.
J. Algorithms, 1982

Fair Deriviations in Context-Free Grammars
Inf. Control., 1982

Non Deterministic Polynomial Optimization Problems and their Approximations.
Theor. Comput. Sci., 1981

General Approximation Algorithms for some Arithmetical Combinatorial Problems.
Theor. Comput. Sci., 1981

Some Results on Relativized Deterministic and Nondeterministic Time Hierarchies.
J. Comput. Syst. Sci., 1981

The Complexity of Identifying Redundant and Essential Elements.
J. Algorithms, 1981

A Note on 'Is Shortest Path Problem not Harder Than Matrix Multiplication?'.
Inf. Process. Lett., 1981

Probabilistic Algorithms and Straight-Line Programs for Some Rank Decision Problems.
Inf. Process. Lett., 1981

Deterministic and Probabilistic Algorithms for Maximum Bipartite Matching Via Fast Matrix Multiplication.
Inf. Process. Lett., 1981

A Note on the Parallel Complexity of Computing the Rank of Order n Matrices.
Inf. Process. Lett., 1980

Non-Deterministic Polynomial Optimization Problems and Their Approximation.
Proceedings of the Automata, 1977