David Peleg

According to our database1, David Peleg authored at least 313 papers between 1983 and 2019.

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

Awards

ACM Fellow

ACM Fellow 2016, "For contributions to distributed computing and graph algorithms".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Distributed distance computation and routing with small messages.
Distributed Computing, 2019

Graph Profile Realizations and Applications to Social Networks.
Proceedings of the WALCOM: Algorithms and Computation - 13th International Conference, 2019

Majority vote and monopolies in social networks.
Proceedings of the 20th International Conference on Distributed Computing and Networking, 2019

2018
The topology of wireless communication on a line.
Theor. Comput. Sci., 2018

EATCS Distinguished Dissertation Award 2018 - Call for Nominations.
Bulletin of the EATCS, 2018

Preferential Attachment as a Unique Equilibrium.
Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

Wireless Expanders.
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Mixed Fault Tolerance in Server Assignment: Combining Reinforcement and Backup.
Proceedings of the Structural Information and Communication Complexity, 2018

Realizability of Graph Specifications: Characterizations and Algorithms.
Proceedings of the Structural Information and Communication Complexity, 2018

2017
Improved Degree Bounds and Full Spectrum Power Laws in Preferential Attachment Networks.
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13, 2017

Maintaining Communication in Multi-Robot Tree Coverage.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

Assortative Mixing Equilibria in Social Network Games.
Proceedings of the Game Theory for Networks - 7th International EAI Conference, 2017

The Effect of Population Control Policies on Societal Fragmentation.
Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, Sydney, Australia, July 31, 2017

2016
Sparse Fault-Tolerant BFS Structures.
ACM Trans. Algorithms, 2016

On social networks of program committees - Structure and effect on paper acceptance fairness.
Social Netw. Analys. Mining, 2016

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Local-on-Average Distributed Tasks.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Message Lower Bounds via Efficient Network Synchronization.
Proceedings of the Structural Information and Communication Complexity, 2016

2015
Fault tolerant additive and (μ, α)-spanners.
Theor. Comput. Sci., 2015

40th international colloquium on automata, languages and programming.
Inf. Comput., 2015

Truth tellers and liars with fewer questions.
Discrete Mathematics, 2015

Nonuniform SINR+Voroni Diagrams Are Effectively Uniform.
Proceedings of the Distributed Computing - 29th International Symposium, 2015

Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Nearly Optimal Local Broadcasting in the SINR Model with Feedback.
Proceedings of the Structural Information and Communication Complexity, 2015

Homophily and the Glass Ceiling Effect in Social Networks.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Core Size and Densification in Preferential Attachment Networks.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Improved Approximation Algorithms for Weighted 2-Path Partitions.
Proceedings of the Algorithms - ESA 2015, 2015

Social Network Analysis of Program Committees and Paper Acceptance Fairness.
Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015

On the Relations Between SINR Diagrams and Voronoi Diagrams.
Proceedings of the Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, 2015

2014
Testing the irreducibility of nonsquare Perron-Frobenius systems.
Inf. Process. Lett., 2014

Randomized distributed decision.
Distributed Computing, 2014

Distributed 3/2-Approximation of the Diameter.
Proceedings of the Distributed Computing - 28th International Symposium, 2014

Fault Tolerant Approximate BFS Structures.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Distributed Computing on Core-Periphery Networks: Axiom-Based Design.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

How Even Tiny Influence Can Have a Big Impact!
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

Immunity against Local Influence.
Proceedings of the Language, Culture, Computation. Computing - Theory and Technology, 2014

2013
Prize for innovation in distributed computing: awarded to Roger Wattenhofer.
SIGACT News, 2013

Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification.
Theory Comput. Syst., 2013

Towards a complexity theory for local distributed computing.
J. ACM, 2013

Special issue on DISC 2011.
Distributed Computing, 2013

Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Efficient distributed source detection with limited bandwidth.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

On the complexity of universal leader election.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

Sublinear Bounds for Randomized Leader Election.
Proceedings of the Distributed Computing and Networking, 14th International Conference, 2013

Randomized Distributed Decision (Invited Lecture Abstract).
Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

Sparse Fault-Tolerant BFS Trees.
Proceedings of the Algorithms - ESA 2013, 2013

Secluded Connectivity Problems.
Proceedings of the Algorithms - ESA 2013, 2013

2012
SINR Diagrams: Convexity and Its Applications in Wireless Networks.
J. ACM, 2012

On the approximability of some degree-constrained subgraph problems.
Discrete Applied Mathematics, 2012

f-Sensitivity Distance Oracles and Routing Schemes.
Algorithmica, 2012

Constructing Resilient Structures in Graphs: Rigid vs. Competitive Fault-Tolerance.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Fault Tolerant Additive Spanners.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Randomized Distributed Decision.
Proceedings of the Distributed Computing - 26th International Symposium, 2012

Discovery through gossip.
Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Gathering despite mischief.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

SINR diagram with interference cancellation.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Notions of Connectivity in Overlay Networks.
Proceedings of the Structural Information and Communication Complexity, 2012

The Fault Tolerant Capacitated k-Center Problem.
Proceedings of the Structural Information and Communication Complexity, 2012

Multipath Spanners via Fault-Tolerant Spanners.
Proceedings of the Design and Analysis of Algorithms, 2012

Distributed Algorithms for Network Diameter and Girth.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
A note on exact distance labeling.
Inf. Process. Lett., 2011

Distributed verification and hardness of distributed approximation.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The topology of wireless communication.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Tight Bounds For Distributed MST Verification.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

On Approximating the d-Girth of a Graph.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

SINR Maps: Properties and Applications.
Proceedings of the Structural Information and Communication Complexity, 2011

Distributed power control in the SINR model.
Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

Local Distributed Decision.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Structure and algorithms in the SINR wireless model.
SIGACT News, 2010

Realtime Classification for Encrypted Traffic.
Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

Relaxed Spanners for Directed Disk Graphs.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Robust Fault Tolerant Uncapacitated Facility Location.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Forbidden-set distance labels for graphs of bounded doubling dimension.
Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Sparse Reliable Graph Backbones.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

f-Sensitivity Distance Oracles and Routing Schemes.
Proceedings of the Algorithms, 2010

Time-Efficient Broadcast in Radio Networks.
Proceedings of the Graphs and Algorithms in Communication Networks: Studies in Broadband, 2010

2009
Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems.
J. Discrete Algorithms, 2009

Conflict-free coloring of unit disks.
Discrete Applied Mathematics, 2009

Computing the fault tolerance of multi-agent deployment.
Artif. Intell., 2009

Low-Port Tree Representations.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Efficient k-Shot Broadcasting in Radio Networks.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Local Computation of Nearly Additive Spanners.
Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Fault-tolerant spanners for general graphs.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

As Good as It Gets: Competitive Fault Tolerance in Network Structures.
Proceedings of the Stabilization, 2009

SINR diagrams: towards algorithmically usable SINR models of wireless networks.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2008
Local spreading algorithms for autonomous robot systems.
Theor. Comput. Sci., 2008

Dynamic routing schemes for graphs with low local density.
ACM Trans. Algorithms, 2008

Time efficient k-shot broadcasting in known topology radio networks.
Distributed Computing, 2008

Degree-Constrained Subgraph Problems: Hardness and Approximation Results.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

A near-linear time algorithm for computing replacement paths in planar directed graphs.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Equal-Area Locus-Based Convex Polygon Decomposition.
Proceedings of the Structural Information and Communication Complexity, 2008

On the effect of the deployment setting on broadcasting in Euclidean radio networks.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

On the locality of distributed sparse spanner construction.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

Towards Networked Computers: What Can Be Learned from Distributed Computing?.
Proceedings of the High Performance Computing, 2008

Localized Spanner Construction for Ad Hoc Networks with Variable Transmission Range.
Proceedings of the Ad-hoc, Mobile and Wireless Networks, 7th International Conference, 2008

2007
Reducing human interactions in Web directory searches.
ACM Trans. Inf. Syst., 2007

Preface.
Theor. Comput. Sci., 2007

Average stretch analysis of compact routing schemes.
Discrete Applied Mathematics, 2007

Time-Efficient Broadcasting in Radio Networks.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Energy and Time Efficient Broadcasting in Known Topology Radio Networks.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time.
Proceedings of the Distributed Computing, 21st International Symposium, 2007

Distributed Models and Algorithms for Mobile Robot Systems.
Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

Distributed Algorithms for Partitioning a Swarm of Autonomous Mobile Robots.
Proceedings of the Structural Information and Communication Complexity, 2007

Broadcasting in udg radio networks with unknown topology.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Time-Efficient Broadcasting in Radio Networks: A Review.
Proceedings of the Distributed Computing and Internet Technology, 2007

2006
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements.
Proceedings of the STACS 2006, 2006

A tight upper bound on the probabilistic embedding of series-parallel graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Local Algorithms for Autonomous Robot Systems.
Proceedings of the Structural Information and Communication Complexity, 2006

Constructing Labeling Schemes Through Universal Matrices.
Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

Dynamic Routing Schemes for General Graphs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Approximate Hierarchical Facility Location and Applications to the Shallow Steiner Tree and Range Assignment Problems.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks.
Proceedings of the Combinatorial and Algorithmic Aspects of Networking, Third Workshop, 2006

2005
Preface: Structural Information and Communication Complexity.
Theor. Comput. Sci., 2005

Approximating k-spanner problems for kge2.
Theor. Comput. Sci., 2005

Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds.
SIAM J. Comput., 2005

Virtual path layouts optimizing total hop count on ATM tree networks.
J. Discrete Algorithms, 2005

Broadcasting with locally bounded Byzantine faults.
Inf. Process. Lett., 2005

Polynomial time approximation schemes for base station coverage with minimum total radii.
Computer Networks, 2005

Energy-Optimal Online Algorithms for Broadcasting in Wireless Networks.
Proceedings of the 2nd International Conference on Wireless on Demand Network Systems and Service (WONS 2005), 2005

Improved recommendation systems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Feasibility and complexity of broadcasting with random transmission failures.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Proof labeling schemes.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Faster communication in known topology radio networks.
Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Distributed Algorithms for Systems of Autonomous Mobile Robots.
Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges.
Proceedings of the Distributed Computing, 2005

Labeling Schemes for Tree Representation.
Proceedings of the Distributed Computing, 2005

Adaptive Collaboration in Peer-to-Peer Systems.
Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS 2005), 2005

Label-Guided Graph Exploration by a Finite Automaton.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004
Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks.
Proceedings of the STACS 2004, 2004

Approximating Minimum Max-Stretch spanning Trees on unweighted graphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Fault-tolerant gathering algorithms for autonomous mobile robots.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Approximation Algorithm for Hotlink Assignment in the Greedy Model.
Proceedings of the Structural Information and Communication Complexity, 2004

Robot Convergence via Center-of-Gravity Algorithms.
Proceedings of the Structural Information and Communication Complexity, 2004

Collaboration of untrusting peers with changing interests.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Graph Exploration by a Finite Automaton.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems.
Proceedings of the Algorithms, 2004

2003
Compact routing schemes with low stretch factor.
J. Algorithms, 2003

Compact and localized distributed data structures.
Distributed Computing, 2003

The Power of Small Coalitions in Graphs.
Discrete Applied Mathematics, 2003

Approximation Algorithm for Hotlink Assignments in Web Directories.
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

MST construction in O(log log n) communication rounds.
Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Hotlink Enhancement Algorithms for Web Directories: (Extended Abstract).
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Labeling Schemes for Weighted Dynamic Trees.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Spanning Trees with Low Maximum/Average Stretch.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

Localized Network Representations.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002
Local majorities, coalitions and monopolies in graphs: a review.
Theor. Comput. Sci., 2002

How to Be an Efficient Snoop, or the Probe Complexity of Quorum Systems.
SIAM J. Discrete Math., 2002

Station Layouts in the Presence of Location Constraints.
Journal of Interconnection Networks, 2002

Exact Algorithms and Approximation Schemes for Base Station Placement Problems.
Proceedings of the Algorithm Theory, 2002

Labeling Schemes for Dynamic Tree Networks.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

Asynchronous Resource Discovery in Peer to Peer Networks.
Proceedings of the 21st Symposium on Reliable Distributed Systems (SRDS 2002), 2002

Labeling schemes for flow and connectivity.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Low Stretch Spanning Trees.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001
The Wakeup Problem in Synchronous Broadcast Systems.
SIAM J. Discrete Math., 2001

Low Complexity Variants of the Arrow Distributed Directory.
J. Comput. Syst. Sci., 2001

Sparse communication networks and efficient routing in the plane.
Distributed Computing, 2001

Assigning labels in an unknown anonymous network with a leader.
Distributed Computing, 2001

The Dense k-Subgraph Problem.
Algorithmica, 2001

Small k-Dominating Sets in Planar Graphs with Applications.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2001

The Average Hop Count Measure for Virtual Path Layouts.
Proceedings of the Distributed Computing, 15th International Conference, 2001

(1+epsilon, beta)-spanner constructions for general graphs.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Deterministic resource discovery in distributed networks.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Distance labeling in graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

The Client-Server 2-Spanner Problem with Applications to Network Design.
Proceedings of the SIROCCO 8, 2001

Distributed MST for constant diameter graphs.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Average probe complexity in quorum systems.
Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Approximating k-Spanner Problems for k>2.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Approximate Distance Labeling Schemes.
Proceedings of the Algorithms, 2001

2000
A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction.
SIAM J. Comput., 2000

Tight Fault Locality.
SIAM J. Comput., 2000

Proximity-preserving labeling schemes.
Journal of Graph Theory, 2000

Feedback vertex set in hypercubes.
Inf. Process. Lett., 2000

Distributed Algorithms for English Auctions.
Proceedings of the Distributed Computing, 14th International Conference, 2000

Approximation Algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems.
Proceedings of the Algorithm Theory, 2000

Distance Labeling Schemes for Well-Separated Graph Classes.
Proceedings of the STACS 2000, 2000

The Hardness of Approximating Spanner Problems.
Proceedings of the STACS 2000, 2000

Extremal bounds for probabilistic polling in graphs.
Proceedings of the SIROCCO 7, 2000

Deterministic distributed resource discovery (brief announcement).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

Sparse communication networks and efficient routing in the plane (extended abstract).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

The wakeup problem in synchronous broadcast systems (extended abstract).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

Assigning labels in unknown anonymous networks (extended abstract).
Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

Informative Labeling Schemes for Graphs.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Strong Inapproximability of the Basic k-Spanner Problem.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
The Compactness of Interval Routing.
SIAM J. Discrete Math., 1999

Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks.
SIAM J. Comput., 1999

Fault-Local Distributed Mending.
J. Algorithms, 1999

Edge-disjoint spanners of complete graphs and complete digraphs.
Discrete Mathematics, 1999

Approximating the Weight of Shallow Steiner Trees.
Discrete Applied Mathematics, 1999

Proximity-Preserving Labeling Schemes and Their Applications.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

Station Layouts in the Presence of Location Constraints.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

A Variant of the Arrow Distributed Directory with Low Average Complexity.
Proceedings of the Automata, 1999

Distributed Probabilistic Polling and Applications to Proportionate Agreement.
Proceedings of the Automata, 1999

A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Faster Exact Solutions for Some NP-Hard Problems.
Proceedings of the Algorithms, 1999

1998
Approximate Maxima Finding of Continuous Functions under Restricted Budget.
Theor. Comput. Sci., 1998

A Sublinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.
SIAM J. Comput., 1998

Optimal Broadcast with Partial Knowledge.
SIAM J. Comput., 1998

Near-Linear Time Construction of Sparse Neighborhood Covers.
SIAM J. Comput., 1998

Fast Distributed Construction of Small k-Dominating Sets and Applications.
J. Algorithms, 1998

The Compactness of Interval Routing for Almost All Graphs.
Proceedings of the Distributed Computing, 12th International Symposium, 1998

Directed Virtual Path Layouts in ATM Networks.
Proceedings of the Distributed Computing, 12th International Symposium, 1998

Thy Neighbor's Interval is Greener: A Proposal for Exploiting Interval Routing Schemes (Position paper).
Proceedings of the SIROCCO'98, 1998

Compact Routing Schemes with Low Stretch Factor (Extended Abstract).
Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998

Deterministic Polylog Approximation for Minimum Communication Spanning Trees.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Distributed Matroid Basis Completion via Elimination Upcast and Distributed Correction of Minimum-Weight Spanning Trees.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

An approximation algorithm for minimum-cost network design.
Proceedings of the Robust Communication Networks: Interconnection and Survivability, 1998

1997
Load Balancing in Quorum Systems.
SIAM J. Discrete Math., 1997

Crumbling Walls: A Class of Practical and Efficient Quorum Systems.
Distributed Computing, 1997

The Availability of Crumbling Wall Quorum Systems.
Discrete Applied Mathematics, 1997

Randomized Approximation of Bounded Multicovering Problems.
Algorithmica, 1997

Approximating Shallow-Light Trees (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Size Bounds for Dynamic Monopolies.
Proceedings of the SIROCCO'97, 1997

Approximating Minimum Communication Spanning Trees.
Proceedings of the SIROCCO'97, 1997

1996
Fast Distributed Network Decompositions and Covers.
J. Parallel Distrib. Comput., 1996

Scheduling Jobs Using Common Resources.
Inf. Comput., 1996

Approximate Maxima Finding of Continuous Functions Under Restricted Budget (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996

Majority Voting, Coalitions and Monopolies in Graphs.
Proceedings of the SIROCCO'96, 1996

Tight Bounds on the Size of 2-Monopolies.
Proceedings of the SIROCCO'96, 1996

How to be an Efficient Snoop, or the Probe Complexity of Quorum Systems (Extended Abstract).
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

The Complexity of Data Mining on the Web (Abstract).
Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

Generalized Submodular Cover Problems and Applications.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

1995
The Complexity of Reconfiguring Network Models
Inf. Comput., August, 1995

A Graph-Theoretic Game and Its Application to the k-Server Problem.
SIAM J. Comput., 1995

A Note on Optimal Time Broadcast in Faulty Hypercubes.
J. Parallel Distrib. Comput., 1995

Online Tracking of Mobile Users.
J. ACM, 1995

The Availability of Quorum Systems.
Inf. Comput., 1995

On the maximum density of 0-1 matrices with no forbidden rectangles.
Discrete Mathematics, 1995

Optimal Broadcast with Partial Knowledge (Extended Abstract).
Proceedings of the Distributed Algorithms, 9th International Workshop, 1995

Load Balancing in Quorum Systems (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Bubbles: adaptive routing scheme for high-speed dynamic networks (Extended Abstract).
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

The Power of Small Coalitions in Graphs.
Proceedings of the Structure, Information and Communication Complexity, 1995

Crumbling Walls: A Class of Practical and Efficient Quorum Systems (Extended Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Fast Distributed Construction of k-Dominating Sets and Applications.
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Fault-Local Distributed Mending (Extended Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

Tight Fault Locality (Extended Abstract).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Computing with Noisy Information.
SIAM J. Comput., 1994

Traffic-light scheduling on the grid.
Discrete Applied Mathematics, 1994

Generating Low-Degree 2-Spanners.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
Distance-Dependent Distributed Directories
Inf. Comput., April, 1993

Time-Space Tradeoffs for Set Operations.
Theor. Comput. Sci., 1993

How to Allocate Network Centers.
J. Algorithms, 1993

Approximating Bounded 0-1 Integer Linear Programs.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Sphere Packing and Local Majorities in Graphs.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

On Choosing a Dense Subgraph (Extended Abstract)
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
Routing with Polynomial Communication-Space Trade-Off.
SIAM J. Discrete Math., 1992

Single Round Simulation on Radio Networks.
J. Algorithms, 1992

Traffic-Light Scheduling on the Grid (Extended Abstract).
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Distributed Resource Allocation Algorithms (Extended Abstract).
Proceedings of the Distributed Algorithms, 6th International Workshop, 1992

Generating Sparse 2-spanners.
Proceedings of the Algorithm Theory, 1992

Low-Diameter Graph Decomposition is in NC.
Proceedings of the Algorithm Theory, 1992

Adapting to Asynchronous Dynamic Networks (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Competitive Distributed Job Scheduling (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Fast Network Decomposition (Extended Abstract).
Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992

Approximation Algorithms for Minimum Time Broadcast.
Proceedings of the Theory of Computing and Systems, 1992

The Complexity of Reconfiguring Network Models.
Proceedings of the Theory of Computing and Systems, 1992

1991
Fault-Tolerant Critical Section Management in Asynchronous Environments
Inf. Comput., November, 1991

Tight Bounds on Minimum Broadcast Networks.
SIAM J. Discrete Math., 1991

A Lower Bound for Radio Broadcast.
J. Comput. Syst. Sci., 1991

Approximation Algorithms for Selecting Network Centers (Preliminary Vesion).
Proceedings of the Algorithms and Data Structures, 1991

Concurrent Online Tracking of Mobile Users.
Proceedings of the SIGCOMM '91, 1991

Compact Deterministic Distributed Dictionaries (Extended Abstract).
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Efficient Deadlock-Free Routing.
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

Broadcast with Partial Knowledge (Preliminary Version).
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

On Buffer-Economical Store-and-Forward Deadlock Prevention.
Proceedings of the Proceedings IEEE INFOCOM '91, 1991

The POwer of Reconfiguration.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract).
Proceedings of the On-Line Algorithms, 1991

1990
Renaming in an Asynchronous Environment
J. ACM, July, 1990

A Trade-Off between Information and Communication in Broadcast Protocols
J. ACM, April, 1990

A Time-Randomness Trade-Off for Oblivious Routing.
SIAM J. Comput., 1990

Time-Optimal Leader Election in General Networks.
J. Parallel Distrib. Comput., 1990

Improved Routing Strategies with Succinct Tables.
J. Algorithms, 1990

Distributed Data Structures: A Complexity-Oriented View.
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Greedy Packet Scheduling.
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

Computing with Unreliable Information (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Randomized Broadcast in Networks.
Proceedings of the Algorithms, 1990

Cost-Sensitive Analysis of Communication Protocols.
Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990

Network Synchronization with Polylogarithmic Overhead
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Sparse Partitions (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
The Token Distribution Problem.
SIAM J. Comput., 1989

Time bounds on fault-tolerant broadcasting.
Networks, 1989

Packet Distribution on a Ring.
J. Parallel Distrib. Comput., 1989

Graph spanners.
Journal of Graph Theory, 1989

A trade-off between space and efficiency for routing tables.
J. ACM, 1989

Constructng disjoint paths on expander graphs.
Combinatorica, 1989

Fault-Tolerant Critical Section Management in Asynchronous Networks.
Proceedings of the Distributed Algorithms, 1989

Compact Distributed Data Structures for Adaptive Routing (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On the Complexity of Radio Communication (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Square Meshes Are Not Always Optimal.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988
Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput., 1988

A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract)
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

A Tradeoff between Information and Communication in Broadcast Protocols.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
On Fault Tolerant Routings in General Networks
Inf. Comput., July, 1987

The Generalized Packet Routing Problem.
Theor. Comput. Sci., 1987

Concurrent Program Schemes and Their Logics.
Theor. Comput. Sci., 1987

Communication in Concurrent Dynamic Logic.
J. Comput. Syst. Sci., 1987

Concurrent dynamic logic.
J. ACM, 1987

Constructing Disjoint Paths on Expander Graphs (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

An Optimal Synchronizer for the Hypercube.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

Achievable Cases in an Asynchronous Environment (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986
Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

On Fault Tolerant Routings in General Networks.
Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, 1986

The Token Distribution Problem (Preliminary Version)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Process Logic with Regular Formulas.
Theor. Comput. Sci., 1985

More on Looping vs. Repeating in Dynamic Logic.
Inf. Process. Lett., 1985

Concurrent Dynamic Logic (Extended Abstract)
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984
On Static Logics, Dynamic Logics, and Complexity Classes
Information and Control, 1984

A generalized closure and complement phenomenon.
Discrete Mathematics, 1984

1983
A note of omega-regular languages.
Bulletin of the EATCS, 1983


  Loading...