-
Chapter and Conference Paper
Brief Announcement: Self Masking for Hardening Inversions
The question whether one way functions (i.e., functions that are easy to compute but hard to invert) exist is arguably one of the central problems in complexity theory, both from theoretical and practical aspe...
-
Article
MinMax algorithms for stabilizing consensus
In the stabilizing consensus problem each agent of a networked system has an input value and is repeatedly writing an output value; it is required that eventually all the output values stabilize to the same value...
-
Article
Simple and optimal randomized fault-tolerant rumor spreading
We revisit the classic problem of spreading a piece of information in a group of \(n\) ...
-
Article
Open AccessStochastic errors vs. modeling errors in distance based phylogenetic reconstructions
Distance-based phylogenetic reconstruction methods use evolutionary distances between species in order to reconstruct the phylogenetic tree spanning them. There are many different methods for estimating distan...
-
Chapter and Conference Paper
Stochastic Errors vs. Modeling Errors in Distance Based Phylogenetic Reconstructions
Distance based phylogenetic reconstruction methods use the evolutionary distances between species in order to reconstruct the tree spanning them. This paper continues the line of research which attempts to adjust...
-
Chapter and Conference Paper
Efficient Approximation of Convex Recolorings
A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a conv...
-
Chapter and Conference Paper
Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms
A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc. e.g., a perfect phylogenet...
-
Chapter and Conference Paper
Using Semi-definite Programming to Enhance Supertree Resolvability
Supertree methods are used to construct a large tree over a large set of taxa, from a set of small trees over overlap** subsets of the complete taxa set. Since accurate reconstruction methods are currently l...
-
Chapter and Conference Paper
Approximation Algorithms for Survivable Optical Networks
We are motivated by the developments in all-optical networks - a new tech- nology that supports high bandwidth demands. These networks provide a set of ligthpaths which can be seen as high-bandwidth pipes on w...
-
Chapter and Conference Paper
Minimum propositional proof length is NP-hard to linearly approximate
We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within any constant factor. These results hold for all Frege systems, for all extended Frege systems, f...
-
Chapter and Conference Paper
Computing in totally anonymous asynchronous shared memory systems
In the totally anonymous shared memory model of asynchronous distributed computing, processes have no id's and run identical programs. Moreover, processes have identical interface to the shared memory, and in par...
-
Article
Possibility and impossibility results in a shared memory environment
We focus on unreliable asynchronous shared memory model which support only atomic read and write operations. For such a model we provide a necessary condition for the solvability of problems in the presence of...
-
Chapter and Conference Paper
On the robustness of h m r
We introduce an N-process deterministic concurrent object for N ≥ 3 processes, called the conditional consensus object. This object, denoted as W, is hard-wired in the sense that each process P can access it usin...
-
Article
Closed schedulers: a novel technique for analyzing asynchronous protocols
Analyzing distributed protocols in various models often involves a careful analysis of the set ofadmissible runs, for which the protocols should behave correctly. In particular, the admissible runs assumed by at-...
-
Chapter and Conference Paper
Average and randomized complexity of distributed problems
A.C. Yao proved that in the decision-tree model the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is sh...
-
Chapter and Conference Paper
Exotic behaviour of consensus numbers
Let the consensus number of a given set \(\mathcal{S}\) of shared objects, denoted
-
Article
A lower bound on the period length of a distributed scheduler
Ad-scheduling of a graphG is a sequence of rounds, each consisting of some of the nodes of the graph, such that the distance between any two nodes participating in the same round is greater thand. Ad-scheduler is...
-
Article
Self-stabilization of dynamic systems assuming only read/write atomicity
Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spann...
-
Chapter and Conference Paper
On the limitation of the global time assumption in distributed systems
An ongoing debate among theoreticians of distributed systems concerns the global time issue. The basic question seems to be to what extent does a model with global time reflect the ‘real’ behavior of a distrib...
-
Chapter and Conference Paper
Closed schedulers: Constructions and applications to consensus protocols
Analyzing distributed protocols in various models often involves a careful analysis of the set of admissible runs, for which the protocols should behave correctly. In particular, the admissible runs assumed by a
