Shlomo Moran

TCS Journal 2025 Journal Article

Self-masking for hardening inversions

• Paweł Cyprys
• Shlomi Dolev
• Shlomo Moran

The question of 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 aspects. While proving that such functions exist could be hard, there were quite a few attempts to provide functions that are one way “in practice”, namely, they are easy to compute, but there are no known polynomial time algorithms that compute their (generalized) inverse (or that computing their inverse is as hard as notoriously difficult tasks, like factoring very large integers). In this paper, we introduce the self-masking technique, which converts polynomial time computable functions to functions that are likely to be harder to invert. The technique is first defined for univalent functions (note that one way functions that are univalent are basic ingredients for cryptographic protocols). Informally, a self masked version of a univalent function f, denoted [ f ], replaces two masking substrings of f ( x ) by their XOR. The masking substrings are critical if [ f ] remains univalent (w. h. p.). Thus, when the masking substrings are critical, inverting [ f ] ( x ) is at least as hard as reconstructing the masking substrings from their XOR. We apply this technique to functions based on variants of the subset sum problem and obtain functions that resist known techniques for inverting the original, unmasked functions (see, e. g. , [13]). Applications of this technique to other functions, as well as its extension to multivalent functions, are also discussed.

TCS Journal 2019 Journal Article

The firing squad problem revisited

• Bernadette Charron-Bost
• Shlomo Moran

In the classical firing squad problem, an unknown number of nodes represented by identical finite states machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated “firing” state. A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously. The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, and that the inter-node communication links can be changed arbitrarily in each time unit, i. e. , are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem? Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.

SODA Conference 2008 Conference Paper

Fast and reliable reconstruction of phylogenetic trees with very short edges

• Ilan Gronau
• Shlomo Moran
• Sagi Snir

TCS Journal 2007 Journal Article

On the hardness of inferring phylogenies from triplet-dissimilarities

• Ilan Gronau
• Shlomo Moran

This work considers the problem of reconstructing a phylogenetic tree from triplet-dissimilarities, which are dissimilarities defined over taxon-triplets. Triplet-dissimilarities are possibly the simplest generalization of pairwise dissimilarities, and were used for phylogenetic reconstructions in the past few years. We study the hardness of finding a tree best fitting a given triplet-dissimilarity table under the ℓ ∞ norm. We show that the corresponding decision problem is NP-hard and that the corresponding optimization problem cannot be approximated in polynomial time within a constant multiplicative factor smaller than 1. 4. On the positive side, we present a polynomial time constant-rate approximation algorithm for this problem. We also address the issue of best-fit under maximal distortion, which corresponds to the largest ratio between matching entries in two triplet-dissimilarity tables. We show that it is NP-hard to approximate the corresponding optimization problem within any constant multiplicative factor.

TCS Journal 2004 Journal Article

Competitive caching of query results in search engines

• Ronny Lempel
• Shlomo Moran

We study the problem of caching query result pages in Web search engines. Popular search engines receive millions of queries per day, and for each query, return a result page to the user who submitted the query. The user may request additional result pages for the same query, submit a new query, or quit searching altogether. An efficient scheme for caching query result pages may enable search engines to lower their response time and reduce their hardware requirements. This work studies query result caching within the framework of the competitive analysis of algorithms. We define a discrete time stochastic model for the manner in which queries are submitted to search engines by multiple user sessions. We then present an adaptation of a known online paging scheme to this model. The expected number of cache misses of the resulting algorithm is no greater than 4 times the expected number of misses that any online caching algorithm will experience under our specific model of query generation.

I&C Journal 2002 Journal Article

Computing in Totally Anonymous Asynchronous Shared Memory Systems

• Hagit Attiya
• Alla Gorbach
• Shlomo Moran

In the totally anonymous shared memory model of asynchronous distributed computing, processes have no identifiers and run identical programs. Moreover, processes have identical interface to the shared memory, and in particular, there are no single-writer registers. This paper assumes that processes do not fail, and the shared memory consists only of read/write registers, which are initialized to some default value. A complete characterization of the functions and agreement tasks that can be solved in this model is presented. Furthermore, it is shown that if a function is computable, then two registers are sufficient for some algorithm to compute it. Consensus is an important agreement task that can be computed. The paper proves logarithmic lower bounds on the number of registers and rounds needed for solving consensus in this model. A consensus protocol using a linear number of shared registers and rounds is also presented.

TCS Journal 2002 Journal Article

Public data structures: counters as a special case

• Hagit Brit
• Shlomo Moran
• Gadi Taubenfeld

A public data structure is required to work correctly in a concurrent environment where many processes may try to access it, possibly at the same time. In implementing such a structure nothing can be assumed in advance about the number or the identities of the processes that might access it. While most of the known concurrent data structures are not public, there are few which are public. Interestingly, these public data structures all deal with various variants of counters, which are data structures that support two operations: increment and read. In this paper, we define the notion of a public data structure, and investigate several types of public counters. Then we give an optimal construction of public counters which satisfies a weak correctness condition, and show that there is no public counter which satisfies a stronger condition. It is hoped that this work will provide insights into the design of other, more complicated, public data structures.

TCS Journal 2000 Journal Article

On the totalk-diameter of connection networks

• Yefim Dinitz
• Tamar Eilam
• Shlomo Moran
• Shmuel Zaks

TCS Journal 2000 Journal Article

Simple and efficient network decomposition and synchronization

• Shlomo Moran
• Sagi Snir

We present a simple and efficient method for constructing sparse decompositions of networks. This method is used to construct the sparse decompositions needed for variants of the synchronizers in [2, 15] in O(|V|) time and O(|E|+|V|log|V|) communication complexities, while maintaining constant messages size and constant memory per edge. Using these decompositions, we present simple and efficient variants of the synchronizers in the above papers. For example, our constructions enable to perform Breadth First Search in an asynchronous network, in which no preprocessing had been done, in communication and time complexities of O(K|V|D+|E|+|V|log|V|) and O(Dlog K|V|+|V|), respectively, where K⩾2 is a parameter, and D is the diameter of the network. We also present an efficient cover-coarsening algorithm, which uses a novel technique for efficient merging of clusters, and improves previous coarsening algorithms in several aspects.

STOC Conference 1999 Conference Paper

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

• Yefim Dinitz
• Shlomo Moran
• Sergio Rajsbaum

MFCS Conference 1998 Conference Paper

Minimum Propositional Proof Length is NP-Hard to Linearly Approximate

• Michael Alekhnovich
• Sam Buss
• Shlomo Moran
• Toniann Pitassi

Abstract 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, for resolution and Horn resolution, and for the sequent calculus and the cut-free sequent calculus. Also, if NP is not in \(QP = DTIME(n^{log^{O(1)} n} )\), then it is impossible to approximate minimum propositional proof length within a factor of \(2^{log^{(1 - \varepsilon )} n}\) for any є > 0. All these hardness of approximation results apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and prove the same hardness results for Monotone Minimum (Circuit) Satisfying Assignment.

TCS Journal 1995 Journal Article

Tight bounds on the round complexity of distributed 1-solvable tasks

• Ofer Biran
• Shlomo Moran
• Shmuel Zaks

A distributed task T is 1-solvable if there exists a protocol that solves it in the presence of (at most) one crash failure. A precise characterization of the 1-solvable tasks was given by Biran et al. (1990). In this paper we determine the number of rounds of communication that are required, in the worst case, by a protocol which 1-solves a given 1-solvable task T for n processors. We define the radius R(T) of T, and show that if R(T) is finite, then the number of rounds is Θ(log n R(T)); more precisely, we give a lower bound of log (n − 1) R(T), and an upper bound of 2 + ⌈log (n − 1) R(T)⌉. The upper bound implies, for example, that each of the following tasks: renaming, order preserving renaming (Attiya et al, 1990) and binary monotone consensus (Biran et al. , 1990) can be solved in the presence of one fault in 3 rounds of communications. All previous protocols that 1-solved these tasks required Ω(n) rounds. The result is also generalized to tasks whose radii are not bounded, e. g. , the approximate consensus and its variants (Dolev et al. , 1986; Biran et al. , 1990).

TCS Journal 1993 Journal Article

Rotating-table games and derivatives of words

• Reuven Bar Yehuda
• Tuvi Etzion
• Shlomo Moran

We consider two versions of a game for two players, A and B. The game consists of manipulations of words of length n over an alphabet of size σ, for arbitrary n and σ. For σ = 2 the game is described as follows: initially, player A puts n drinking glasses on a round table, some of which are upside down. Player B attempts to force player A to set all the glasses in the upright position. For this, he instructs player A to invert some of the glasses. Before following the instruction, player A has the freedom to rotate the table, and then to invert the glasses that are in the locations originally pointed by player B. In one version of the game, player B is blindfolded and in the other he is not. We show that player B has winning strategies for both games iff n and σ are powers of the same prime. In both games we provide optimal winning strategies for B. The analysis of the games is closely related to the concept of the derivative of a σ-ary word of length n. In particular, it is related to the depth of such word, which is the smallest k such that the kth derivative of the word is the all-zero word. We give tight upper bounds on the depth of σ-ary words of length n, where σ and n are powers of the same prime.

TCS Journal 1991 Journal Article

Optimal covering of cacti by vertex-disjoint paths

• Shlomo Moran
• Yaron Wolfstahl

A path cover (or in short: cover) of a graph G is a set of vertex-disjoint paths which cover all the vertices of G. An optimal cover of G is a cover of the smallest possible cardinality. Notable applications of graph covering are code optimization and mapping parallel programs to parallel architectures. The optimal covering problem is known to be NP-complete even for cubic 3-connected planar graphs. Motivated by the intractability of this problem, we develop an efficient optimal covering algorithm for cacti (i. e. graphs where no edge lies on more than one cycle). In doing so we generalize the results of Boesch, Gimpel, McHugh (1974) and of Pinter, Wolfstahl (1987) where optimal covering algorithms for trees and graphs where no two cycles share a vertex were presented.

STOC Conference 1990 Conference Paper

The Wakeup Problem (Extended Abstract)

• Michael J. Fischer
• Shlomo Moran
• Steven Rudich
• Gadi Taubenfeld

I&C Journal 1989 Journal Article

Proving properties of interactive proofs by a generalized counting technique

• László Babai
• Shlomo Moran

The problem of proving membership in languages accepted by interactive proof protocols is reduced to the problem of estimating the number of leaves in certain trees. Using this reduction, we present a direct proof that every language accepted by an interactive protocol whithin g(n) rounds is also accepted by an Arthur Merlin game within ⌈ g(n) 2 ⌉ rounds. This unifies the proofs of the two main positive results on the IP Hierarchy, namely: that private coin tossing can be replaced by public coin tossing, and that the numer of interactions can be reduced by a constant factor.

FOCS Conference 1984 Conference Paper

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

• Shlomo Moran
• Marc Snir
• Udi Manber

Combinatorial techniques for extending lower bounds results for decision trees to general types of queries are presented. We consider problems, which we call order invariant, that are defined by simple inequalities between inputs. A decision tree is called k-bounded if each query depends on at most k variables. We make no further assumptions on the type of queries. We prove that we can replace the queries of any k-bounded decision tree that solves an order invariant problem over a large enough input dornain with k-bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison based algorithms are valid for general k-bounded decision trees, where k is a constant. We also prove an /spl Omega/(n log n) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k - )(n/sup c/) and c < 1/2. This lower bound is tight since that there exist n/sup 1/2/-bounded decision trees of complexity 0(n) that solve the element uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

TCS Journal 1983 Journal Article

On the control power of integer division

• Oscar H. Ibarra
• Shlomo Moran
• Louis E. Rosier

We consider the problem of simplifying the control structure of programs that manipulate numbers. In particular, we examine some simple programming language constructs which have sufficient computational power to eliminate all or most branching instructions (e. g. ‘while’, ‘if-then-else’ and ‘goto’ constructs) from such programs. We show that the operation of integer division by 2 is of considerable importance in this context. We also show that integer division by 2 cannot be computed by any loop-free program over the set of rational instructions, and hence that the power of integer division by 2 is, in a sense, greater than that of the conditional and unconditional branching instructions. We also investigate the power of indirect addressing in simplifying the control structure of programs over numerical inputs.

TCS Journal 1982 Journal Article

On the complexity of simple arithmetic expressions

• Oscar H. Ibarra
• Brian S. Leininger
• Shlomo Moran

Let E be the set of all simple arithmetic expressions of the form E(x) = xT l …T k where x is a nonnegative integer variable and each T i is a multiplication or integer division by a positive integer constant. We investigate the complexity of the inequivalence and the bounded inequivalence problems for expressions in E. (The bounded inequivalence problem is the problem of deciding for arbitrary expressions E 1(x) and E 2(x) and a positive integer l whether or not E 1(x) ≠ E 2(x) for some nonnegative integer x<l. If l = ∞, i. e. , there is no upper bound on x, the problem becomes the inequivalence problem.) We show that the inequivalence problem (or equivalently, the equivalence problem) for a large subclass of E is decidable in polynomial time. Whether or not the problem is decidable in polynomial time for the full class E remains open. We also show that the bounded inequivalence problem is NP-complete even if the divisors are restricted to be equal to 2. This last result can be used to sharpen some known NP-completeness results in the literature. Note that if division is rational division, all problems are trivially decidable in polynomial time.

TCS Journal 1981 Journal Article

General approximation algorithms for some arithmetical combinatorial problems

• Shlomo Moran

A general approximation technique for a large class of NP-hard optimization problems which involve arithmetic calculations is given. This technique guarantees a worst case relative error smaller than ε in time which is polynomial both in the size of the problem instance and 1/ε. It is also shown that problems in that class which are not approximable by this technique are not approximable in polynomial time at all, provided P ≠ NP, and hence this technique is the most general approximation technique applicable to this class.