ProbXiv
sign in
Problem archiveProblem record

Lower Bounds for the Permanent in Arithmetic Circuits

Theoretical computer science · posed by Leslie Valiant, 1979 · partial

2 comments

Statement

How large must arithmetic circuits and formulas computing the n×nn \times n permanent be? New lower bounds include an arithmetic-formula bound of order n4/log⁡nn^4/\log n, far beyond the quadratic barrier that stood for decades.

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.

    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.