Since 2014
Reviewing Bounds on the Circuit Size of the Hardest Functions
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Reviewing Bounds on the Circuit Size of the Hardest Functions
|
|
| Creator |
Frandsen, Gudmund Skovbjerg
Miltersen, Peter Bro |
|
| Description |
In this paper we review the known bounds for L(n), the circuit size complexity of the hardest Boolean function on n input bits. The best known bounds appear to be 2^n / n (1 + log n / n - O(1/n))
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
2005-03-11
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/21875
10.7146/brics.v12i9.21875 |
|
| Source |
BRICS Report Series; No 9 (2005): RS-9 Reviewing Bounds on the Circuit Size of the Hardest Functions
BRICS Report Series; No 9 (2005): RS-9 Reviewing Bounds on the Circuit Size of the Hardest Functions 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/21875/19302
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|