scientific article; zbMATH DE number 1746571

MaRDI QIDQ4530740zbMATHFDO

Authors Elizaveta Antonovna Okol'Nishnikova

Publication date 28 May 2002

zbMATH Keywords

complexityBoolean functionReed-Muller codebranching programgeneralized Hamming weight

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 5899238
• scientific article; zbMATH DE number 3913677
• Complexity bounds on program realizations of Boolean functions specified in various forms
• scientific article; zbMATH DE number 706832
• Lower bounds for the complexity of restrictions of Boolean functions
• On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
• scientific article; zbMATH DE number 4008289
• scientific article; zbMATH DE number 4095386
• The power of nondeterminism in polynomial-size bounded-width branching programs
• scientific article; zbMATH DE number 4047115

Cited in

(6)

• Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 4172394 (Why is no real title available?)
• A lower bound for the computational complexity of characteristic functions of BCH-codes by branching programs
• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• A nondeterministic space-time tradeoff for linear codes

This page was built for publication:

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