1 citations · 1 across the 3 of their papers we have counts for
3 papers
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.CC2016
Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infi…