Shlomo Moran
According to our database^{1}, Shlomo Moran
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at id.loc.gov

at dl.acm.org
On csauthors.net:
Bibliography
2018
The Firing Squad Problem Revisited.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018
2017
Synchronization in Dynamic Networks.
CoRR, 2017
2016
Simple and optimal randomized faulttolerant 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 ACMSIAM Symposium on Discrete Algorithms, 2008
2007
On the hardness of inferring phylogenies from tripletdissimilarities.
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
RankStability and RankSimilarity of LinkBased Web Ranking Algorithms in AuthorityConnected 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 Semidefinite 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 shortestpath 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 linkstructure analysis.
ACM Trans. Inf. Syst., 2001
Minimum Propositional Proof Length Is NPHard to Linearly Approximate.
J. Symb. Log., 2001
2000
Simple and efficient network decomposition and synchronization.
Theor. Comput. Sci., 2000
On the totalkdiameter of connection networks.
Theor. Comput. Sci., 2000
The stochastic approach for linkstructure 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 ThirtyFirst 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 NPHard to Linearly Approximate.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998
1997
Uniform Dynamic SelfStabilizing Leader Election.
IEEE Trans. Parallel Distrib. Syst., 1997
Resource Bounds for SelfStabilizing MessageDriven Protocols.
SIAM J. Comput., 1997
A Lower Bound on WaitFree Counting.
J. Algorithms, 1997
A Simple DFSBased Algorithm for Linear Interval Routing.
Proceedings of the Distributed Algorithms, 11th International Workshop, 1997
The Complexity of Characterization of Networks Supporting ShortestPath 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
WaitFreedom vs. BoundedFreedom 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 SchedulerLuck Games.
IEEE Trans. Software Eng., 1995
Tight Bounds on the Round Complexity of Distributed 1Solvable 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 InputFree 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 Nonanonymous 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
WaitFreedom vs. Bounded WaitFreedom in Public Data Structures (Extended Abstract).
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994
1993
RotatingTable Games and Derivatives of Words.
Theor. Comput. Sci., 1993
Gap Theorems for Distributed Computation.
SIAM J. Comput., 1993
SpaceEfficient Asynchronous Consensus Without Shared Memory Initialization.
Inf. Process. Lett., 1993
SelfStabilization of Dynamic Systems Assuming Only Read/Write Atomicity.
Distributed Computing, 1993
TwoPage Book Embedding of Trees under VertexNeighborhood Constraints.
Discrete Applied Mathematics, 1993
A Lower Bound on the Period Length of a Distributed Scheduler.
Algorithmica, 1993
A Lower Bound on WaitFree 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 VertexDisjoint Paths.
Theor. Comput. Sci., 1991
Uniform Dynamic SelfStabilizing 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
OnePage Book Embedding Under VertexNeighborhood Constraints.
SIAM J. Discrete Math., 1990
Approximation algorithms for covering a graph by vertexdisjoint paths of maximum total weight.
Networks, 1990
A Combinatorial Characterization of the Distributed 1Solvable Tasks.
J. Algorithms, 1990
Deciding 1sovability of distributed task is NPhard.
Proceedings of the GraphTheoretic Concepts in Computer Science, 1990
Tight Bounds on the Round Complexity of Distributed 1Solvable 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
SelfStabilization of Dynamic Systems Assuming only Read/Write Atomicity.
Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990
Onepage book embedding under vertexneighborhood 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 01 Flows.
J. Parallel Distrib. Comput., 1989
Initial failures in distributed computations.
International Journal of Parallel Programming, 1989
A Correction Algorithm for TokenPassing 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 Nonanonymous 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
MinimumDiameter Cyclic Arrangements in Mapping DataFlow Graphs onto VLSI Arrays.
Mathematical Systems Theory, 1988
ArthurMerlin 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 MinimumWeight Spaning Tree in a Broadcast Network.
Distributed Computing, 1987
Geometric Applications of a MatrixSearching 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 npcompleteness 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 StraightLine Programs
J. ACM, January, 1983
On the Complexity of Designing Optimal PartialMatch Retrieval Systems.
ACM Trans. Database Syst., 1983
On the Control Power of Integer Division.
Theor. Comput. Sci., 1983
A Distributed ChannelAccess Protocol for FullyConnected Networks with Mobile Nodes.
IEEE Trans. Computers, 1983
Some TimeSpace Tradeoff Results Concerning SingleTape and Offline TM's.
SIAM J. Comput., 1983
Dynamic selection of a performanceeffective transmission sequence for tokenpassing 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 ContextFree 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 StraightLine 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
NonDeterministic Polynomial Optimization Problems and Their Approximation.
Proceedings of the Automata, 1977