30 citations · 61 across the 15 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.CC2023★ 1 cited
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…
cs.CC2023
Constant-depth circuits vs. monotone circuits
Bruno P. Cavalar, Igor C. Oliveira
We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every , there is a monotone function in that re…
cs.CC2023★ 1 cited
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira +2
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on…