Approximating good simultaneous Diophantine approximations is almost NP-hard
Authors:
- 1 January 1996
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 494-505
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Approximate solution of NP optimization problemsTheoretical Computer Science, 1995
- A parallel repetition theorem1995
- The complexity of greatest common divisor computationsLecture Notes in Computer Science, 1994
- Factoring integers and computing discrete logarithms via diophantine approximation1993
- Two-prover one-round proof systems1992
- Proof verification and hardness of approximation problems1992
- Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbersMathematics of Computation, 1988
- An application of simultaneous diophantine approximation in combinatorial optimizationCombinatorica, 1987
- The Computational Complexity of Simultaneous Diophantine Approximation ProblemsSIAM Journal on Computing, 1985
- On the difference between consecutive primesInventiones Mathematicae, 1979