1 citations · 2 across the 3 of their papers we have counts for
4 papers
A Theory for Probabilistic Polynomial-Time Reasoning
Lijie Chen, Jiatu Li, Igor C. Oliveira +1
In this work, we propose a new bounded arithmetic theory, denoted , designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer scie…
Identity Testing for Circuits with Exponentiation Gates
Jiatu Li, Mengdi Wu
Motivated by practical applications in the design of optimization compilers for neural networks, we initiated the study of identity testing problems for arithmetic circuits augment…
On the Unprovability of Circuit Size Bounds in Intuitionistic
Lijie Chen, Jiatu Li, Igor C. Oliveira
We show that there is a constant such that Buss's intuitionistic theory does not prove that SAT requires co-nondeterministic circuits of size at least .…
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Jiatu Li, Igor Carboni Oliveira
While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jeřábek's theory $APC…