Pseudo-solutions of polynomial systems and the lower bound problem for $\mbox{AC}^0[p]$-Frege systems
The problem to establish a lower bound for $\mbox{AC}^0[p]$-Frege refutations of a system of polynomial equations over ${\bf F}_p$ was in K. (2024) reduced to the existence of a pseudo-solution (a notion defined there) for the system. Here we reduce this further, for the system expressing the negation of the PHP, to a property of search trees querying values of linear maps on the vector space of low degree polynomials over ${\bf F}_p$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35927
curl -X POST /api/v1/records/arxiv/2609.35927/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35927/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'