All reports by Author Igor Oliveira:

__
TR24-115
| 14th July 2024
__

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam#### On the Complexity of Avoiding Heavy Elements

__
TR24-059
| 4th April 2024
__

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity

__
TR22-081
| 26th May 2022
__

Zhenjian Lu, Igor Oliveira#### Theory and Applications of Probabilistic Kolmogorov Complexity

__
TR22-072
| 15th May 2022
__

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

__
TR21-095
| 8th July 2021
__

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira#### LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

__
TR20-185
| 1st December 2020
__

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram#### Quantum learning algorithms imply circuit lower bounds

Revisions: 1

__
TR20-018
| 18th February 2020
__

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

We introduce and study the following natural total search problem, which we call the {\it heavy element avoidance} (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N) \ge 1/\poly(N)$ fixed in advance, output an $N$-bit string that has ... more >>>

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string $x$ can be generated by a ... more >>>

Zhenjian Lu, Igor Oliveira

Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants ... more >>>

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Oliveira

We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. Building on a number of techniques, we establish the ... more >>>

Srinivasan Arunachalam, Alex Grilo, Tom Gur, Igor Oliveira, Aarthi Sundaram

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathrm{C}$ be a class of polynomial-size concepts, and suppose that $\mathrm{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 - \gamma$ by a time $T$ quantum algorithm. ... more >>>

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>