Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates

DOI10.1109/TIT.2013.2270275MaRDI QIDQ5346309zbMATHFDO

Authors Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Bounds on codes (94B65) Analytic circuit theory (94C05)

Cited in

(5)

• On the minimum depth of circuits with linear number of wires encoding good codes
• Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Bounded-depth circuits cannot sample good codes

This page was built for publication: Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346309)