Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Igor Carboni Oliveira:

TR21-041 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira

An Efficient Coding Theorem via Probabilistic Representations and its Applications

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

TR21-040 | 15th March 2021
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

TR21-039 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Algorithms and the Structure of Probabilistic Time

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

TR20-021 | 21st February 2020
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

NP-Hardness of Circuit Minimization for Multi-Output Functions

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

TR19-168 | 20th November 2019
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Beyond Natural Proofs: Hardness Magnification and Locality

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

TR19-077 | 30th May 2019
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

Consistency of circuit lower bounds with bounded theories

Proving that there are problems in $P^{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 the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

TR19-073 | 17th May 2019
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

Parity helps to compute Majority

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$ circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can ... more >>>

TR19-064 | 23rd April 2019
Igor Carboni Oliveira

Randomness and Intractability in Kolmogorov Complexity

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability.

This complexity measure gives rise to a ... more >>>

TR18-159 | 11th September 2018
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

Expander-Based Cryptography Meets Natural Proofs

Revisions: 1

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... more >>>

TR18-158 | 11th September 2018
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Hardness magnification near state-of-the-art lower bounds

Revisions: 1

This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs ... more >>>

TR18-139 | 10th August 2018
Igor Carboni Oliveira, Rahul Santhanam

Hardness Magnification for Natural Problems

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include:

1. Let MCSP$[s]$ be the decision problem whose YES instances are ... more >>>

TR18-122 | 3rd July 2018
Igor Carboni Oliveira, Rahul Santhanam

Pseudo-derandomizing learning and approximation

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser
[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed
output with high probability. We explore pseudo-determinism in the settings of learning and ap-
proximation. Our goal is to simulate known randomized algorithms in these settings ... more >>>

TR18-030 | 9th February 2018
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

TR17-173 | 6th November 2017
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

An Average-Case Lower Bound against ACC^0

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

TR16-197 | 7th December 2016
Igor Carboni Oliveira, Rahul Santhanam

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

TR16-196 | 5th December 2016
Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Constructions in Subexponential Time

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

TR16-071 | 1st May 2016
Jan Krajicek, Igor Carboni Oliveira

Unprovability of circuit upper bounds in Cook's theory PV

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>

TR15-123 | 31st July 2015
Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Addition is exponentially harder than counting for shallow monotone circuits

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

TR15-008 | 14th January 2015
Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

The Power of Negations in Cryptography

Revisions: 1

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>>

TR14-173 | 13th December 2014
Igor Carboni Oliveira, Rahul Santhanam

Majority is incompressible by AC$^0[p]$ circuits

Revisions: 1

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

TR14-144 | 30th October 2014
Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Learning circuits with few negations

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 functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

ISSN 1433-8092 | Imprint