{"id":"arxiv/2609.35927","url":"https://arxiv.org/abs/2609.35927","tags":["cs.CC","math.LO"],"score":0,"title":"Pseudo-solutions of polynomial systems and the lower bound problem for $\\mbox{AC}^0[p]$-Frege systems","domain":"cs.CC","source":"arxiv","authors":["Jan Krajicek"],"reviews":0,"subject":"cs.CC","summary":"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$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}