Natural Properties are (roughly) Equivalent to (randomized) Compression Algorithms

Some circuit-analysis algorithms (for example circuit-SAT [Williams 13] and compression [Chen et al, 2015]) imply circuit lower bounds. The opposite direction, using a generic circuit lower bound to build a genericcircuit analysis algorithm without re-using the proof of the lower bound, was not known outside derandomization. We move towards such a connection by using a natural property to construct a randomized compression algorithm.

All scheduled dates:


No Upcoming activities yet