The Computational Complexity of Simultaneous Diophantine Approximation Problems
From MaRDI portal
Publication:3676213
DOI10.1137/0214016zbMath0563.10025OpenAlexW2150529683MaRDI QIDQ3676213
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0214016
algorithmsinteger programmingNP-completenessNP-hardpublic key cryptographycomputational number theorybest simultaneous diophantine approximation denominatorshort vectors in integral lattices
Related Items
Algorithms to construct Minkowski reduced and Hermite reduced lattice bases ⋮ Simultaneous diophantine approximation of rationals by rationals ⋮ On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering ⋮ Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness ⋮ An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\) ⋮ Optimal length resolution refutations of difference constraint systems ⋮ QUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITS ⋮ Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ Short Presburger Arithmetic Is Hard ⋮ On a generalization of Horn constraint systems ⋮ Generating exact nonlinear ranking functions by symbolic-numeric hybrid method ⋮ Local and global relational consistency ⋮ Proving total correctness and generating preconditions for loop programs via symbolic-numeric computation methods ⋮ The convergence of the generalised Selmer algorithm ⋮ Exact safety verification of hybrid systems using sums-of-squares representation ⋮ Applications and efficient algorithms for integer programming problems on monotone constraints ⋮ Numeration and discrete dynamical systems ⋮ The Computational Complexity of Integer Programming with Alternations ⋮ The optimal LLL algorithm is still polynomial in fixed dimension. ⋮ Trichotomy for integer linear systems based on their sign patterns ⋮ Simultaneous approximation problems of \(p\)-adic numbers and \(p\)-adic knapsack cryptosystems -- Alice in \(p\)-adic numberland ⋮ Analyzing fractional Horn constraint systems ⋮ Splitting the Control Flow with Boolean Flags ⋮ NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations ⋮ A combinatorial algorithm for Horn programs ⋮ Preimage selective trapdoor function: how to repair an easy problem ⋮ Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients ⋮ The vehicle routing problem with coupled time windows ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The two variable per inequality abstract domain ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ Incremental closure for systems of two variables per inequality ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design ⋮ CRT-based fully homomorphic encryption over the integers ⋮ Tractability conditions for numeric CSPs ⋮ FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime ⋮ Recurrent properties of quasi-periodic dynamical systems with multiple frequencies of \(p\)-adic Liouville numbers ⋮ Selected Applications of LLL in Number Theory ⋮ On finite-precision representations of geometric objects ⋮ An Improved Tight Closure Algorithm for Integer Octagonal Constraints ⋮ Complexity and approximations for submodular minimization problems on two variables per inequality constraints ⋮ On memoryless provers and insincere verifiers ⋮ On the hardness of approximating shortest integer relations among rational numbers ⋮ A relation of primal--dual lattices and the complexity of shortest lattice vector problem ⋮ Incrementally closing octagons ⋮ Random lattices, threshold phenomena and efficient reduction algorithms. ⋮ A lattice-based public-key cryptosystem ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Signatures Through Approximate Representations by Quadratic Forms ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor ⋮ Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality ⋮ On the complexity of the dual method for maximum balanced flows ⋮ An efficient algorithm for a class of constraint satisfaction problems ⋮ Revisiting orthogonal lattice attacks on approximate common divisor problems