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

DOI10.1109/TIT.2013.2270275MaRDI QIDQ5346309zbMATH OpenFDO

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)

Full work available at URL https://doi.org/10.1109/TIT.2013.2270275

Mathematics Subject Classification ID

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

Cited in

(6)

• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Bounded-depth circuits cannot sample good codes
• On the minimum depth of circuits with linear number of wires encoding good codes
• Explicit time and space efficient encoders exist only with random access
• Tight and Rigorous Error Bounds for Basic Building Blocks of Double-Word Arithmetic

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)