Simple general magnification of circuit lower bounds

Albert Atserias, Moritz Müller

We introduce a technically and conceptually simple approach to magnification of circuit and formula lower bounds. Central to the method are so-called distinguishers, sparse matrice…