2026-07-25T01:58:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13609 2024-03-06T10:52:26Z ddc:004 open_access

Shrinkage of Decision Lists and DNF Formulas Rossman, Benjamin shrinkage decision lists DNF formulas We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the p-random restriction R_p for all values of p ∈ [0,1]. For a function f with domain {0,1}ⁿ, let DL(f) denote the minimum size of a decision list that computes f. We show that E[DL(f ↾ R_p)] ≤ DL(f)^log_{2/(1-p)}((1+p)/(1-p)). For example, this bound is √{DL(f)} when p = √5-2 ≈ 0.24. For Boolean functions f, we obtain the same shrinkage bound with respect to DNF formula size plus 1 (i.e., replacing DL(⋅) with DNF(⋅)+1 on both sides of the inequality). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Rossman 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.70 urn:nbn:de:0030-drops-136098 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.70 eng https://creativecommons.org/licenses/by/3.0/legalcode