Fall 2015

Fine-Grained Rough Draft

Oct 28, 2015 10:00 am – 11:30 am 

Add to Calendar


Marco Carmosino (UC San Diego)


Calvin Lab Room 116

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.