30 citations · 61 across the 15 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
Theory and Applications of Probabilistic Kolmogorov Complexity
Zhenjian Lu, Igor C. Oliveira
Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have…
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
The classical coding theorem in Kolmogorov complexity states that if an -bit string is sampled with probability by an algorithm with prefix-free domain then K$(x) \leq \…
Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of : proving hierarchy theorems and showing the e…
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2
The class consists of Boolean functions computable by size- de Morgan formulas whose leaves are any Boolean functions from a class .…
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
Consistency of circuit lower bounds with bounded theories
Jan Bydzovsky, Jan Krajicek, Igor C. Oliveira
Proving that there are problems in that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are…
On monotone circuits with local oracles and clique lower bounds
Jan Krajicek, Igor C. Oliveira
We investigate monotone circuits with local oracles [K., 2016], i.e., circuits containing additional inputs that can perform unstructured computations on the i…
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…
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Igor C. Oliveira, Rahul Santhanam
We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup le…
Near-optimal small-depth lower bounds for small distance connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio +1
We show that any depth- circuit for determining whether an -node graph has an -to- path of length at most must have size . The previous best circu…
Addition is exponentially harder than counting for shallow monotone circuits
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
Let denote the Boolean function which takes as input strings of bits each, representing numbers in , and output…
Learning circuits with few negations
Eric Blais, Clément L. Canonne, Igor C. Oliveira +2
Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean…
Algorithms versus Circuit Lower Bounds
Igor C. Oliveira
Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this s…