The Computational Complexity of Simultaneous Diophantine Approximation Problems

From MaRDI portal
Publication:3676213

DOI10.1137/0214016zbMath0563.10025OpenAlexW2150529683MaRDI QIDQ3676213

Jeffrey C. Lagarias

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




Related Items

Algorithms to construct Minkowski reduced and Hermite reduced lattice basesSimultaneous diophantine approximation of rationals by rationalsOn the complexity of an expanded Tarski's fixed point problem under the componentwise orderingWeakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctnessAn improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)Optimal length resolution refutations of difference constraint systemsQUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITSComplex Dimensions of Self-Similar Fractal Strings and Diophantine ApproximationThe Linear Complementarity Problems with a Few Variables per ConstraintShort Presburger Arithmetic Is HardOn a generalization of Horn constraint systemsGenerating exact nonlinear ranking functions by symbolic-numeric hybrid methodLocal and global relational consistencyProving total correctness and generating preconditions for loop programs via symbolic-numeric computation methodsThe convergence of the generalised Selmer algorithmExact safety verification of hybrid systems using sums-of-squares representationApplications and efficient algorithms for integer programming problems on monotone constraintsNumeration and discrete dynamical systemsThe Computational Complexity of Integer Programming with AlternationsThe optimal LLL algorithm is still polynomial in fixed dimension.Trichotomy for integer linear systems based on their sign patternsSimultaneous approximation problems of \(p\)-adic numbers and \(p\)-adic knapsack cryptosystems -- Alice in \(p\)-adic numberlandAnalyzing fractional Horn constraint systemsSplitting the Control Flow with Boolean FlagsNP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equationsA combinatorial algorithm for Horn programsPreimage selective trapdoor function: how to repair an easy problemExact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficientsThe vehicle routing problem with coupled time windowsConstraint Satisfaction Problems over Numeric DomainsThe two variable per inequality abstract domainA set partitioning reformulation of a school bus scheduling problemMonotonizing linear programs with up to two nonzeroes per columnIncremental closure for systems of two variables per inequalityTrichotomy for the reconfiguration problem of integer linear systemsUsing the Inhomogeneous Simultaneous Approximation Problem for Cryptographic DesignCRT-based fully homomorphic encryption over the integersTractability conditions for numeric CSPsFHE over the Integers: Decomposed and Batched in the Post-Quantum RegimeRecurrent properties of quasi-periodic dynamical systems with multiple frequencies of \(p\)-adic Liouville numbersSelected Applications of LLL in Number TheoryOn finite-precision representations of geometric objectsAn Improved Tight Closure Algorithm for Integer Octagonal ConstraintsComplexity and approximations for submodular minimization problems on two variables per inequality constraintsOn memoryless provers and insincere verifiersOn the hardness of approximating shortest integer relations among rational numbersA relation of primal--dual lattices and the complexity of shortest lattice vector problemIncrementally closing octagonsRandom lattices, threshold phenomena and efficient reduction algorithms.A lattice-based public-key cryptosystemSolving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximationsSignatures Through Approximate Representations by Quadratic FormsA new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factorTight bounds and 2-approximation algorithms for integer programs with two variables per inequalityOn the complexity of the dual method for maximum balanced flowsAn efficient algorithm for a class of constraint satisfaction problemsRevisiting orthogonal lattice attacks on approximate common divisor problems