Constructing O(n Log n) Size Monotone Formulae For The k-th Elementary Symmetric Polynomial Of n Boolean Variables

25 August 2005

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 506-515
https://doi.org/10.1109/sfcs.1984.715953

Abstract

In this paper, we construct formulae for the k-th elementary symmetry polynomial of n Boolean variables, using only conjunction and disjunction, which for fixed k are of size O(n log n), with the construction taking time polynomial in n. We also prove theorems involving n log n/spl middot/(polynomial in k) upper bounds on such formulae. Our methods involve solving the following combinatorial problem: for fixed k and any n construct a collection of r=O(log n) functions f/sub 1/,...,f/sub r/ from {1,...,n} to {1,...,K} such that any subset of {1,...,n} of order k is mapped 1-1 to {1,...,k} by at least one f/sub i/..

Keywords

This publication has 4 references indexed in Scilit:

Short monotone formulae for the majority function
Published by Elsevier ,2004
Introduction to Coding Theory
Published by Springer Nature ,1982
Probabilistic Algorithms in Finite Fields
SIAM Journal on Computing, 1980
An explicit construction of short monotone formulae for the monotone symmetric functions
Theoretical Computer Science, 1978