Title: Negation-Limited Formulas
Speaker: Siyao Guo, Courant Institute (New York University)
Date: Wednesday, February 3, 2016 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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 tt negation gates can be shrunk using a random restriction to a formula of size O(t)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)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 nn variables with n1/2−ϵ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.
See: http://www.cs.rutgers.edu/~allender/theory-spring16.html