Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables

DOI10.1137/0215047zbMath0613.94011OpenAlexW1977452695MaRDI QIDQ4721956

Joel Friedman

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215047

zbMATH Keywords

partitionsthreshold functionerror-correcting codesmonotone Boolean formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05)

Related Items (6)

The graph clustering problem has a perfect zero-knowledge interactive proof ⋮ How to Share a Secret, Infinitely ⋮ Construction of universal enumerators and formulas for threshold functions ⋮ ERCW PRAMs and optical communication ⋮ Using amplification to compute majority with small majority gates ⋮ The conjunctive complexity of quadratic Boolean functions

This page was built for publication: Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables