Transposon mutagenesis, in combination with parallel sequencing, is becoming a powerful tool for en-masse mutant analysis. A probability generating function was used to explain observed miniHimar transposon insertion patterns, and gene essentiality calls were made by transposon insertion frequency analysis (TIFA). TIFA incorporated the observed genome and sequence motif bias of the miniHimar transposon. The gene essentiality calls were compared to: 1) previous genome-wide direct gene-essentiality assignments; and, 2) flux balance analysis (FBA) predictions from an existing genome-scale metabolic model of Shewanella oneidensis MR-1. A three-way comparison between FBA, TIFA, and the direct essentiality calls was made to validate the TIFA approach. The refinement in the interpretation of observed transposon insertions demonstrated that genes without insertions are not necessarily essential, and that genes that contain insertions are not always nonessential. The TIFA calls were in reasonable agreement with direct essentiality calls for S. oneidensis, but agreed more closely with E. coli essentiality calls for orthologs. The TIFA gene essentiality calls were in good agreement with the MR-1 FBA essentiality predictions, and the agreement between TIFA and FBA predictions was substantially better than between the FBA and the direct gene essentiality predictions.

This paper presents a new economic approach for studying competition and innovation in a complex and highly interactive system of network providers, users, and suppliers of digital goods and services (i.e., service providers). It employs Cournot and Bertrand games to model competition among service providers and network providers, respectively, and develops a novel unified model to capture the interaction and competition among these players in a "service-oriented" Internet. Incentives for service and network innovation are studied in this model.

No abstract available.

This note discusses briefly some questions on economics of privacy, especially the relation of privacy to price discrimination, as well as relevant developments in ecommerce and ordinary commerce. Various open questions that call for further research are discussed. In particular, while much interesting theoretical research has been done, and a small number of informative laboratory experiments have been carried out, much more work would be desirable, especially in some areas of behavioral economics, and there is a great unmet need for active monitoring of the marketplace.

No abstract available.

The rapid erosion of privacy poses numerous puzzles. Why is it occurring, and why do people care about it? This paper proposes an explanation for many of these puzzles in terms of the increasing importance of price discrimination. Privacy appears to be declining largely in order to facilitate difierential pricing, which ofiers greater social and economic gains than auctions or shopping agents. The thesis of this paper is that what really motivates commercial organizations (even though they often do not realize it clearly themselves) is the growing incentive to price discriminate, coupled with the increasing ability to price discriminate. It is the same incentive that has led to the airline yield management system, with a complex and constantly changing array of prices. It is also the same incentive that led railroads to invent a variety of price and quality difierentiation schemes in the 19th century. Privacy intrusions serve to provide the information that allows sellers to determine buyers' willingness to pay. They also allow monitoring of usage, to ensure that arbitrage is not used to bypass discriminatory pricing.Economically, price discrimination is usually regarded as desirable, since it often increases the efficiency of the economy. That is why it is frequently promoted by governments, either through explicit mandates or through indirect means. On the other hand, price discrimination often arouses strong opposition from the public.There is no easy resolution to the conflict between sellers; incentives to price discriminate and buyers' resistance to such measures. The continuing tension between these two factors will have important consequences for the nature of the economy. It will also determine which technologies will be adopted widely. Governments will likely play an increasing role in controlling pricing, although their roles will continue to be ambiguous. Sellers are likely to rely to an even greater extent on techniques such as bundling that will allow them to extract more consumer surplus and also to conceal the extent of price discrimination. Micropayments and auctions are likely to play a smaller role than is often expected. In general, because of strong conflicting pressures, privacy is likely to prove an intractable problem that will be prominent on the the public agenda for the foreseeable future.

A simple approach, called PMP (Paris Metro Pricing), is suggested for providing differentiated services in packet networks such as the Internet.It is to partition a network into several logically separate channels, each of which would treat all packets equally on a best effort basis.There would be no formal guarantees of quality of service.These channels svould differ only in the prices paid for using them.Channels with higher prices would attract less traffic, and thereby provide better service.Price would be the primary tool of traffic management.PMP is the simplest differentiated services solution.It is designed to accommodate user preferences at the cost of sacrificing some of the utilization efficiency of the network.

An urn containsm balls of value -1 and p balls of value +1. At each turn a ball is drawn randomly, without replacement, and the player decides before the draw whether or not to accept the ball, i.e., the bet where the payoff is the value of the ball. The process continues until all m+p balls are drawn. Let $\overline{V}(m,p)$ denote the value of this acceptance $(m,p)$ urn problem under an optimal acceptance policy. In this paper, we first derive an exact closed form for \overline{V}(m,p) and then study its properties and asymptotic behavior. We also compare this acceptance (m,p) urn problem with the original (m,p)$ urn problem which was introduced by Shepp [Ann. Math. Statist., 40 (1969), pp. 993--1010]. Finally, we briefly discuss some applications of this acceptance (m,p) urn problem and introduce a Bayesian approach to this optimal stopping problem. Some numerical illustrations are also provided.

We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely relate

Article Search for the maximum of a random walk Share on Author: Andrew M. Odlyzko AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 336–345https://doi.org/10.1145/195058.195182Online:23 May 1994Publication History 0citation366DownloadsMetricsTotal Citations0Total Downloads366Last 12 Months2Last 6 weeks1 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

Abstract We propose a new routing strategy for the KYKLOS II multiprocessor interconnection network that achieves minimum distance for the path between any two processors. For KYKLOS II with 2n processors, the average distance is shorter than those of previous routing strategies by approximately 2 log2n. The traffic density, a measure of traffic concentration, is better than previous strategies for up to 2000 processors, though asymptotically inferior to a strategy proposed by Jenevein and Menezes. © 1994 by John Wiley & Sons, Inc.

Article Free Access Share on Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis Authors: Dima Yu. Grigoriev View Profile , Marek Karpinski View Profile , Andrew M. Odlyzko View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 117–122https://doi.org/10.1145/143242.143287Online:01 August 1992Publication History 5citation182DownloadsMetricsTotal Citations5Total Downloads182Last 12 Months2Last 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 SiteeReaderPDF

This work presents a class of methods by which one can translate, on a term-by-term basis, an asymptotic expansion of a function around a dominant singularity into a corresponding asymptotic expansion for the Taylor coefficients of the function. This approach is based on contour integration using Cauchy’s formula and Hankel-like contours. It constitutes an alternative to either Darboux’s method or Tauberian theorems that appears to be well suited to combinatorial enumerations, and a few applications in this area are outlined.

Cryptosystems are tested by subjecting them to cryptanalytic attacks by experts. Most of the cryptosystems that have been publicly proposed in the last decade have been broken. Some of the attacks that have been used are outlined, and some of the basic tools available to the cryptanalyst are explained. Attacks on the knapsack cryptosystems, congruential generators, and a variety of two key secrecy and signature schemes are discussed. There is also a brief discussion of the status of the security of cryptosystems for which there is no known feasible attack, such as the RSA, discrete exponentiation, and DES cryptosystems.>

For n>0, d>or=0, n identical to d (mod 2), let K(n, d) denote the minimal cardinality of a family V of +or-1 vectors of dimension n, such that for any +or-1 vector w of dimension n there is a v in V such that mod v-w mod>

The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n , may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. Each algorithm may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.

An algorithm of Beyer and Hedetniemi [SIAM J. Comput., 9 (1980), pp. 706–712] for generating rooted unlabeled trees is extended to generate unlabeled free trees. All the nonisomorphic trees of a given size are generated, without repetition, in time proportional to the number of trees.

It is shown that for each integerb \geq 1infinitely many optimum cyclicb-burst-correcting codes exist, i.e., codes whose lengthn, redundancyr, and burst-correcting capabilityb, satisfyn = 2^{r-b+1} - 1. Some optimum codes forb = 3, 4, and5are also studied in detail.

Article Simple, efficient asynchronous parallel algorithms for maximization Share on Authors: Albert G. Greenberg AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Boris D. Lubachevsky AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Andrew M. Odlyzko AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 300–308https://doi.org/10.1145/323596.323625Online:01 August 1985Publication History 1citation122DownloadsMetricsTotal Citations1Total Downloads122Last 12 Months2Last 6 weeks1 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

The subset sum problem is to decide whether or not the 0-l integer programming problem Σ n i=l a i x i = M , ∀I , x I = 0 or 1, has a solution, where the a i and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public-key cryptosystems of knapsack type. An algorithm is proposed that searches for a solution when given an instance of the subset sum problem. This algorithm always halts in polynomial time but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz to attempt to find v. The performance of the proposed algorithm is analyzed. Let the density d of a subset sum problem be defined by d = n /log 2 (max i a i ). Then for “almost all” problems of density d < 0.645, the vector v we searched for is the shortest nonzero vector in the lattice. For “almost all” problems of density d < 1/ n , it is proved that the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d < d c ( n ), where d c ( n ) is a cutoff value that is substantially larger than 1/ n . This method gives a polynomial time attack on knapsack public-key cryptosystems that can be expected to break them if they transmit information at rates below d c ( n ), as n → ∞.

The basic Merkle-Hellman additive trapdoor knapsack public-key cryptosystem was recently shown to be insecure, and attacks have also been developed on stronger variants of it, such as the Graham-Shamir system and the iterated knapsack cryptosystem. It is shown that some simple variants of another Merkle-Hellman system, the multiplicative knapsack cryptosystem, are insecure. It is also shown that the Shamir fast signature scheme can be broken quickly. Similar attacks can also be used to break the Schöbi-Massey authentication scheme. These attacks have not been rigorously proved to succeed, but heuristic arguments and empirical evidence indicate that they work on systems of practical size.

The subset sum problem is to decide whether or not the 0-1 integer programming problem Σi=1n aixi = M; all xi = 0 or 1; has a solution, where the ai and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public key cryptosystems of knapsack type. We propose an algorithm which when given an instance of the subset sum problem searches for a solution. This algorithm always halts in polynomial time, but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász to attempt to find v. We analyze the performance of the proposed algorithm. Let the density d of a subset sum problem be defined by d=n/log2(maxi ai). Then for "almost all" problems of density d ≪ .645 the vector v we are searching for is the shortest nonzero vector in the lattice. We prove that for "almost all" problems of density d ≪ 1/n the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d ≪ dc (n), where dc (n) is a cutoff value that is substantially larger than 1/n. This method gives a polynomial time attack on knapsack public key cryptosystems that can be expected to break them if they transmit information at rates below dc (n), as n → ∞.

It is shown that under certain hypotheses, irreducibility testing and factorization of polynomials with integer coefficients are polynomial time reducible to primality testing and factorization of integers, respectively. Combined with recently discovered fast primality tests, this yields an almost polynomial time irreducibility algorithm. The assertions of irreducibility produced by this algorithm are always certain and yield short proofs of irreducibility.

The average height of a binary tree With n internal nodes is shown to be asymptotic to 2√πn. More generally, the average height of a tree in a simple family S with n nodes is asymptotic to c(S) √πn where c(S) is a number (usually algebraic) which can be explicitly determined from S. These results are achieved by means of a detailed singularity analysis of corresponding generating functions.

The Boyer-Moore algorithm searches for all occurrences of a specified string, the pattern, in another string, the text. We study the combinatorial structure of periodic strings and use these results to derive a new proof of the linearity of the Boyer-Moore algorithm in the worst case. Our proof reduces the previously best known bound of $7n$ to $4n$, where n is the length of the text.

Coefficient inaccuracy in FIR filters is known to degrade the frequency response particularly in stopband regions. The magnitude of the stopband degradation increases with the number of stages N, the length of the impulse response. A widely used formula for the error in frequency response is proportional to\sqrt{N}. Recently, we have found that for random additive coefficient errors with variance σ2, the maximum error in frequency response for large N is given by\sigma\sqrt{N\logN}. This result is applied to an empirical formula relating the minimum number of stages, N, to specified lowpass filter performance parameters. The results lead to absolute bounds on attainable stopband rejection for band-select FIR filters. The realization of transversal filters with charge-coupled devices (CCD's) is particularly relevant to this study.

Improved bounds forA(n,d), the maximum number of codewords in a (linear or nonlinear) binary code of word lengthnand minimum distanced, and forA(n,d,w), the maximum number of binary vectors of lengthn, distanced, and constant weightwin the rangen \leq 24andd \leq 10are presented. Some of the new values areA

The Boyer-Moore algorithm searches for all occurrences of a specified string, the pattern, in another string, the text. We study the combinatorial structure of periodic strings and use these results to derive a new proof of the linearity of the Boyer-Moore algorithm in the worst case. Our proof reduces the previously best known bound of $7n$ to $4n$, where n is the length of the text.

LetF = GF(2), andFG = F[x]/(x^n + 1). FGis the residue class ring of polynomials modx^n + 1. An element ofFGis represented by a polynomial of degree at mostn - 1\begin{equation} c(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1} \end{equation} with coefficients inF. It may also be represented by a polynomial \begin{equation} g(z) = \sum_{j=0}^{n-1} c(\alpha^j)z^j \end{equation} with coefficients inGF(2^m), wheremis the least integer such thatndivides2^m - 1, and\alphais a primitiventh root of unity. Mattson and Solomon [1] introduced this representation in 1961. The new theorem states that \begin{equation} zg'(z) = \frac{g(z)(g(z) + 1)}{z^n +l}. \end{equation} A typical application of this result is as follows. Letn = 2^m - 1, wherem \equiv 1mod 2. Let\mathcal{A}_1be the cyclic code of dimension 2m defined by the property that its check polynomial has zeros\alpha ^{-j}, wherej = 1,2,\cdots,2^{m-1}andj = l,2l,\cdots,2^{m-1} l, l = 2^i + 1. If(i,m) = 1this code has just three nonzero weights, namely,2^{m-1} \pm 2^{(m-1)/2}and2^{m-1}. The weight distribution can then be obtained from the MacWflliams identifies. These conditions are satisfied forn = 31, l = 3,5; n = 127,l= 3,5,9;n = 511, l = 3,5,17; etc. Thus forn= 127, for example, the three codes\mathcal{A}_3,\mathcal{A}_5, \mathcal{A}_9have the same weight distribution, although they are probably not equivalent in the usual sense.