Publication:4375817
From MaRDI portal
zbMath0896.11051MaRDI QIDQ4375817
Carsten Rössner, Jean-Pierre Seifert
Publication date: 1 October 1998
computational complexity; approximation algorithm; NP-hard; probabilistically checkable proofs; 2-prover 1-round interactive proof-systems; good diophantine approximation
68Q25: Analysis of algorithms and problem complexity
11Y16: Number-theoretic algorithms; complexity
68W10: Parallel algorithms in computer science
Related Items
An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\), Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design