Monotone Boolean formulas can approximate monotone linear threshold functions

被引：9

作者：

Servedio, RA ^{[1
]}

机构：

[1] Columbia Univ, Dept Comp Sci, New York, NY 10027 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2004年 / 142卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

linear threshold functions; Boolean formulas; monotone computation;

D O I：

10.1016/j.dam.2004.02.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that any monotone linear threshold function on n Boolean variables can be approximated to within any constant accuracy by a monotone Boolean formula of poly(n) size. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：181 / 187

页数：7

共 11 条

[1] SORTING IN C LOG N PARALLEL STEPS [J].

AJTAI, M ;

KOMLOS, J ;

SZEMEREDI, E .

COMBINATORICA, 1983, 3 (01) :1-19

[2]

[Anonymous], I HAUTES ETUDES SCI

[3]

[Anonymous], 1992, COMPUT COMPLEX, DOI 10.1007/BF01200426

[4] Simulating threshold circuits by majority circuits [J].

Goldmann, M ;

Karpinski, M .

SIAM JOURNAL ON COMPUTING, 1998, 27 (01) :230-246

[5]

GRIGNI M, 1992, LMS LECTURE NOTES, P57

[6]

HAERDLE W, PARTIALLY LINEAR MOD

[7] ON THE SIZE OF WEIGHTS FOR THRESHOLD GATES [J].

HASTAD, J .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (03) :484-492

[8]

Muroga S., 1971, THRESHOLD LOGIC ITS

[9]

PETROV V.V., 1995, Limit Theorems of Probability Theory: Sequences of Independent Random Variables

[10] SHORT MONOTONE FORMULAS FOR THE MAJORITY FUNCTION [J].

VALIANT, LG .

JOURNAL OF ALGORITHMS, 1984, 5 (03) :363-366

← 1 2 →