An explicit construction of short monotone formulae for the monotone symmetric functions

Mark Kleiman; Nicholas Pippenger

doi:10.1016/0304-3975(78)90021-X

Theoretical Computer Science

Paper

01 Jan 1978

An explicit construction of short monotone formulae for the monotone symmetric functions

View publication

Abstract

We construct formulae that assume the value 1 when and only when at least k of their n variables assume the value 1, using only conjunction and disconjunction, and having (for any fixed k) only O(nlogn) k 2log*n occurences of variables. © 1978.

Conference paper

Non-gaussian statistical timing analysis using second-order polynomial fitting

Lerong Cheng, Jinjun Xiong, et al.

ASP-DAC 2008

Conference paper

HealthSense: Classification of health-related sensor data through user-assisted machine learning

Erich P. Stuntebeck, John S. Davis II, et al.

HotMobile 2008

Paper

Tight bounds for delay-sensitive aggregation

Yvonne Anne Pignolet, Stefan Schmid, et al.

Discrete Mathematics and Theoretical Computer Science

Conference paper

Selecting an optimal combination of storage & transmission assets with a non-dispatchable electricity supply

Khalid Abdulla, Andrew Wirth, et al.

ICIAfS 2014

View all publications

Abstract

Related

Non-gaussian statistical timing analysis using second-order polynomial fitting

HealthSense: Classification of health-related sensor data through user-assisted machine learning

Tight bounds for delay-sensitive aggregation

Selecting an optimal combination of storage & transmission assets with a non-dispatchable electricity supply