Unprovability of strong complexity lower bounds in bounded arithmetic
J Li, IC Oliveira - Proceedings of the 55th Annual ACM Symposium on …, 2023 - dl.acm.org
While there has been progress in establishing the unprovability of complexity statements in
lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory APC 1 …
lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory APC 1 …
On matrix rank function over bounded arithmetics
E Ken, S Kuroda - arXiv preprint arXiv:2310.05982, 2023 - arxiv.org
In arXiv: 1811.04313, a definition of determinant is formalized in the bounded arithmetic $
VNC^{2} $. Following the presentation of [Gathen, 1993], we can formalize a definition of …
VNC^{2} $. Following the presentation of [Gathen, 1993], we can formalize a definition of …
[HTML][HTML] On some -formulae generalizing counting principles over
E Ken - Archive for Mathematical Logic, 2024 - Springer
We formalize various counting principles and compare their strengths over V 0. In particular,
we conjecture the following mutual independence between: a uniform version of modular …
we conjecture the following mutual independence between: a uniform version of modular …
Formalizing Pfaffian in bounded arithmetic
S Kuroda - arXiv preprint arXiv:2404.01728, 2024 - arxiv.org
arXiv:2404.01728v1 [math.LO] 2 Apr 2024 Page 1 arXiv:2404.01728v1 [math.LO] 2 Apr 2024
Formalizing Pfaffian in bounded arithmetic Satoru Kuroda∗ Department of Culture and …
Formalizing Pfaffian in bounded arithmetic Satoru Kuroda∗ Department of Culture and …
[PDF][PDF] Polynomial ideals in algebraic complexity
RG Andrews - 2023 - ideals.illinois.edu
First and foremost, I want to express my deepest gratitude to my Ph. D. advisor, Michael A.
Forbes. He has been a source of unwavering encouragement, sage guidance, and sincere …
Forbes. He has been a source of unwavering encouragement, sage guidance, and sincere …
[PDF][PDF] SIGACT News Complexity Theory Column (DRAFT)
IC Oliveira - dcs.warwick.ac.uk
The investigation of the inherent complexity of computational tasks is a central research
direction in 35 theoretical computer science. While unconditional results are known in a …
direction in 35 theoretical computer science. While unconditional results are known in a …