Shlomo Moran

IACR Cryptol. ePrint Arch., 2022

Brief Announcement: Self Masking for Hardening Inversions.

[BibT_eX]

[DOI]

Pawel Cyprys

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2022

2021

Elementary Derivations of the Euclidean Hurwitz Algebras Adapted from Gadi Moran's last paper.

[BibT_eX]

[DOI]

Tomer Moran

Shay Moran

Am. Math. Mon., 2021

MinMax algorithms for stabilizing consensus.

[BibT_eX]

[DOI]

Bernadette Charron-Bost

Distributed Comput., 2021

2020

Adjustable Coins.

[BibT_eX]

[DOI]

Irad Yavneh

CoRR, 2020

2019

The firing squad problem revisited.

[BibT_eX]

[DOI]

Bernadette Charron-Bost

Theor. Comput. Sci., 2019

2017

Synchronization in Dynamic Networks.

[BibT_eX]

[DOI]

Bernadette Charron-Bost

CoRR, 2017

2016

Simple and optimal randomized fault-tolerant rumor spreading.

[BibT_eX]

[DOI]

Distributed Comput., 2016

2012

Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2012

Fast Fault Tolerant Rumor Spreading with Minimum Message Complexity

[BibT_eX]

[DOI]

CoRR, 2012

Stochastic errors vs. modeling errors in distance based phylogenetic reconstructions.

[BibT_eX]

[DOI]

Algorithms Mol. Biol., 2012

2011

Partial convex recolorings of trees and galled networks: Tight upper and lower bounds.

[BibT_eX]

[DOI]

Wing-Kin Sung

ACM Trans. Algorithms, 2011

Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstructions - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics - 11th International Workshop, 2011

2010

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

[BibT_eX]

[DOI]

Irad Yavneh

J. Comput. Biol., 2010

2008

Convex recolorings of strings and trees: Definitions, hardness results and algorithms.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Bit complexity of breaking and achieving symmetry in chains and rings.

[BibT_eX]

[DOI]

Yefim Dinitz

Sergio Rajsbaum

J. ACM, 2008

Fast and reliable reconstruction of phylogenetic trees with very short edges.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

On the hardness of inferring phylogenies from triplet-dissimilarities.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Efficient approximation of convex recolorings.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

Neighbor Joining Algorithms for Inferring Phylogenies via LCA Distances.

[BibT_eX]

[DOI]

J. Comput. Biol., 2007

Optimal implementations of UPGMA and other common clustering algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

2005

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

[BibT_eX]

[DOI]

Inf. Retr., 2005

Using Semi-definite Programming to Enhance Supertree Resolvability.

[BibT_eX]

[DOI]

Satish Rao

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

2004

Optimizing result prefetching in web search engines with segmented indices.

[BibT_eX]

[DOI]

ACM Trans. Internet Techn., 2004

Competitive caching of query results in search engines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

2003

Exact communication costs for consensus and leader in a tree.

[BibT_eX]

[DOI]

Yefim Dinitz

Sergio Rajsbaum

J. Discrete Algorithms, 2003

Predictive caching and prefetching of query results in search engines.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International World Wide Web Conference, 2003

2002

The complexity of the characterization of networks supporting shortest-path interval routing.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Public data structures: counters as a special case.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Lightpath arrangement in survivable rings to minimize the switching cost.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2002

Computing in Totally Anonymous Asynchronous Shared Memory Systems.

[BibT_eX]

[DOI]

Hagit Attiya

Alla Gorbach

Inf. Comput., 2002

Introducing regulated bias into co-citation ranking schemes on the Web.

[BibT_eX]

[DOI]

Proceedings of the Information, Connetcitons and Community, 2002

2001

SALSA: the stochastic approach for link-structure analysis.

[BibT_eX]

[DOI]

ACM Trans. Inf. Syst., 2001

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

[BibT_eX]

[DOI]

J. Symb. Log., 2001

2000

Simple and efficient network decomposition and synchronization.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

On the totalk-diameter of connection networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

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

[BibT_eX]

[DOI]

Comput. Networks, 2000

Approximation Algorithms for Survivable Optical Networks.

[BibT_eX]

[DOI]

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

1999

Lower bounds for linear interval routing.

[BibT_eX]

[DOI]

Networks, 1999

Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract).

[BibT_eX]

[DOI]

Yefim Dinitz

Sergio Rajsbaum

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1997

Uniform Dynamic Self-Stabilizing Leader Election.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 1997

Resource Bounds for Self-Stabilizing Message-Driven Protocols.

[BibT_eX]

[DOI]

SIAM J. Comput., 1997

A Lower Bound on Wait-Free Counting.

[BibT_eX]

[DOI]

J. Algorithms, 1997

A Simple DFS-Based Algorithm for Linear Interval Routing.

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 11th International Workshop, 1997

On the total<sub>k</sub>-diameter of connection networks.

[BibT_eX]

[DOI]

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996

The Wakeup Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Average and Randomized Complexity of Distributed Problems.

[BibT_eX]

[DOI]

Nechama Allenberg-Navony

Alon Itai

SIAM J. Comput., 1996

Wait-Freedom vs. Bounded-Freedom in Public Data Structures.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 1996

Concurrent Counting.

[BibT_eX]

[DOI]

Irit Yadin

J. Comput. Syst. Sci., 1996

Possibility and Impossibility Results in a Shared Memory Environment.

[BibT_eX]

[DOI]

Acta Informatica, 1996

On the Robustness of h^r_m.

[BibT_eX]

[DOI]

Lihu Rappoport

Proceedings of the Distributed Algorithms, 10th International Workshop, 1996

A Lower Bound for Linear Interval Routing.

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 10th International Workshop, 1996

1995

Analyzing Expected Time by Scheduler-Luck Games.

[BibT_eX]

[DOI]

IEEE Trans. Software Eng., 1995

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Closed Schedulers: A Novel Technique for Analyzing Asynchronous Protocols.

[BibT_eX]

[DOI]

Ronit Lubitch

Distributed Comput., 1995

Using Approximate Agreement to Obtain Complete Disagreement: The Output Structure of Input-Free Asynchronous Computations.

[BibT_eX]

[DOI]

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Public Data Structures: Counters as a Special Case (Abridged Version).

[BibT_eX]

[DOI]

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994

Impossibility Results in the Presence of Multiple Faulty Processes

[BibT_eX]

[DOI]

Shmuel Katz

Inf. Comput., September, 1994

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

[BibT_eX]

[DOI]

Hans L. Bodlaender

Manfred K. Warmuth

Inf. Comput., January, 1994

Exotic Behaviour of Consensus Numbers.

[BibT_eX]

[DOI]

Robert Cori

Proceedings of the Distributed Algorithms, 8th International Workshop, 1994

Wait-Freedom vs. Bounded Wait-Freedom in Public Data Structures (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

1993

Rotating-Table Games and Derivatives of Words.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Tuvi Etzion

Theor. Comput. Sci., 1993

Gap Theorems for Distributed Computation.

[BibT_eX]

[DOI]

Manfred K. Warmuth

SIAM J. Comput., 1993

Space-Efficient Asynchronous Consensus Without Shared Memory Initialization.

[BibT_eX]

[DOI]

Michael J. Fischer

Inf. Process. Lett., 1993

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

[BibT_eX]

[DOI]

Distributed Comput., 1993

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

[BibT_eX]

[DOI]

Yaron Wolfsthal

Discret. Appl. Math., 1993

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

[BibT_eX]

[DOI]

Yossi Malka

Algorithmica, 1993

1992

Closed Schedulers: Constructions and Applications to Consensus Protocols.

[BibT_eX]

[DOI]

Ronit Lubitch

Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Concurrent Counting (Extended Abstract).

[BibT_eX]

[DOI]

Irit Yadin

Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

1991

Optimal Covering of Cacti by Vertex-Disjoint Paths.

[BibT_eX]

[DOI]

Yaron Wolfsthal

Theor. Comput. Sci., 1991

Uniform Dynamic Self-Stabilizing Leader Election (Extended Absrtact).

[BibT_eX]

[DOI]

Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

On the Limitation of the Global Time Assumption in Distributed Systems (Extended Abstract).

[BibT_eX]

[DOI]

Uri Abraham

Shai Ben-David

Proceedings of the Distributed Algorithms, 5th International Workshop, 1991

1990

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

[BibT_eX]

[DOI]

Shay Kutten

ACM Trans. Program. Lang. Syst., 1990

One-Page Book Embedding Under Vertex-Neighborhood Constraints.

[BibT_eX]

[DOI]

Yaron Wolfstahl

SIAM J. Discret. Math., 1990

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

[BibT_eX]

[DOI]

Ilan Newman

Yaron Wolfstahl

Networks, 1990

A Combinatorial Characterization of the Distributed 1-Solvable Tasks.

[BibT_eX]

[DOI]

J. Algorithms, 1990

Deciding 1-sovability of distributed task is NP-hard.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1990

The Wakeup Problem (Extended Abstract)

[BibT_eX]

[DOI]

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

1989

Proving Properties of Interactive Proofs by a Generalized Counting Technique

[BibT_eX]

[DOI]

László Babai

Inf. Comput., August, 1989

Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Message complexity versus space complexity in fault tolerant broadcast protocols.

[BibT_eX]

[DOI]

Networks, 1989

Parallel Algorithms for Maximum Bipartite Matchings and Maximum 0-1 Flows.

[BibT_eX]

[DOI]

Baruch Schieber

J. Parallel Distributed Comput., 1989

Initial failures in distributed computations.

[BibT_eX]

[DOI]

Shmuel Katz

Int. J. Parallel Program., 1989

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

[BibT_eX]

[DOI]

Algorithmica, 1989

Computing the Minimum Visible Vertex Distance between Two Polygons (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 1989

Impossibility Results in the Presence of Multiple Faulty Processes (Preliminary Version).

[BibT_eX]

[DOI]

Shmuel Katz

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1989

1988

Estimating Metrical Change in Fully Connected Mobile Networks - A Least Upper Bound on the Worst Case.

[BibT_eX]

[DOI]

IEEE Trans. Computers, 1988

Minimum-Diameter Cyclic Arrangements in Mapping Data-Flow Graphs onto VLSI Arrays.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1988

Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes.

[BibT_eX]

[DOI]

László Babai

J. Comput. Syst. Sci., 1988

A Combinatorial Characterization of the Distributed Tasks Which Are Solvable in the Presence of One Faulty Processor.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988

Analysis of a Distributed Scheduler for Communication Networks.

[BibT_eX]

[DOI]

Yossi Malka

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.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

Extended Impossibility Results for Asynchronous Complete Networks.

[BibT_eX]

[DOI]

Yaron Wolfstahl

Inf. Process. Lett., 1987

Generalized Lower Bounds Derived from Hastad's Main Lemma.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1987

Extremal problems on permutations under cyclic equivalence.

[BibT_eX]

[DOI]

Paul Erdös

Nathan Linial

Discret. Math., 1987

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

[BibT_eX]

[DOI]

Distributed Comput., 1987

Geometric Applications of a Matrix-Searching Algorithm.

[BibT_eX]

[DOI]

Algorithmica, 1987

1986

Slowing Sequential Algorithms for Obtaining Fast Distributed and Parallel Algorithms: Maximum Matchings.

[BibT_eX]

[DOI]

Baruch Schieber

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

1985

Applications of Ramsey's Theorem to Decision Tree Complexity

[BibT_eX]

[DOI]

Marc Snir

Udi Manber

J. ACM, October, 1985

Sequential Machine Characterizations of Trellis and Cellular Automata and Applications.

[BibT_eX]

[DOI]

Sam M. Kim

SIAM J. Comput., 1985

The Optimality of Distributed Constructions of Minimum Weigth and Degree Restricted Spanning Trees in a Complete Network of Processors.

[BibT_eX]

[DOI]

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

1984

On the np-completeness of certain network testing problems.

[BibT_eX]

[DOI]

Networks, 1984

On the length of optimal TSP circuits in sets of bounded diameter.

[BibT_eX]

[DOI]

J. Comb. Theory B, 1984

On approximation problems related to the independent set and vertex cover problems.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

Discret. Appl. Math., 1984

Tight Lower and Upper Bounds for Some Distributed Algorithms for a Complete Network of Processors.

[BibT_eX]

[DOI]

Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version)

[BibT_eX]

[DOI]

Marc Snir

Udi Manber

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

[BibT_eX]

[DOI]

J. ACM, January, 1983

On the Complexity of Designing Optimal Partial-Match Retrieval Systems.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 1983

On the Control Power of Integer Division.

[BibT_eX]

[DOI]

Louis E. Rosier

Theor. Comput. Sci., 1983

A Distributed Channel-Access Protocol for Fully-Connected Networks with Mobile Nodes.

[BibT_eX]

[DOI]

William R. Franta

IEEE Trans. Computers, 1983

Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM's.

[BibT_eX]

[DOI]

SIAM J. Comput., 1983

Dynamic selection of a performance-effective transmission sequence for token-passing networks with mobile nodes.

[BibT_eX]

[DOI]

Proceedings of the Eighth Symposium on Data Communications, 1983

1982

On the Complexity of Simple Arithmetic Expressions.

[BibT_eX]

[DOI]

Brian S. Leininger

Theor. Comput. Sci., 1982

On the Accepting Density Hierarchy in NP.

[BibT_eX]

[DOI]

SIAM J. Comput., 1982

On Some Decision Problems for RAM Programs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1982

A Generalization of the Fast LUP Matrix Decomposition Algorithm and Applications.

[BibT_eX]

[DOI]

Roger Hui

J. Algorithms, 1982

Fair Deriviations in Context-Free Grammars

[BibT_eX]

[DOI]

Inf. Control., 1982

1981

Non Deterministic Polynomial Optimization Problems and their Approximations.

[BibT_eX]

[DOI]

Azaria Paz

Theor. Comput. Sci., 1981

General Approximation Algorithms for some Arithmetical Combinatorial Problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1981

Some Results on Relativized Deterministic and Nondeterministic Time Hierarchies.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1981

The Complexity of Identifying Redundant and Essential Elements.

[BibT_eX]

[DOI]

Yehoshua Perl

J. Algorithms, 1981

A Note on 'Is Shortest Path Problem not Harder Than Matrix Multiplication?'.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

Probabilistic Algorithms and Straight-Line Programs for Some Rank Decision Problems.

[BibT_eX]

[DOI]

Louis E. Rosier

Inf. Process. Lett., 1981

Deterministic and Probabilistic Algorithms for Maximum Bipartite Matching Via Fast Matrix Multiplication.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1981

1980

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

[BibT_eX]

[DOI]

Louis E. Rosier

Inf. Process. Lett., 1980

1977

Non-Deterministic Polynomial Optimization Problems and Their Approximation.

[BibT_eX]

[DOI]

Azaria Paz