Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Oliveira, Igor C."'
We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathsf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result
Externí odkaz:
http://arxiv.org/abs/2404.11841
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 the topic, Gat and Goldwasser posed as their main open problem whethe
Externí odkaz:
http://arxiv.org/abs/2305.15140
Autor:
Cavalar, Bruno P., Oliveira, Igor C.
We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every $k \geq 1$, there is a monotone function in ${\sf AC^0}$ that requires monotone circuits of depth $\Omega(\log^k n)$. This significant
Externí odkaz:
http://arxiv.org/abs/2305.06821
Autor:
Lu, Zhenjian, Oliveira, Igor C.
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
Externí odkaz:
http://arxiv.org/abs/2205.14718
The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] e
Externí odkaz:
http://arxiv.org/abs/2204.08312
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $\mathsf{BPTIME}$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarise
Externí odkaz:
http://arxiv.org/abs/2103.08539
We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a class of polynomial-size concepts, and suppose that $\mathfrak{C}$ can be PAC-learned with membership q
Externí odkaz:
http://arxiv.org/abs/2012.01920
Autor:
Chen, Lijie, Hirahara, Shuichi, Oliveira, Igor C., Pich, Jan, Rajgopal, Ninad, Santhanam, Rahul
Hardness magnification reduces major complexity separations (such as $\mathsf{\mathsf{EXP}} \nsubseteq \mathsf{NC}^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, C
Externí odkaz:
http://arxiv.org/abs/1911.08297
Publikováno v:
Logical Methods in Computer Science, Volume 16, Issue 2 (June 18, 2020) lmcs:5578
Proving that there are problems in $\mathsf{P}^\mathsf{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that
Externí odkaz:
http://arxiv.org/abs/1905.12935
Autor:
Krajicek, Jan, Oliveira, Igor C.
Publikováno v:
Chicago Journal of Theoretical Computer Science, vol.2018, nb.1, (March 2018), pp.1-18
We investigate monotone circuits with local oracles [K., 2016], i.e., circuits containing additional inputs $y_i = y_i(\vec{x})$ that can perform unstructured computations on the input string $\vec{x}$. Let $\mu \in [0,1]$ be the locality of the circ
Externí odkaz:
http://arxiv.org/abs/1704.06241