Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

Theoretical Cryptanalysis of the Klimov-Shamir Number Generator TF-1

The internal state of the Klimov-Shamir number generator TF-1 consists of four words of size w bits each, whereas its intended strength is 2^2w. We exploit an asymmetry in its output function to show that the internal state can be recovered after having 2^w outputs, using 2^1.5w operations. For w = 32 the attack is practical, but for their recommended w = 64 it is only of theoretical interest.     

Production outsourcing: A linear programming model for the Theory-Of-Constraints

This paper presents an analysis of the outsourcing problem. Pertinent variables are identified and the relationships between them are defined. We formulate the outsourcing problem as a Linear-Programming (LP) problem and identify an analytical solution. We proceed with an example examining three decision models: standard cost accounting, standard Theory-Of-Constraints (TOC) and our own solution. The model enables managers to determine which products to manufacture and which to outsource. The solution of the LP formulation enables managers to apply the model by computing an operational ratio, without having to solve a linear programming problem. The final model is simpler to apply and requires the computation of fewer variables than other prevalent models.     

Arma spectral estimation based on partial autocorrelations — Part II: Statistical analysis

In a previous paper [1], a new algorithm for ARMA spectral estimation of stationary time series has been presented. The algorithm is based on nonlinear least squares fit of the sample partial autocorrelations to the partial autocorrelations generated by the assumed ARMA model. This paper explores the statistical properties of the above algorithm, including some numerical examples of the asymptotic variance of the estimated parameters, as compared to the Cramer-Rao bound. The results confirm the good performance of the algorithm and suggest an improvement in its implementation.     

Optimal smoothing schedules for real-time streams

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space requirement, and playback delay. We focus on lossy schedules, where data may be dropped due to limited bandwidth or space. We present the following results. First, we determine the optimal tradeoff between buffer space, smoothing delay, and link bandwidth for lossy smoothing schedules. Specifically, this means that if two of these parameters are given, we can precisely calculate the value for the third which minimizes data loss while avoiding resource wastage. The tradeoff is accomplished by a simple generic algorithm, that allows one some freedom in choosing which data to discard. This algorithm is very easy to implement both at the server and at the client, and it enjoys the nice property that only the server decides which data to discard, and the client needs only to reconstruct the stream.In a second set of results we study the case where different parts of the data have different importance, modeled by assigning a real weight to each packet in the stream. For this setting we use competitive analysis, i.e., we compare the weight delivered by on-line algorithms to the weight of an optimal off-line schedule using the same resources. We prove that a natural greedy algorithm is 4-competitive. We also prove a lower bound of 1.23 on the competitive ratio of any deterministic on-line algorithm. Finally, we give a few experimental results which seem to indicate that smoothing is very effective in practice, and that the greedy algorithm performs very well in the weighted case.Received: 21 November 2001, Accepted: 6 November 2003, Published online: 6 February 2004Research supported in part by Israel Ministry of Science. An extended abstract of this paper appeared in Proc. 19th ACM Symp. on Principles of Distributed Computing, July 2000.     

Excessive software development: Practices and penalties

This study focuses on the tendency to develop software excessively, above and beyond need or available development resources. The literature pays little attention to this issue, overlooking its crucial impact and penalties. Terms used in reference to excessive software development practices include over-requirement, over-specification, over-design, gold-plating, bells-and-whistles, feature creep, scope creep, requirements creep, featuritis, scope overload and over-scoping. Some of these terms share the same meaning, some overlap, some refer to the development phase, and some to the final system. Via a systematic literature search, we first demonstrate the poor state of research about excessive software development practices in the information systems and project management areas. Then, we suggest a framework consolidating the problems associated with excessive software development in three ‘beyond’ categories (beyond needs, beyond resources, beyond plans), describe and analyze their causes, consequences, boundaries and overlapping zones. Finally, we discuss the findings and present directions for future research.