Igor C. Oliveira

Available identifiers

zbMath Open oliveira.igor-carboniMaRDI QIDQ2125079

List of research outcomes

Publication	Date of Publication	Type
Constant-depth circuits vs. monotone circuits	2024-11-19	Paper
Probabilistic Kolmogorov complexity with applications to average-case complexity	2024-07-05	Paper
Optimal coding theorems in time-bounded Kolmogorov complexity	2024-06-24	Paper
A duality between one-way functions and average-case symmetry of information	2024-05-08	Paper
Unprovability of strong complexity lower bounds in bounded arithmetic	2024-05-08	Paper
Pseudodeterministic algorithms and the structure of probabilistic time	2023-11-14	Paper
https://portal.mardi4nfdi.de/entity/Q6161054	2023-06-26	Paper
Beyond Natural Proofs: Hardness Magnification and Locality	2023-04-27	Paper
https://portal.mardi4nfdi.de/entity/Q5875777	2023-02-03	Paper
Hardness magnification near state-of-the-art lower bounds	2022-07-27	Paper
Parity helps to compute majority	2022-07-27	Paper
Randomness and Intractability in Kolmogorov Complexity	2022-07-21	Paper
https://portal.mardi4nfdi.de/entity/Q5092472	2022-07-21	Paper
Algorithms and lower bounds for de morgan formulas of low-communication leaf gates	2022-07-21	Paper
Expander-based cryptography meets natural proofs	2022-04-12	Paper
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates	2022-03-29	Paper
https://portal.mardi4nfdi.de/entity/Q5028364	2022-02-09	Paper
https://portal.mardi4nfdi.de/entity/Q5121893	2020-09-22	Paper
https://portal.mardi4nfdi.de/entity/Q5114830	2020-06-26	Paper
https://portal.mardi4nfdi.de/entity/Q5111148	2020-05-26	Paper
An average-case lower bound against \(\mathsf{ACC}^0\)	2020-02-12	Paper
Beyond Natural Proofs: Hardness Magnification and Locality	2019-11-19	Paper
Consistency of circuit lower bounds with bounded theories	2019-05-30	Paper
On monotone circuits with local oracles and clique lower bounds	2018-08-08	Paper
30th Conference on Computational Complexity (CCC 2015)	2018-01-24	Paper
Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability	2017-10-10	Paper
Near-optimal small-depth lower bounds for small distance connectivity	2017-09-29	Paper
Learning circuits with few negations	2017-08-31	Paper
Pseudodeterministic constructions in subexponential time	2017-08-17	Paper
Addition is exponentially harder than counting for shallow monotone circuits	2017-08-17	Paper
Unprovability of circuit upper bounds in Cook's theory PV	2017-05-08	Paper
An algebraic formulation of the graph reconstruction conjecture	2016-04-15	Paper
The Power of Negations in Cryptography	2015-07-06	Paper
Erratum to ``The Ricean objection: An analogue of Rice's theorem for first-order theories.	2009-12-18	Paper
The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories	2009-01-21	Paper

Research outcomes over time

This page was built for person: Igor C. Oliveira