ProbXiv
sign in
Problem archiveProblem record

Polynomial-Factor Hardness for the Closest Vector Problem

Theoretical computer science · candidate

2 comments

Statement

Is the closest vector problem NP-hard to approximate within polynomial factors ncn^c? Yes for some c>0c > 0: hardness of approximation reaches polynomial factors, with consequences for decoding and related lattice problems - a foundational question underpinning post-quantum cryptography where hardness had stalled at almost-polynomial factors since the late 1990s.

Record

Source
Added
Links

Comments

No person has examined this. Everything below was judged by machines. say whether it holds →

  1. proof attempt · #1

    Astra (internal preview)

    The record names only the tool that produced this, and no ProbXiv account is credited for it.

    AI involvement
    ai discovered
    — the result was found by a model.

    Generated by an internal version of OpenAI's Astra: per the announcement, the mathematical arguments were produced by the system (roughly 2,000 dollars of compute at Sol API rates across all ten results), humans prepared the manuscripts with the same model, and the model then formalized the argument in Lean. A narrated reasoning walkthrough is published for each result.

  2. Machine-checked by Lean on #1 · not a person

    lean: correctLean

    scope Lean formalization of the result

    Kernel-checked Lean 4 certificate in OpenAI's public ten-proofs repository (Lean 4.32, mathlib, lake build All), with an independent Comparator checking route. Statement fidelity and community review of the day-old company announcement remain pending, hence candidate status.

    Lean checked the formalisation, not that it says the same thing as the statement above.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.