arXiv Open Access 2009

A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent

Pascal Koiran Sylvain Perifel

Lihat Sumber

Abstrak

We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.

Topik & Kata Kunci

cs.CC

Penulis (2)

Pascal Koiran

Sylvain Perifel

Format Sitasi

APA MLA BibTeX

Koiran, P., Perifel, S. (2009). A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. https://arxiv.org/abs/0902.1866

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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