Mathematik
Refine
Year of publication
Document Type
- Article (111)
- Doctoral Thesis (76)
- Preprint (46)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (373) (remove)
Is part of the Bibliography
- no (373)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
- Moran model (3)
- coalescent (3)
- computational complexity (3)
- contraction method (3)
- point process (3)
- spike train (3)
- Algebraische Geometrie (2)
- Arithmetische Gruppe (2)
- Biographie (2)
- Brownian motion (2)
- Commitment Scheme (2)
- Frankfurt <Main> / Universität (2)
- Fuchsian groups (2)
- Fächerübergreifender Unterricht (2)
- Geometrie (2)
- Heat kernel (2)
- Hinterlegungsverfahren <Kryptologie> (2)
- Integral Geometry (2)
- Knapsack problem (2)
- Kombinatorische Optimierung (2)
- Krein space (2)
- Laplace operator on graphs (2)
- Lattice basis reduction (2)
- Martingal (2)
- Mathematiker (2)
- Musik (2)
- Oblivious Transfer (2)
- Perception (2)
- Quantum Zeno dynamics (2)
- San Jose (2)
- Semidefinite Programming (2)
- Shortest lattice vector problem (2)
- Stochastischer Prozess (2)
- Subset sum problem (2)
- Tropical geometry (2)
- Tropische Geometrie (2)
- Valuation Theory (2)
- Verzweigungsprozess (2)
- Vision (2)
- W*-dynamical system (2)
- X-Y model (2)
- Yule-Prozess (2)
- ancestral selection graph (2)
- binary search tree (2)
- collective intelligence (2)
- combinatorial optimization (2)
- complexity (2)
- duality (2)
- firing patterns (2)
- fixation probability (2)
- genealogy (2)
- level of difficulty (2)
- quantum spin systems (2)
- return to equilibrium (2)
- segments (2)
- task space (2)
- thought structure (2)
- Λ−coalescent (2)
- A-Discriminant (1)
- ADM1 (1)
- Abelian (1)
- Action potential (1)
- Actions in mathematical learning (1)
- Activity (1)
- Adaptive dynamics (1)
- Algebra (1)
- Algorithmus (1)
- Amoeba (1)
- Anaerobe Fermentation (1)
- Analyse von Algorithmen (1)
- Ancestral selection graph (1)
- Anisotropic Norm (1)
- Approximation (1)
- Approximation algorithm (1)
- Approximationsalgorithmus (1)
- Arbitrage (1)
- Assignment Problem (1)
- Asymptotically Even Nonlinearity (1)
- Ausreißer <Statistik> (1)
- Automorphismengruppe (1)
- Axon (1)
- Banach spaces (1)
- Bayesian Inference (1)
- Berkovich spaces (1)
- Binomialmodell (1)
- Binärsuchbaum (1)
- Black and Scholes Option Price theory (1)
- Black-Scholes (1)
- Blind Signature (1)
- Block Korkin—Zolotarev reduction (1)
- Blockplay (1)
- Bolthausen-Sznitman (1)
- Boolean Lattice (1)
- Bootstrap-Statistik (1)
- Boundary (1)
- Boundary Value Problems (1)
- Branch and Bound (1)
- Branching particle systems (1)
- Branching process approximation (1)
- Breaking knapsack cryptosystems (1)
- Bruhat-Tits-Gebäude (1)
- Burst (1)
- CAT(0)-Räume (1)
- CAT(0)-spaces (1)
- CIR-1 (1)
- Calderón problem (1)
- Cannings model (1)
- Catalan number (1)
- Cauchy-Anfangswertproblem (1)
- Cayley-Graph (1)
- China-Restaurant-Prozess (1)
- Chinese Remainder Theorem (1)
- Chinese restaurant process (1)
- Chinese-restaurant-process (1)
- Circuit (1)
- Closest Vector Problem (1)
- Coamoeba (1)
- Cognitive psychology (1)
- Commitment (1)
- Commitment schemes (1)
- Computational complexity (1)
- Concentration Inequality (1)
- Condensing (1)
- Containment (1)
- Contraction method (1)
- Datenbank (1)
- Datenstruktur (1)
- Degenerate Linear Part (1)
- Dehn (1)
- Derivate (1)
- Dessins d'enfants (1)
- Diagrams and mathematical learning (1)
- Dichte <Stochastik> (1)
- Digital and analogue materials (1)
- Digital trees (1)
- Dimension 2 (1)
- Directional selection (1)
- Dirichlet bound (1)
- Dirichlet random measure (1)
- Dirichletsche L-Reihe; Nullstelle (1)
- Discrete Logarithm (1)
- Diskrete Geometrie (1)
- Diskrete Mathematik (1)
- Diskreter Markov-Prozess (1)
- Diversity in trait space (1)
- Donkers theorem (1)
- Dopamine (1)
- Doplicher-Haag-Roberts Axiomatik; Algebraische Quantenfeldtheorie; Superauswahlregeln und -sektoren; Quantenstatistik; Zopfgruppenstatistik (1)
- Dormancy (1)
- Dosis-Wirkungs-Modellierung (1)
- Dreiecksgruppe (1)
- Dreiecksgruppen (1)
- Duality (1)
- Early Childhood (1)
- Einbettung <Mathematik> (1)
- Elektronische Unterschrift (1)
- Elementar- und Primarbereich (1)
- Endliche Präsentation (1)
- Endlichkeitseigenschaften (1)
- Energie-Modell (1)
- Error Bound (1)
- Erwartungswert (1)
- Evolutionary branching (1)
- Evolving Yield Curves in the Real-World Measures (1)
- Ewens sampling formula (1)
- Examples (1)
- Extended RMJBN Modell (1)
- FEM-BEM-coupling (1)
- FID model (1)
- FIND algorithm (1)
- Face (1)
- Face recognition (1)
- Factoring (1)
- Familie (1)
- Family (1)
- Feller branching with logistic growth (1)
- Finite element methods (1)
- Finitely many measurements (1)
- Fixation probability (1)
- Fixpunkt (1)
- Fractional Brownian Motion (1)
- Fractional Laplacian (1)
- Frühe Bildung (1)
- Fuchs-Gruppe (1)
- Fuchssche Gruppe ; Modulare Einbettung (1)
- Fuchssche Gruppen (1)
- Functions (1)
- Funktionenkegel (1)
- Funktionenkörper ; Arithmetische Gruppe ; Auflösbare Gruppe ; Endlichkeit (1)
- Galerkin Approximation (1)
- Galois group (1)
- Galois-Gruppe (1)
- Game Tree (1)
- Gaussian Random Field (1)
- Gaussian process (1)
- Gelfand-Shilov space (1)
- Gemischte Volumen (1)
- Genealogical construction (1)
- Genealogische Konstruktion (1)
- Genetischer Fingerabdruck (1)
- Genus One (1)
- Geometrische Gruppentheorie (1)
- Geometry (1)
- Gespräch (1)
- Gestaenge (1)
- Girsanov transform (1)
- Gitter <Mathematik> ; Basis <Mathematik> ; Reduktion ; Algorithmus ; Laufzeit ; L-unendlich-Norm ; Rucksackproblem ; Kryptosystem (1)
- Gitter <Mathematik> ; Basis <Mathematik> ; Reduktion ; Gauß-Algorithmus (1)
- Gram-Hadamard inequalities (1)
- Graphen (1)
- Grenzwertsatz (1)
- Griffiths–Engen–McCloskey distribution (1)
- Group dynamics (1)
- Große Abweichung (1)
- Großinvestor (1)
- Gruppendynamiken (1)
- Gruppentheorie (1)
- Hadamard's Three-Lines Theorem (1)
- Halbeinfache algebraische Gruppe (1)
- Handelman (1)
- Handlung (1)
- Harmoniebox (1)
- Heisenberg algebra (1)
- Hidden Markov models (1)
- Hintertür <Informatik> (1)
- Hodge bundle (1)
- Holzklötzchen (1)
- Hopf algebroids (1)
- Householder reflection (1)
- Hyperfunktion ; Asymptotische Entwicklung (1)
- Hypotrochoid (1)
- Identification (1)
- Immigration (1)
- Index at Infinity (1)
- Infrared singularity (1)
- Integer relations (1)
- Integraldarstellung (1)
- Interaction (1)
- Internet (1)
- Invariante (1)
- Inverse problems (1)
- Iteration (1)
- Jahr der Mathematik (1)
- Kettenbruchentwicklung ; Dimension n ; Diophantische Approximation (1)
- Kieferorthopädie (1)
- Klassifizierender Raum (1)
- Klebsiella pneumoniae (1)
- Knotenabstand (1)
- Knotentiefe (1)
- Koaleszent (1)
- Kochen-Specker theorem (1)
- Kollektivintelligenz (1)
- Kombinatorische Gruppen (1)
- Konforme Feldtheorie (1)
- Konstruktiver Beweis (1)
- Kontaktprozess (1)
- Kontraktionsmethode (1)
- Konzentrationsungleichung (1)
- Korkin—Zolotarev reduction (1)
- Kreuzkorrelation (1)
- Kryptosystem (1)
- Kullback-Leibler Informational Divergence (1)
- L^p bounds (1)
- L^p means (1)
- Label cover (1)
- Lanzeitverhalten (1)
- Laplace-Differentialgleichung (1)
- Large Deviation (1)
- Lattice Reduction (1)
- Leerverkauf (1)
- Lernen (1)
- Linear Filtering (1)
- Linear Preferential Attachment Trees (1)
- Linear-Implicit Scheme (1)
- Linkages (1)
- Loewner monotonicity and convexity (1)
- Logarithmic Laplacian (1)
- Long- Range Dependence (1)
- Long-Range Dependence (1)
- Long-time behaviour (1)
- Longitudinal Study (1)
- Lotka-Volterra system (1)
- Lovász Local Lemma (1)
- Low density subset sum algorithm (1)
- MINT-Bildung (1)
- Machine Learning (1)
- Malliavin calculus (1)
- Mallows model (1)
- Markov chain Monte Carlo Method (1)
- Markov chain imbedding technique (1)
- Markov model (1)
- Markov-Kette (1)
- Mathematical Giftedness (1)
- Mathematical Reasoning (1)
- Mathematical modelling (1)
- Mathematics Learning (1)
- Mathematische Bildung (1)
- Mathematische Modellierung (1)
- Max (1)
- McEliece (1)
- Mean Anisotropy (1)
- Message authentication (1)
- Methanogenese (1)
- Mixed Volumes (1)
- Modellierung (1)
- Modular Multiplication (1)
- Mooney faces (1)
- Morava K-theory (1)
- Mouse (1)
- Multi-Harmonie-Ansatz (1)
- Multiple lineare Regression (1)
- Multityp-Verzweigungsprozess mit Immigration (1)
- Multitype Branching with Immigration (1)
- NP-complete problems (1)
- NP-hard (1)
- NP-hardness (1)
- Nash-Gleichgewicht (1)
- Nelson-Siegel (1)
- Neural encoding (1)
- Neurophysiology (1)
- Neuroscience (1)
- Neurowissenschaft (1)
- Newton–Okounkov bodies (1)
- Non-Malleability (1)
- Noticeable Probability (1)
- Optimal Mean-Square Filter (1)
- Oracle Query (1)
- Parabolic SPDE (1)
- Parisi conjecture (1)
- Participation (1)
- Partizipation (1)
- Patientenbewertung (1)
- Pause (1)
- Permutation (1)
- Permutationsgruppen (1)
- Pfadeigenschaften (1)
- Phragmén-Lindelöf principle (1)
- Piecewise-constant coefficient (1)
- Poisson Process (1)
- Poisson boundary (1)
- Poisson-Prozess (1)
- Polyedrische Kombinatorik (1)
- Polymorphic evolution sequence (1)
- Polynomial Optimization (1)
- Pontrjagin space (1)
- Populationsdynamiken (1)
- Portfolios (1)
- Positivstellensatz (1)
- Potenzialtheorie (1)
- Prag <1999> (1)
- Preferential Attachment-Modelle (1)
- Private Information Retrieval (1)
- Probabilistic analysis of algorithms (1)
- Probabilistically checkable proofs (1)
- Probabilistische Analyse von Algorithmen (1)
- Probability distribution (1)
- Probability of fixation (1)
- Professionalisierung (1)
- Profil Likelihood (1)
- Projektionen (1)
- Public Key Cryptosystem (1)
- Public Parameter (1)
- Punktprozess (1)
- Pólya urn (1)
- Quadratic Residue (1)
- Quantenfeldtheorie ; Konforme Feldtheorie ; Algebraische Methode (1)
- Quantum Zeno Effect (1)
- Quantum Zeno effect (1)
- Quasi-Automorphismen (1)
- Quaternionenalgebra (1)
- Quickselect (1)
- RSA-Verschlüsselung (1)
- Radix sort (1)
- Random Oracle (1)
- Random Split Trees (1)
- Random String (1)
- Random environment (1)
- Random variables (1)
- Randomisieren (1)
- Ray-Knight representation (1)
- Reaction time (1)
- Reale vs. risikoneutrale Welt in der Finanzmathematik (1)
- Rechenzentrum (1)
- Rekursiver Algorithmus (1)
- Relaxation (1)
- Representation Problem (1)
- Research article (1)
- Riemann surfaces (1)
- Riemannsche Fläche (1)
- Riemannsche Flächen (1)
- Ringtheorie (1)
- Risikobewertung (1)
- Risikomanagement (1)
- Robustheit (1)
- Rückkopplungseffekt (1)
- S-arithmetic groups (1)
- SLLL-reduction (1)
- Sackgassen (1)
- San Francisco (1)
- Santa Barbara (1)
- Schizophrenia (1)
- Schwarz triangel functions (1)
- Schwinger model (1)
- Security (1)
- Security Parameter (1)
- Semidefinite Optimierung (1)
- Semidefinite Optimization (1)
- Semiotics according to C. S. Peirce (1)
- Sensory perception (1)
- Sensory processing (1)
- Sigma-Invariante (1)
- Sigma-invariant (1)
- Signalverarbeitung (1)
- Signature (1)
- Small Worlds (1)
- Small order expansion (1)
- Spectrahedra (1)
- Spiel (1)
- Spielbaum (1)
- Spielbaum-Suchverfahren (1)
- Stable reduction algorithm (1)
- State dependent branching rate (1)
- Stationarity (1)
- Stochastic Analysis of Square Zero Variation Processes (1)
- Stonesches Spektrum (1)
- Striatum (1)
- Strong Taylor Scheme (1)
- Stummel, Friedrich (1)
- Suchbaum (1)
- Suchoperation (1)
- Sudoku (1)
- Sum of Squares (1)
- Support (1)
- Symmetrie (1)
- Symmetrischer Raum (1)
- Symmetry (1)
- Sympatric speciation (1)
- Tail Bound (1)
- Tailschranke (1)
- Talk (1)
- Thorne Kishino Felsenstein model (1)
- Topic Model (1)
- Trapdoor (1)
- Trinomial (1)
- Tropical Geometry (1)
- Tropical Grassmannians (1)
- Tropical bases (1)
- Tropical varieties (1)
- Tropische Basen (1)
- Trotter's product formula (1)
- Turkish immigrants (1)
- Typ-In-Algebra (1)
- Typology (1)
- Türkisch (1)
- Uniform regularity (1)
- Uniform resource locators (1)
- Unterstützung (1)
- Valuation on functions (1)
- Varianz (1)
- Vertexoperator (1)
- Verzweigende Teilchensysteme (1)
- Virasoro-Algebra (1)
- Wahrscheinlichkeit (1)
- Wahrscheinlichkeitsverteilung (1)
- Wiener Index (1)
- Wiener index (1)
- Wiener-Index (1)
- Yule process (1)
- Yule-process (1)
- Zinsstrukturmodelle (1)
- Zinsänderungsrisiko (1)
- Zolotarev metric (1)
- Zolotarev-Metrik (1)
- Zopfgruppe ; Lineare Darstellung ; Kettengruppe ; Homologiegruppe ; Automorphismengruppe ; Kettenkomplex (1)
- Zufall (1)
- Zufallsgraph (1)
- Zufällige Umgebung (1)
- Zustandsabhängige Verzweigungsrate (1)
- Zweiphasen-Biogasreaktor (1)
- Zweistufen-Biogasreaktor (1)
- abelian differentials (1)
- abstract potential theory (1)
- algebraic curves (1)
- algebraic values (1)
- alpha-stable branching (1)
- ampleness (1)
- analysis of algorithms (1)
- anti-Zeno effect (1)
- argumentation (1)
- arithmetic ball quotients (1)
- arithmetic group (1)
- assignment problem (1)
- augmented and restricted base loci (1)
- autocorrelograms (1)
- bid-ask spread (1)
- bordism theory (1)
- branching processes (1)
- branching random walk in random medium (1)
- buildings (1)
- cancer cell dormancy (1)
- canonical divisors (1)
- catastrophe modeling (1)
- central limit theorem (1)
- chosen ciphertext attack (1)
- clique problem (1)
- colorabdity (1)
- colored graphs (1)
- compact Riemann surfaces (1)
- complex multiplication (1)
- composition (1)
- computational geometry (1)
- concurrent composition (1)
- condensing (1)
- confirmatory factory analysis (1)
- consensus (1)
- contact process (1)
- continued fraction algorithm (1)
- controlled homotopy (1)
- convexity (1)
- convolution quadrature (1)
- cooperative systems (1)
- cross correlation (1)
- cryptography (1)
- cycle structure of permutations (1)
- dead ends (1)
- degenerate semigroup (1)
- delay equation (1)
- depth of a nod (1)
- dessins d’enfants (1)
- difference sets (1)
- digital search tree (1)
- digital tools (1)
- discrete dynamical system (1)
- discrete logarithm (1)
- discrete logarithm (DL) (1)
- diskrete Mathematik (1)
- dose-resoponse modelling (1)
- doubly stochastic point process (1)
- eigenvalue (1)
- elastodynamic wave equation (1)
- emergence (1)
- endliche metrische Räume (1)
- error bounds (1)
- exponentiation (1)
- external branch (1)
- face inversion (1)
- face perception (1)
- fake projective planes (1)
- families of hash functions (1)
- feedback effect (1)
- finite resolution (1)
- finiteness-properties (1)
- flat surfaces (1)
- floating norms (1)
- floating point arithmetic (1)
- floating point errors (1)
- foliated Schwarz symmetry (1)
- forming a group (1)
- fractional Brownian motion (1)
- fractions of exponentiation (1)
- frühkindliche Erziehung (1)
- fuchsian group (1)
- functional limit theorem (1)
- functional limit theorems (1)
- fächerübergreifendes Lernen (1)
- generic algorithm (1)
- generic algorithms (1)
- generic complexity (1)
- generic group model (1)
- geometry (1)
- graph coloring (1)
- graph isomorphism (1)
- h-transform (1)
- hard bit (1)
- hardcore subsets (1)
- harmonic function (1)
- heavy tails (1)
- hidden Markov model (1)
- hierarchical mean-field limit (1)
- highly regular nearby points (1)
- hyperbolische Geometrie (1)
- hypergeometric functions (1)
- hypervariable region (1)
- höhere Momente (1)
- incremental schemes (1)
- indefinite inner product space (1)
- individual-based models (1)
- inner product (1)
- integer relation (1)
- integer vector (1)
- interacting particle Systems (1)
- interdisziplinäre Lehre (1)
- internal diffusion limited aggregation (1)
- internal path length (1)
- inverse coefficient problem, (1)
- iterated subsegments (1)
- key comparisons (1)
- kinetic fingerprint (1)
- knapsack cryptosystems (1)
- kontrollierte Homotopie (1)
- large deviations (1)
- large trader (1)
- latent variance (1)
- lattice basis reduction (1)
- lattices (1)
- leapfrog (1)
- length defect (1)
- limit order markets (1)
- local LLL-reduction (1)
- local LLLreduction (1)
- local coordinates (1)
- local randomness (1)
- local time (1)
- local time drift (1)
- logarithmic geometry (1)
- logical networks (1)
- lookdown construction (1)
- lower bounds (1)
- manifold and geodesic (1)
- market making (1)
- mathematical modeling (1)
- mathematical modelling (1)
- mathematics (1)
- measurement (1)
- mehrdimensionale Ausreißererkennung (1)
- message-passing algorithm (1)
- modelling (1)
- modular automorphism group (1)
- modular group (1)
- moduli spaces (1)
- multi-agents system (1)
- multi-drug treatment (1)
- multiharmony (1)
- multilevel branching (1)
- music (1)
- mutation parameter estimation (1)
- neuronal code (1)
- neuronaler Kode (1)
- nichtlineare stochastische Integration (1)
- non-archimedean geometry (1)
- non-autonomous dynamical systems (1)
- non-malleability (1)
- noncommutative ring spectra (1)
- nondetermmistlc Turing machines (1)
- nonlinear stochastic integration (1)
- numerical experiments (1)
- observable Funktion (1)
- one-more decryption attack (1)
- one-way function (1)
- one-way functions (1)
- operator algebra (1)
- optimal transport (1)
- pair HMM (1)
- parameter dependent semimartingales (1)
- parameterabhängige Semimartingale (1)
- partial match queries (1)
- path properties (1)
- perceptual closure (1)
- permutation groups (1)
- phage (1)
- phage therapy (1)
- phase coding (1)
- phase transitions (1)
- platonischer Körper (1)
- poisson process (1)
- polynomial random number generator (1)
- population dynamics (1)
- portfolio optimization (1)
- positivity of line bundles (1)
- preferential attachment (1)
- preferential attachment models (1)
- probabilistic analysis of algorithms (1)
- probability (1)
- probability metric (1)
- professional development (1)
- profile likelihood (1)
- projections (1)
- projective planes (1)
- q-binomial theorem (1)
- quantum field theory (1)
- quasi-automorphisms (1)
- quaternion algebra (1)
- quincunx (1)
- random assignment problem (1)
- random environment (1)
- random function generator (1)
- random graphs (1)
- random measures (1)
- random media (1)
- random metric (1)
- random move (1)
- random number generator (1)
- random oracle model (1)
- random partition (1)
- random recursive tree (1)
- random rekursiv tree (1)
- random trees (1)
- random walks (1)
- raum-zeitliche Muster (1)
- reactant-catalyst systems (1)
- recursive distributional equation (1)
- reguläre Parkettierung (1)
- resistance (1)
- resistance mutation (1)
- reversibility (1)
- riemann surfaces (1)
- risk assessment (1)
- risk theory (1)
- rotating plane method (1)
- rough paths theory (1)
- satlsfiablhty (1)
- scaling (1)
- search operation (1)
- searchtrees (1)
- secure bit (1)
- security analysis of protocols (1)
- security of data (1)
- self-organizing groups (1)
- self-organizing groups; population dynamics; collective intelligence; forming groups; metric on finite sets (1)
- semidefinite optimization (1)
- sequence alignment (1)
- set-valued pullback attractors (1)
- shadow price (1)
- short integer relation (1)
- shortest lattice vector (1)
- signature size (1)
- signed ElGamal encryption (1)
- simultaneous diophantine approximations (1)
- simultaneous security of bits (1)
- single block replacement (1)
- small worlds (1)
- spatio-temporal patterns (1)
- split tree (1)
- statistic analysis (1)
- statistical alignment (1)
- statistische Analyse (1)
- statistischer Test (1)
- stoch. Analyse von Algorithmen (1)
- stochastic filtering (1)
- stochastic modeling (1)
- stochastic population dynamics (1)
- stochastische Prozesse (1)
- strong transience (1)
- subgroup growth (1)
- subset sum problems (1)
- substitution attacks (1)
- sum of squared factor loadings (1)
- switching systems (1)
- synergistic interaction (1)
- therapy evasion (1)
- topological entropy (1)
- trading strategies (1)
- transcendence (1)
- transversal learning (1)
- treatment protocol design (1)
- treatment success (1)
- triangle group (1)
- triangle groups (1)
- tropical geometry (1)
- tropical universal Jacobian (1)
- tropicalization (1)
- universal compactified Jacobian (1)
- urn model (1)
- von Neumann algebra (1)
- von Neumann algebras (1)
- von Neumann-Algebra (1)
- weak convergence (1)
- zufälliger Algorithmus (1)
- zufälliger rekursiver Baum (1)
- zufälliges Assignment Problem (1)
- Λ-coalescent (1)
- σ-field (1)
Institute
- Mathematik (373) (remove)
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 ...
Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time O(npoly(log n)), the ℓinfinity-shortest integer relation for a given vector x small epsilon, Greek Qn cannot be approximated in polynomial time within a factor of 2log0.5 − small gamma, Greekn, where small gamma, Greek is an arbitrarily small positive constant. This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known L3-algorithm approximates for a vector x small epsilon, Greek Qn the ℓ2-shortest integer relation within a factor of 2n/2 in polynomial time. Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems. The same inapproximability result is valid for finding the ℓinfinity-shortest integer solution for a homogeneous linear system of equations over Q.
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
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.
We propose a fast variant of the Gaussian algorithm for the reduction of two dimensional lattices for the l1-, l2- and l-infinite- norm. The algorithm runs in at most O(nM(B) logB) bit operations for the l-infinite- norm and in O(n log n M(B) logB) bit operations for the l1 and l2 norm on input vectors a, b 2 ZZn with norm at most 2B where M(B) is a time bound for B-bit integer multiplication. This generalizes Schönhages monotone Algorithm [Sch91] to the centered case and to various norms.
We present an efficient variant of LLL-reduction of lattice bases in the sense of Lenstra, Lenstra, Lov´asz [LLL82]. We organize LLL-reduction in segments of size k. Local LLL-reduction of segments is done using local coordinates of dimension 2k. Strong segment LLL-reduction yields bases of the same quality as LLL-reduction but the reduction is n-times faster for lattices of dimension n. We extend segment LLL-reduction to iterated subsegments. The resulting reduction algorithm runs in O(n3 log n) arithmetic steps for integer lattices of dimension n with basis vectors of length 2O(n), compared to O(n5) steps for LLL-reduction.