Mathematik
Refine
Year of publication
Document Type
- Report (22) (remove)
Has Fulltext
- yes (22)
Is part of the Bibliography
- no (22)
Keywords
- LLL-reduction (2)
- segments (2)
- Energie-Modell (1)
- Group dynamics (1)
- Gruppendynamiken (1)
- Householder reflection (1)
- Kollektivintelligenz (1)
- Populationsdynamiken (1)
- SLLL-reduction (1)
- Schwarz triangel functions (1)
Institute
- Mathematik (22)
- Informatik (12)
We study the following problem: given x element Rn either find a short integer relation m element Zn, so that =0 holds for the inner product <.,.>, or prove that no short integer relation exists for x. Hastad, Just Lagarias and Schnorr (1989) give a polynomial time algorithm for the problem. We present a stable variation of the HJLS--algorithm that preserves lower bounds on lambda(x) for infinitesimal changes of x. Given x \in {\RR}^n and \alpha \in \NN this algorithm finds a nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no very short relation exists for points \bar{x} within half the x'--distance from x. On the other hand if x'=x then m is, up to a factor 2^{n/2}, a shortest integer relation for \mbox{x.} Our algorithm uses, for arbitrary real input x, at most \mbox{O(n^4(n+\log \alpha))} many arithmetical operations on real numbers. If x is rational the algorithm operates on integers having at most \mbox{O(n^5+n^3 (\log \alpha)^2 + \log (\|q x\|^2))} many bits where q is the common denominator for x.
We consider Schwarz maps for triangles whose angles are rather general rational multiples of pi. Under which conditions can they have algebraic values at algebraic arguments? The answer is based mainly on considerations of complex multiplication of certain Prym varieties in Jacobians of hypergeometric curves. The paper can serve as an introduction to transcendence techniques for hypergeometric functions, but contains also new results and examples.
Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
We generalize the concept of block reduction for lattice bases from l2-norm to arbitrary norms. This extends the results of Schnorr. We give algorithms for block reduction and apply the resulting enumeration concept to solve subset sum problems. The deterministic algorithm solves all subset sum problems. For up to 66 weights it needs in average less then two hours on a HP 715/50 under HP-UX 9.05.
Condensing phenomena for systems biology, ecology and sociology present in real life different complex behaviors. Based on local interaction between agents, we present another result of the Energy-based model presented by [20]. We involve an additional condition providing the total condensing (also called consensus) of a discrete positive measure. Key words: Condensing; consensus; random move; self-organizing groups; collective intelligence; stochastic modeling. AMS Subject Classifications: 81T80; 93A30; 37M05; 68U20
Bei der Untersuchung des Langzeitverhaltens von Verzweigungsprozessen und räumlich verzweigenden Populationen ist die Betrachtung von Stammbäumen zunehmend in den Vordergrund gerückt. Probabilistische Methoden haben die in der Theorie vorherrschenden analytischen Techniken ergänzt und zu wesentlichen neuen Einsichten geführt. Die vorliegende Synopse diskutiert eine Auswahl meiner Veröffentlichungen der letzten Jahre. Den Arbeiten ist gemeinsam, dass durch das Studium der genealogischen Verhältnisse in der Population Aussagen über deren Langzeitverhalten gewonnen werden konnten. Zwei dieser Arbeiten behandeln den klassischen Galton-Watson Prozess. Eine weitere Arbeit befasst sich mit Verzweigungsprozessen in zufälliger Umgebung, sie ist technische wesentlich anspruchsvoller. Die vierte der hier besprochenen Arbeiten beschäftigt sich mit dem Wählermodell, einem der Prototypen interagierender Teilchensysteme.
Local interactions between particles of a collection causes all particles to reorganize in new positions. The purpose of this paper is to construct an energy-based model of self-organizing subgroups, which describes the behavior of singular local moves of a particle. The present paper extends the Hegselmann-Krause model on consensus dynamics, where agents simultaneously move to the barycenter of all agents in an epsilon neighborhood. The Energy-based model presented here is analyzed and simulated on finite metric space. AMS Subject Classifications:81T80; 93A30; 37M05; 68U20