Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with natural properties:
TR99-045 | 16th November 1999
Valentine Kabanets, Jin-Yi Cai

Circuit Minimization Problem

We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or ... more >>>

TR17-023 | 15th February 2017
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

The Power of Natural Properties as Oracles

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).
We obtain new circuit lower bounds, as well as some hardness results for the relativized version ... more >>>

ISSN 1433-8092 | Imprint