Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALGORITHMS FROM CIRCUIT LOWER BOUNDS:
Reports tagged with algorithms from circuit lower bounds:
TR16-008 | 26th January 2016
Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Algorithms from Natural Lower Bounds

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>




ISSN 1433-8092 | Imprint