CS Events Monthly View
Wednesday, February 03, 2016, 11:00am
We give an efficient structural decomposition theorem for formulas that depends on their negation complexity and demonstrate its power with the following applications.
• We prove that every formula that contains t negation gates can be shrunk using a random restriction to a formula of size O(t) with the shrinkage exponent of monotone formulas. As a result, the shrinkage exponent of formulas that contain a constant number of negation gates is equal to the shrinkage exponent of monotone formulas.
• We give an efficient transformation of formulas with t negation gates to circuits with log(t) negation gates. This transformation provides a generic way to cast results for negation-limited circuits to the setting of negation-limited formulas. For example, using a result of Rossman (CCC '15), we obtain an average-case lower bound for formulas of polynomial-size on n variables with n1/2−ϵ negations.
In addition, we prove a lower bound on the number of negations required to compute one-way permutations by polynomial-size formulas.
Joint work with Ilan Komargodski.
Speaker: Siyao Guo
Location : Core A (Room 301)
Eric Allender, Pranjal Awasthi, Michael Saks and Mario Szegedy
Event Type: Seminar
Courant Institute (New York University)