Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 41 min ago
PreprintCC BY 4.0arXiv

Pseudo-solutions of polynomial systems and the lower bound problem for AC0[p]-Frege systems

  • Jan Krajicek
Open at sourcePDFDOICite

Abstract

The problem to establish a lower bound for AC0[p]-Frege refutations of a system of polynomial equations over bf Fp 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 Fp.

Related

  1. Generic finiteness of solutions to parametrized systems of generalized polynomial inequalities
    Stefan Müller
    arXivPreprintarXiv licenceFull textSystems & synthetic biologyAlgebra & number theoryarXiv
  2. Conic Pseudo-Finslerian Mechanical Systems
    Benigno Oliveira Alves, Glaene S. S. Mendonça
    arXivPreprintarXiv licenceFull textGeometry & topologyMathematical physicsarXiv
  3. Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
    Saroj Prasad Chhatoi, Aneel Tanwani, Didier Henrion
    HALPreprintPublisher termsFull textOptimisation & controlHAL
  4. On the Peak Estimation of Scalar Polynomial Systems via Integrability
    Karolína Sehnalová
    arXivPreprintCC BY 4.0Full textDynamical systemsOptimisation & controlarXiv
  5. Complete solution to the weak persistent center and isochronous center problems of cubic polynomial systems
    Feng Li, Huimei Liu, Chen Cao +1
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv

Cite

BibTeXRIS
BibTeX
@misc{krajicek2026pseudosolutions,
  title = {{Pseudo-solutions of polynomial systems and the lower bound problem for $\mboxAC^0[p]$-Frege systems}},
  author = {Jan Krajicek},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35927},
  eprint = {2609.35927},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35927},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Pseudo-solutions of polynomial systems and the lower bound problem for AC^0[p]-Frege systems
AU  - Jan Krajicek
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.35927
UR  - https://arxiv.org/abs/2609.35927
AB  - The problem to establish a lower bound for 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.
ER  -