Abstract In the early 1980s, the grid area required by the sorting nets of Batcher for input vectors of length N was investigated by Thompson. He showed that the Ω(N2) area was necessary and sufficient, but the hidden constant factors, both for the lower and upper bounds, were not discussed. In this paper, a lower bound of (N − 1)2/2 is proven, for the area required by any sorting network. Upper bounds of 4N2 and 3N2 are shown for the bitonic sorter and the odd—even sorter, respectively. In the layouts, which are presented to establish these upper bounds, slanted lines are used and there are no knock‐knees. © 2001 John Wiley & Sons, Inc.

A technique for automatically producing a rectilinear planar drawings of interconnection networks is described. It is based on the layered cross product suggested by Even and Litman. The technique is demonstrated on the butterfly network, the binary tree, and the mesh-of-trees of Leighton. © 2000 John Wiley & Sons, Inc.

For the Butterfly of N input/output vertices we present a layout on the square grid of area k N2 + o(N').A lower bound of the same order is proved.The encompassing rectangle which defines the area is 45' slanted w.r.t. the grid axes and the input/output vertices are not on the boundary of this rectangle.For the Butterfly of A4 input/output edges we present a layout of area +M" + o(M').In this layout the input edges are on the 1.h.s. of the upright encompassing rectangle and the output edges are on its r.h.s.Again this is also a lower bound.Both layouts are scalable.i.e. if one allocates for each switch a square of Q x a area, the layouts remain of area f N2 + o( N2) and iA4' + o(M'), respectively, where the value of a affects only the o(N2) and o(A4') terms.Both layouts are free of knock-knees.

The grid-area required by a sorting net for input vectors of length N is shown to be at least (N -1)"/2.Of 11 a sorting nets which use o(N2) comparators, the bitonic sorting net of Batcher has been known to have a layout of O(N"), but the hidden constant factor has not been investigated.A straightforward use of known techniques leads to a layout of grid-area 20.25N2.We present area-efficient layouts of the bitonic

This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let G be a graph with four distinguished and distinct vertices, w 1 , w 2 , b 1 , b 2 . Consider the two properties, TRI + (G) and MONO(G), defined as follows. TRI + (G): There is a planar drawing of G such that all 3-cycles of G are faces; all faces of G are triangles except for the single face which is the 4-cycle (w 1 -b 1 -w 2 -b 2 -w 1 ). MONO(G): G contains the 4-cycle (w 1 -b 1 -w 2 -b 2 -w 1 ) and, for any labeling of the vertices of G by the colors {white, black} such that w 1 and w 2 are white, while b 1 and b 2 are black, precisely one of the following holds. There is a path of white vertices connecting w 1 and w 2 . There is a path of black vertices connecting b 1 and b 2 . Our main result is that a graph G enjoys property TRI + (G) if and only if it is minimal with respect to property MONO. Building on this, we show that one can decide in polynomial time whether or not a given graph G has property MONO(G).

The Layered Cross Product (LCP) of layered graphs is introduced. It is shown that several well-known networks are LCPs of simple layered graphs, such as trees. We believe that this new tool will make the construction of new networks easier, and it will simplify the study of the properties of known and new networks. © 1997 John Wiley & Sons, Inc.

We establish upper and lower bounds on the layout area of the butterfly network, which differ only in low-order terms. Specifically, the N-input, N-output butterfly network can be laid out in area (1 + o(1)) N^2, while no layout of the network can have area smaller than (1 - o(1)) N^2. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.

Article Layered cross product—a technique to construct interconnection networks Share on Authors: Shimon Even View Profile , Ami Litman View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 60–69https://doi.org/10.1145/140901.140908Published:01 June 1992 10citation249DownloadsMetricsTotal Citations10Total Downloads249Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Thispaper investigates the capabilities of systolic systems.We show that arty synchronous system can be transformed into an equivalent systolic system via two opposite techniques, one syntactic and the other semantic.

Directed, strongly connected networks of finite-state automata, of bounded in- and outdegree but unknown topology and unbounded size n, are considered. Protocols that are quadratic or linear in n and accomplish the following tasks are provided: waking up and reporting when done, constructing smart spanning trees out from the root and in to the root, conducting breadth-first and depth-first searches, sending a message from the endpoint of a (directed) edge to its startpoint, running a slow clock, and solving the firing squad synchronization problem. The protocols are highly parallel and entail the use of sequences of signals called 'snakes''. All the tasks are accomplished in less time than is possible with any previously known techniques.>

In a previous paper we analyzed the performance of networks with negligible transmission delay, who~ operation is controlled by a simple synchronizer.It was shown that full speed is achieved, for any wake-up pattern, by letting the netwonk run free, without the use of a "firing squad" mechanism or a scheduler.In this paper we investigate the effect of fixed delays in the communication channels on the performance of a netwo~ in which there is a global clock, but there is no global start-up signal.We show that here too, maximum rate of computation is always reached, just by using the synchronizer and letting the network run free.To a certain extent, the wake-up pattern may influence the length of the transitory stage and the periodicity of the steady state, but not the ultimate rate.

Assume each processor in a network has some piece of information.We study how efficiently information can be spread in a communication network.Specifically, we investigate the number of rounds necessary to spread all the pieces of information to all processors.This problem is known as the "gossip" problem, and initially, the question was to determine the number of telephone calls necessary to achieve complete dissemination.In this paper we study the "telegraph comnmnication node", where in each round, each processor is active only via one of its links and the communication is one-way, i.e. each processor can either transmit or receive, but not both.For an even number of processors, we prove upper and lower bounds on the number of rounds needed for disseminating the information in this telegraph mode.The two bounds are related to Fibonacci numbers and differ by, at most, an additive constant of 1.Our lower bound technique uses elements from matrix theory, specifically matrix norms.These results show, for the first time, that in the two-way mode, information can be distributed faster than in the one-way mode.Similar techniques are applied to obtain upper and lower bounds on the number of rounds needed for gossip in other communication modes.We consider the (pR, qS)communication modes, where during each round each processor can receive information from at most p processors or can send information to at most q processors, but no processor can send and receive during the same round. ITechnion, Israel Institute

Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. In this paper, general theorems of this kind that can be applied to several well-known automata-based complexity classes, including a common class of randomized algorithms, are proved.

The unicity distance of a cascade of random ciphers, with respect to known plaintext attack, is shown to be the sum of the key lengths. A time-space trade-off for the exhaustive cracking of a cascade of ciphers is shown. The structure of the set of permutations realized by a cascade is studied; it is shown that only l .2 k exhaustive experiments are necessary to determine the behavior of a cascade of l stages, each having k key bits. It is concluded that the cascade of random ciphers is not a random cipher. Yet, it is shown that, with high probability, the number of permutations realizable by a cascade of l random ciphers, each having k key bits, is 2 lk . Next, it is shown that two stages are not worse than one, by a simple reduction of the cracking problem of any of the stages to the cracking problem of the cascade. Finally, it is shown that proving a nonpolynomial lower bound on the cracking problem of long cascades is a hard task, since such a bound implies that P ≉ NP .

We deal with communication networks whose topology changes arbitrarily subject to the restriction that no edge-cut in the network persists forever. Up to now, no formal-ground rules have been proposed for such networks, and no protocol has been proved to possess any desirable property. We introduce a new proof methodology, in the sense that link-behavior in such networks is axiomatized.

Abstract Let G(V, E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints to be a transmitter, the other to be a receiver, and sending a message from the transmitter to the receiver through the line. We define several different models for communication networks, all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models, two problems arise: What is the maximum number of lines one can test simultaneously? and What is the minimum number of phases necessary for testing the entire network?, where, by “phase” we mean a period in which some tests are conducted simultaneously. We show that in most models, including the “natural” model of radio communication, both problems are NP‐hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem is unknown.

We define a p-party ping-pong protocol and its security problem, along the lines of Dolev and Yao's definition for twoparty ping-pong protocol. In the case of two parties, it was assumed, with no loss of generality, that there exists a single saboteur in the net and the protocol was defined to be secure iff it was secure against the active interventions of one saboteur. We show that for more than 2 parties this assumption can no longer be made and that for p parties 3(p-2) + 1 is a lower bound on the number of saboteurs which should be considered for the security problem. On the other hand we establish a 3(p-2) + 2 upper bound on the number of saboteurs which should be considered. We conclude that for a fixed p, p-party ping-pong protocols can be tested for security in 0(n3) time and 0(n2) space, when n is the length of the protocol. We show that if p, the number of participants in the protocol, is part of the input then the security problem becomes NP-Hard. Relaxing the definition of a ping-pong protocol so that operators can operate on half words (thus introducing commutativity of the operators) causes the security problem to become undecidable.

A set of transformations on binary vectors of lengthnis defined. These transformations are similar to those of the data encryption standard (DES) and therefore are called DES-like functions. It is proved that the group of permutations generated by the DES-like functions is exactly the alternating group of the set of binarynvectors.

Randomized protocols for signing contracts, certified mail, and flipping a coin are presented. The protocols use a 1-out-of-2 oblivious transfer subprotocol which is axiomatically defined. The 1-out-of-2 oblivious transfer allows one party to transfer exactly one secret, out of two recognizable secrets, to his counterpart. The first (second) secret is received with probability one half, while the sender is ignorant of which secret has been received. An implementation of the 1-out-of-2 oblivious transfer, using any public key cryptosystem, is presented.

The approximation problem for vertex cover of n-vertex planar graphs is treated. Two results are presented:

article Free Access Share on An On-Line Edge-Deletion Problem Authors: Yossi Shiloach IBM Israel Scientific Center, Technion City, Haifa, Israel and Stanford University, Stanford, California IBM Israel Scientific Center, Technion City, Haifa, Israel and Stanford University, Stanford, CaliforniaView Profile , Shimon Even Computer Science Department, Technion, Haifa, Israel and University of California, Berkeley, California Computer Science Department, Technion, Haifa, Israel and University of California, Berkeley, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 28Issue 1Jan. 1981 pp 1–4https://doi.org/10.1145/322234.322235Published:01 January 1981Publication History 189citation1,844DownloadsMetricsTotal Citations189Total Downloads1,844Last 12 Months172Last 6 weeks27 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A linear implementation of the optimal universal data compression methods of Lempel and Ziv is described.The main tool is McCreight's algorithm for constructing suffix trees.Both bounded and unbounded memory are considered.

This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem solvable in polynomial space is solvable in polynomial time. This result suggests that the theory of combinational games is difficult.

A very primitive version of Gotlieb’s timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multicommodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases.

A very primitive version of Gotlieb's timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).

This work presents a new efficient algorithm for finding a maximum matching in an arbitrary graph. Two implementations are suggested, the complexity of the first is O(n2.5) and the complexity of the second is O(m√n·log n) where n, m are the numbers of the vertices and the edges in the graph.

We consider a generalization, which we call the Shannon switching game on vertices, of a familiar board game called HEX. We show that determining who wins such a game if each player plays perfectly is very hard; in fact, it is as hard as carrying out any polynomial-space-bounded computation. This result suggests that the theory of combinatorial games is difficult.

ABSTRACrr.An algorithm for constructing an optimal prefix code of n eqmprobable words over r unequal cost coding letters is given.The discussion is in terms of rooted labeled trees.The algorithm consists of two parts.The first one is an extension algorithm which constructs a prefix code of n words.This code is either optimal or is a "good" approximation The second part is a mending algorithm which changes the code constructed by the extension algorithm into an optimal code in case it is not already optimal.The validity of the combined algorithm is proved and its structure is analyzed.The analysis leads to further improvement of the algorithm's efficiency.It is shown that the number of steps required is at mnst O(r.n.log n), if a heap data structure is used Alternatively, one can use a data structure of r queues, in which case the number of steps is bounded by O(r.n).

The algorithm presented in this paper is for testing whether the connectivity of a large graph of n vertices is at least k. First the case of undirected graphs is discussed, and then it is shown that a variation of this algorithm works for directed graphs. The number of steps the algorithm requires, in case $k < \sqrt n $, is bounded by $O(kn^3 )$.

An algorithm of Dinic for finding the maximum flow in a network is described. It is then shown that if the vertex capacities are all equal to one, the algorithm requires at most $O(|V|^{1/2} \cdot |E|)$ time, and if the edge capacities are all equal to one, the algorithm requires at most $O(|V|^{2/3} \cdot |E|)$ time. Also, these bounds are tight for Dinic’s algorithm. These results are used to test the vertex connectivity of a graph in $O(|V|^{1/2} \cdot |E|^2 )$ time and the edge connectivity in $O(|V|^{5/3} \cdot |E|)$ time.

We discuss the prefix encoding of aQ-ary source(Q \geq 2)into anL-symbol channel alphabet withL \geq Q. We present an optimal encoding scheme that minimizes the expected cost per symbol in the case of equally probable source symbols and arbitrary channel symbol costs.

A graph G with vertex set N = {1, 2, .-. , n} is called a permutation graph there exists a permutation P on N such that for i,j E N, (i -j)[P-'(i) -P-'(j)] < 0 if ar only if i and j are joined by an edge in G.A structural relationship is established between permutation graphs and transitive graph An algorithm for determining whether a given graph is a permutation graph is given.Efficie, algorithms for finding a maximum size clique and a minimum coloration of transitive grapl are presented.These algorithms are then shown to be applicable in solving problems in memo] allocation and circuit layout.

A regular expression is called unambiguous if every tape in the event can be generated from the expression in one way only. The flow-graph technique for constructing an expression is shown to preserve ambiguities of the graph, and thus, if the graph is that of a deterministic automaton, the expression is unambiguous. A procedure for generating a nondeterministic automaton which preserves the ambiguities of the given regular expression is described. Finally, a procedure for testing whether a given expression is ambiguous is given.

The construction of a shortest feedback shift register which generates a given finite sequence is described for the cases of linear and nonlinear feedback logic. It is shown that the ratio of the number of delay elements required in the linear case to that of the nonlinear case grows without bound for proper choice of sequences.

A Gray code counter which has an iterative and relatively simple structure is described. The code is shown to be the reflected binary Gray code, implying simple conversion of the count into binary code.

The problem of solving sequential Boolean equations is shown to be equivalent to the problem of finding whether there exists a path on a labeled graph for every sequence of labels. Algorithms are given for testing whether a solution exists, and if a solution with a finite delay exists. In case of existence of solutions the algorithms provide them.

The minimal number of terms required for representing any switching function as a modulo 2 sums of products is investigated, and an algorithm for obtaining economical realization is described. The main result is the following: every symmetric function of 2m+1 variables has a modulo 2 sum of products realization with at most 3mterms; but there are functions of n variables which require at least 2n/n log23 terms for sufficiently large n.

In this paper a relationship among distinct Pn+1, cycles, distinct stable maximum transient feedback shift registers of order n+1, and stable feedback shift registers of order n will be presented. In the course of the discussion, two algorithms will be introduced. The first will provide a one-to-one mapping between distinct stable feedback shift registers of order n and distinct stable maximum-transient feedback shift registers of order n+1. The second will provide a one-to-one mapping between distinct maximum transient feed-back shift registers of order n+1 and distinct Pn+1, cycles. As a corollary to these relationships, an enumeration of the stable feed-back shift registers is obtained.

This paper is a study of linear machines and their submachines. Methods are presented for finding the reduced form of a given linear machine with or without fixed initial state. A technique is suggested for detecting whether a machine is linear or can be embedded as a submachine in a linear machine. In the latter case a state assignment is produced for the minimum linear realization. Encoded inputs and outputs are assumed, but given machines are not assumed reduced, nor are there any restrictions on the number of states in the given machine or in the linear realization. The method also detects machines that are linearly realizable when constants are available. The main results are that the reduced form of a linear machine is linear and that a linearly realizable machine with r-independent states has an r-dimensional realization.

A coding graph is a model which contains all the types of finite automata and codes as special cases. A test for information losslessness and for information losslessness of finite order of a coding graph is described. Efficient methods of computation are given which make the calculation simple and mechanizable. The application of the tests to finite deterministic automata is discussed and a method of constructing a decoder for a given finite automaton that is information lossless of finite order, is described.

In a recent note by Bacon [1], a new result about the minimization of stochastic finite state machines has been proven. Extending the theory developed by Carlyle [2], he shows that all minimal-state forms of equivalent machines are state equivalent, and they all have the same number of states. He also describes a necessary and sufficient condition for a machine to be minimal.

In this paper the relation between a sequential circuit and its regular expression is investigated. The circuits are without special starting units. One method of analysis of a circuit leads to a set of equations whose solutions are regular expressions related to the state diagram of the circuit. In another approach, a set of regular equations, identical in form to the next state equations, is obtained directly from the circuit. By reversing the regular equations and using derivatives, the regular equations are transformed to a form related to the reverse state diagram. The discussion clarifies the relationship among circuits, regular expressions and state diagrams. Moreover, further insight is obtained into the solution of equations with as unknowns.

A (finite) code is called synchronizable ofMth order if, and only if, there exists a least positive integerMsuch that the knowledge of the lastMletters of any message suffices to determine a separation of code words. This condition is less constraining than the comma-free restriction. Sections I-IV is a description of a way of selecting a synchronizable block codeC_{\sigma , n}for a given alphabet with\deltaletters and a given code-word length n. It is proved thatC_{\sigma , n}is maximal in the sense that it contains as many words as possible; and an expression is given for the number of words inC_{\sigma , n}.^{1}Sections V-VIII is a description of a construction of phase-shift-keying synchronizable codes. In the PSK case the letters themselves cannot be identified by the receiver. Only the differences between successive letters can be detected. Thus, if the sequenceX_{1},X_{2}, \cdots , X_{l}is transmitted, then the observed sequence in the receiver isX_{2} - X_{1}, X_{3}- X_{2}, \cdots , X_{i+1}- X_{i}, \cdots , X_{l} - X_{l-1}. The letters are assumed to be the integers mod\delta; andX_{i+1} - X_{i}is taken mod\delta. This situation occurs in the reading of phase-modulated signals. The construction of these codes (calledK_{\sigma , n}) is based onC_{\sigma , n}.

A finite automation is called synchronizable ofNth order if the knowledge of the lastNoutputs suffices to determine the state of the automaton at one time during the lastNoutputs (including the initial and the final states). In an analogous manner synchronizability ofNth order is defined for variable length codes. The paper describes a test for synchronizability on a more general model, the coding graphs, and shows that finite automata and variable length codes are special cases of it.

A test for unique decipherability of a given codeword set is described. The test also shows whether the set is decipherable with a finite delay, and in the latter case, determines the necessary delay. Finally, it is shown how the test of Sardinas and Patterson [1] can be used to get the same result,^{1}as was conjectured by Gilbert and Moore [2].