The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997). The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. Journal of Computer and System Sciences.

Type

Journal article

Intellectual base

Primary research

Year

1997

DOI

10.1006/jcss.1997.1472

Link

https://doi.org/10.1006/jcss.1997.1472

Cited by

1 citation across 1 artifact.

Domain-specific

• Minimum Relevant Variables in a Linear System
  • Complexity results manage expectations: poor worst-case approximability means that a universally reliable near-optimal polynomial algorithm is unlikely under the cited assumptions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:5078fce615ef · see in the full table