Refine
Year of publication
- 1993 (5) (remove)
Document Type
- Preprint (5) (remove)
Language
- English (5) (remove)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5) (remove)
Keywords
Institute
- Informatik (3)
- Mathematik (3)
- Physik (1)
We report on improved practical algorithms for lattice basis reduction. We propose a practical floating point version of theL3-algorithm of Lenstra, Lenstra, Lovász (1982). We present a variant of theL3-algorithm with "deep insertions" and a practical algorithm for block Korkin—Zolotarev reduction, a concept introduced by Schnorr (1987). Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 66 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC1 + computer.
We call a distribution on n bit strings (", e) locally random, if for every choice of e · n positions the induced distribution on e bit strings is in the L1 norm at most " away from the uniform distribution on e bit strings. We establish local randomness in polynomial random number generators (RNG) that are candidate one way functions. Let N be a squarefree integer and let f1, . . . , f be polynomials with coe±- cients in ZZN = ZZ/NZZ. We study the RNG that stretches a random x 2 ZZN into the sequence of least significant bits of f1(x), . . . , f(x). We show that this RNG provides local randomness if for every prime divisor p of N the polynomials f1, . . . , f are linearly independent modulo the subspace of polynomials of degree · 1 in ZZp[x]. We also establish local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman (1979). The proofs of our results rely on upper bounds for exponential sums.
Thirty-one years ago Tsu-lin Mei (1961) argued against the traditional doctrine that saw the subject-predicate distinction in grammar as parallel to the particular- universal distinction in logic, as he said it was a reflex of an Indo-European bias, and could not be valid, as ‘Chinese ... does not admit a distinction into subject and predicate’ (p. 153). This has not stopped linguists working on Chinese from attempting to define ‘subject’ (and ‘object’) in Chinese. Though a number of linguists have lamented the difficulties in trying to define these concepts for Chinese (see below), most work done on Chinese still assumes that Chinese must have the same grammatical features as Indo-European, such as having a subject and a direct object, though no attempt is made to justify that view. This paper challenges that view and argues that there has been no grammaticalization of syntactic functions in Chinese. The correct assignment of semantic roles to the constituents of a discourse is done by the listener on the basis of the discourse structure and pragmatics (information flow, inference, relevance, and real world knowledge) (cf. Li & Thompson 1978, 1979; LaPolla 1990).
We present a RQMD calculation of antiproton yields and their momentum distribution in Ne + NaF collisions at 2 GeV/u. The antiprotons can be produced below threshold due to multi-step excitations for which meson-baryon interactions play a considerable role. In this system the annihilation probability for an initially produced antiproton is predicted to be about 65%.