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

Math @ Duke



Publications [#348669] of Benjamin Rossman

Papers Published

  1. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Computational Complexity, vol. 27 no. 2 (June, 2018), pp. 209-223 [doi]
    (last updated on 2022/05/19)

    We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity O(1dlogs)d. In particular, this gives a tight 2Ω(d(n1/d-1)) lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding 2Ω(n1/d) and O(log s) d bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.
ph: 919.660.2800
fax: 919.660.2821

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