On randomized complexity of functions approximating the majority function (Q2746911)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1656843
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On randomized complexity of functions approximating the majority function |
scientific article; zbMATH DE number 1656843 |
Statements
11 October 2001
0 references
complexity
0 references
Boolean function
0 references
lower bound
0 references
RAM
0 references
random number generator
0 references
On randomized complexity of functions approximating the majority function (English)
0 references
The computational complexity of partial Boolean functions approximating the majority function by a modified RAM with a random number generator is considered. It is shown that there exist partial functions that approximate the majority function. The deterministic complexity of these functions exceeds their randomized complexity by the factor \(n\) (up to the order), where \(n\) is the number of variables of the Boolean functions under consideration.
0 references
0.7857726812362671
0 references
0.7747036218643188
0 references
0.7531828284263611
0 references
