Negation-Limited Formulas
- LecturerDr. Siyao Guo (Department of Computer Science and Engineering, CUHK)
Host: Kai-Min Chung - Time2015-10-15 (Thu.) 10:30 ~ 12:30
- LocationAuditorium 108 at old IIS Building
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 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 n^{1/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.