Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#359224] of Benjamin Rossman

Papers Published

  1. Rossman, B, Shrinkage of decision lists and DNF formulas, Leibniz International Proceedings in Informatics, Lipics, vol. 185 (February, 2021), ISBN 9783959771771 [doi]
    (last updated on 2022/01/23)

    Abstract:
    We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the p-random restriction Rp for all values of p ∈ [0, 1]. For a function f with domain {0, 1}n, let DL(f) denote the minimum size of a decision list that computes f. We show that E[ DL(fRp) ] ≤ DL(f)log2/(1-p)(1 1+ - p p) . For example, this bound is pDL(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).

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320