# Shlomo Moran

According to our database

^{1}, Shlomo Moran## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2017

Synchronization in Dynamic Networks.

CoRR, 2017

2016

Simple and optimal randomized fault-tolerant rumor spreading.

Distributed Computing, 2016

2012

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 for Molecular Biology, 2012

2011

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

2010

Adaptive Distance Measures for Resolving K2P Quartets: Metric Separation versus Stochastic Noise.

Journal of Computational Biology, 2010

2008

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

2007

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.

Journal of Computational Biology, 2007

Optimal implementations of UPGMA and other common clustering algorithms.

Inf. Process. Lett., 2007

2005

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

Inf. Retr., 2005

Efficient Approximation of Convex Recolorings

CoRR, 2005

Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms.

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Using Semi-definite Programming to Enhance Supertree Resolvability.

Proceedings of the Algorithms in Bioinformatics, 5th International Workshop, 2005

Efficient Approximation of Convex Recolorings.

Proceedings of the Approximation, 2005

2004

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

2003

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

2002

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 Journal on Selected Areas in Communications, 2002

Computing in Totally Anonymous Asynchronous Shared Memory Systems.

Inf. Comput., 2002

Optimizing Result Prefetching in Web Search Engines with Segmented Indices.

Proceedings of the VLDB 2002, 2002

2001

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

2000

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.

Computer Networks, 2000

Approximation Algorithms for Survivable Optical Networks.

Proceedings of the Distributed Computing, 14th International Conference, 2000

Exact communication costs for consensus and leader in a tree.

Proceedings of the SIROCCO 7, 2000

1999

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

1998

Computing in Totally Anonymous Asynchronous Shared Memory Systems.

Proceedings of the Distributed Computing, 12th International Symposium, 1998

Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

Uniform Dynamic Self-Stabilizing Leader Election.

IEEE Trans. Parallel Distrib. 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

The Complexity of Characterization of Networks Supporting Shortest-Path Interval Routing.

Proceedings of the SIROCCO'97, 1997

On the total

_{k}-diameter of connection networks.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996

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. UCS, 1996

Concurrent Counting.

J. Comput. Syst. Sci., 1996

Possibility and Impossibility Results in a Shared Memory Environment.

Acta Inf., 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

1995

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 Computing, 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

1994

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

Average and Randomized Complexity of Distributed Problems.

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

1993

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 Computing, 1993

Two-Page Book Embedding of Trees under Vertex-Neighborhood Constraints.

Discrete Applied Mathematics, 1993

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

Algorithmica, 1993

A Lower Bound on Wait-Free Counting.

Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, 1993

1992

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

1991

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

Resource Bounds for Self Stabilizing Message Driven Protocols.

Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

1990

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. Discrete 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

Tight Bounds on the Round Complexity of Distributed 1-Solvable Tasks.

Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

The Wakeup Problem (Extended Abstract)

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Self-Stabilization of Dynamic Systems Assuming only Read/Write Atomicity.

Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990

One-page book embedding under vertex-neighborhood constraints.

Proceedings of the Next Decade in Information Technology: Proceedings of the 5th Jerusalem Conference on Information Technology 1990, 1990

1989

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 Distrib. Comput., 1989

Initial failures in distributed computations.

International Journal of Parallel Programming, 1989

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

Algorithmica, 1989

Possibility and Impossibility Results in a Shared Memory Environment.

Proceedings of the Distributed Algorithms, 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

The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case.

Proceedings of the Fundamentals of Computation Theory, 1989

1988

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.

Mathematical Systems 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

1987

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.

Discrete Mathematics, 1987

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

Distributed Computing, 1987

Geometric Applications of a Matrix-Searching Algorithm.

Algorithmica, 1987

1986

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

Gap Theorems for Distributed Computation.

Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

Geometric Applications of a Matrix Searching Algorithm.

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985

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

A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms.

Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

1984

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.

Discrete Applied Mathematics, 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

1983

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 SIGCOMM '83, 1983

1982

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

Information and Control, 1982

1981

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

On the Complexity of Simple Arithmetic Expressions.

Proceedings of the Automata, 1981

1980

A Note on the Parallel Complexity of Computing the Rank of Order n Matrices.

Inf. Process. Lett., 1980

1977

Non-Deterministic Polynomial Optimization Problems and Their Approximation.

Proceedings of the Automata, 1977