An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division
Source: arxiv.org/abs/2609.29568
We record lower bounds for permanent circuits with valid division over characteristic zero, counting nonscalar multiplications and divisions while additions and scalar operations are free. Chapter 5 of OpenAI's Ten Advances supplies the block construction and critical-locus estimate; these, with the parameter choice made here and the classical bounds of Strassen and Baur-Strassen, give liminf as n tends to infinity of L_div(per_n)/(n^2 log_2 log_2 n) >= 1/12. Our finite-parameter refinement for matching-minor polynomials observes that the coefficient vector at deletion size h lies in a space…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.29568
curl -X POST /api/v1/records/arxiv/2609.29568/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.29568/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'