Linear Transformations in Boolean Complexity Theory

DOI10.1007/978-3-540-73001-9_32MaRDI QIDQ5425332zbMATH OpenOpenAlexFDO

Authors Joel Friedman

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_32

zbMATH Keywords

Boolean circuit complexitycohomologylinear transformations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of Linear Boolean Operators
• The generalized complexity of linear Boolean functions
• On complexity of linear operators on the class of circuits of depth 2
• On the complexity of linear Boolean operators with thin matrices
• scientific article; zbMATH DE number 3867233

Cited in

(6)

• A useful transform of standard input data for a classical NP-complete problem
• Betti numbers of polynomial hierarchical models for experimental designs
• A linear-time transformation of linear inequalities into conjunctive normal form
• scientific article; zbMATH DE number 6027103 (Why is no real title available?)
• Complexity of Linear Boolean Operators
• Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks

This page was built for publication: Linear Transformations in Boolean Complexity Theory

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