On the hardness of approximating shortest integer relations among rational numbers

DOI10.1016/S0304-3975(97)00118-7zbMath0912.68062OpenAlexW2053570496MaRDI QIDQ1274930

Jean-Pierre Seifert, Carsten Rössner

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00118-7

zbMATH Keywords

computational complexityapproximation algorithmNP-hardprobabilistically checkable proofslabel cover2-prover 1-round interactive proof systemsinteger relations

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (1)

An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• On the limits of computations with the floor function
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• Polynomial-Time Aggregation of Integer Programming Problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers
• On the hardness of approximating minimization problems

This page was built for publication: On the hardness of approximating shortest integer relations among rational numbers