![](/sites/default/files/styles/workshop_banner_sm_1x/public/complexity_logo_final.png.jpg?itok=H_SevtP4)
Description
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:
Upcoming
No Upcoming activities yet