30 citations · 61 across the 15 of their papers we have counts for
20 papers
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…
Quantum learning algorithms imply circuit lower bounds
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur +2
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let be a class of polynomial-size concepts…
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…
Unprovability of circuit upper bounds in Cook's theory PV
Jan Krajicek, Igor C. Oliveira
We establish unconditionally that for every integer there is a language $L \in \mbox{P}$ such that it is consistent with Cook's theory PV that . Our…
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…
Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
Marcelo M. Gauy, Hiêp Hàn, Igor C. Oliveira
We investigate the asymptotic version of the Erdős-Ko-Rado theorem for the random -uniform hypergraph . For , let and $D…
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…
An algebraic formulation of the graph reconstruction conjecture
Igor C. Oliveira, Bhalchandra D. Thatte
The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its v…