The Computational Complexity of Simultaneous Diophantine Approximation Problems

algorithms integer programming NP-completeness NP-hard public key cryptography computational number theory best simultaneous diophantine approximation denominator short vectors in integral lattices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (63)

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

This page was built for publication: The Computational Complexity of Simultaneous Diophantine Approximation Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3676213)