arXiv Open Access 2017

Lower bound for monotone Boolean convolution

Mike S. Paterson

Lihat Sumber

Abstrak

Any monotone Boolean circuit computing the $n$-dimensional Boolean convolution requires at least $n^2$ and-gates. This precisely matches the obvious upper bound.

Topik & Kata Kunci

cs.CC

Penulis (1)

Mike S. Paterson

Format Sitasi

APA MLA BibTeX

Paterson, M.S. (2017). Lower bound for monotone Boolean convolution. https://arxiv.org/abs/1708.03523

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓