2026-08-17T23:50:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5340 2024-03-06T10:36:21Z ddc:004 open_access

Negation-Limited Formulas Guo, Siyao Komargodski, Ilan Negation complexity De Morgan formulas Shrinkage 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-epsilon} negations. In addition, we prove a lower bound on the number of negations required to compute one-way permutations by polynomial-size formulas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siyao Guo and Ilan Komargodski 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.850 urn:nbn:de:0030-drops-53400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.850 eng https://creativecommons.org/licenses/by/3.0/legalcode