The Computational Complexity of Simultaneous Diophantine Approximation Problems
From MaRDI portal
Recommendations
Cited in
(72)- Algorithms to construct Minkowski reduced and Hermite reduced lattice bases
- Simultaneous diophantine approximation of rationals by rationals
- 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
- 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
- Local and global relational consistency
- The optimal LLL algorithm is still polynomial in fixed dimension.
- Monotonizing linear programs with up to two nonzeroes per column
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Effective simultaneous approximability of reals.
- An efficient algorithm for a class of constraint satisfaction problems
- On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
- 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
- Preimage selective trapdoor function: how to repair an easy problem
- Incremental closure for systems of two variables per inequality
- CRT-based fully homomorphic encryption over the integers
- Complexity and approximations for submodular minimization problems on two variables per inequality constraints
- Random lattices, threshold phenomena and efficient reduction algorithms.
- A lattice-based public-key cryptosystem
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
- Revisiting orthogonal lattice attacks on approximate common divisor problems
- Analyzing fractional Horn constraint systems
- Recurrent properties of quasi-periodic dynamical systems with multiple frequencies of \(p\)-adic Liouville numbers
- Incrementally closing octagons
- On a generalization of Horn constraint systems
- Proving total correctness and generating preconditions for loop programs via symbolic-numeric computation methods
- A combinatorial algorithm for Horn programs
- Using the inhomogeneous simultaneous approximation problem for cryptographic design
- The Linear Complementarity Problems with a Few Variables per Constraint
- Splitting the Control Flow with Boolean Flags
- New Hardness Results for Diophantine Approximation
- On memoryless provers and insincere verifiers
- Generating exact nonlinear ranking functions by symbolic-numeric hybrid method
- Numeration and discrete dynamical systems
- scientific article; zbMATH DE number 599115 (Why is no real title available?)
- scientific article; zbMATH DE number 1113848 (Why is no real title available?)
- scientific article; zbMATH DE number 1114048 (Why is no real title available?)
- Complex Dimensions of Self-Similar Fractal Strings and Diophantine Approximation
- Constraint satisfaction problems over numeric domains
- Signatures through approximate representations by quadratic forms
- Short Presburger Arithmetic Is Hard
- Distributed computing of simultaneous Diophantine approximation problems
- The computational complexity of integer programming with alternations
- The Complexity of the Diagonal Problem for Recursion Schemes
- Efficient computing of \(n\)-dimensional simultaneous Diophantine approximation problems
- Selected applications of LLL in number theory
- QUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITS
- An Improved Tight Closure Algorithm for Integer Octagonal Constraints
- FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime
- On finite-precision representations of geometric objects
- Applications and efficient algorithms for integer programming problems on monotone constraints
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- The two variable per inequality abstract domain
- A set partitioning reformulation of a school bus scheduling problem
- 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
- Tractability conditions for numeric CSPs
- Parameterized algorithms for block-structured integer programs with large entries
- On the approximation of quasiperiodic functions with Diophantine frequencies by periodic functions
- Dichotomy for the Hausdorff dimension of non-ergodic directions on translation surfaces
- Leakage-resilience of Shamir's secret sharing: identifying secure evaluation places
- A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
- The complexity of almost linear diophantine problems
- 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
- The convergence of the generalised Selmer algorithm
- Exact safety verification of hybrid systems using sums-of-squares representation
- Trichotomy for integer linear systems based on their sign patterns
- The vehicle routing problem with coupled time windows
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)
