中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

Negation-Limited Formulas

:::

Negation-Limited Formulas

  • 講者Siyao Guo 博士 (Department of Computer Science and Engineering, CUHK)
    邀請人:鐘楷閔
  • 時間2015-10-15 (Thu.) 10:30 ~ 12:30
  • 地點資訊所舊館 108 演講廳
摘要

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.