scientific article; zbMATH DE number 176776

MaRDI QIDQ4036606zbMATH OpenFDO

Authors Hans Dietmar Gröger, Gy. Turán

Publication date 18 May 1993

zbMATH Keywords

randomizationerror probabilitylinear decision treesinner product \(\mod 2\) of two \(n\)-bit vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Recommendations

• Lower bounds for linear decision trees with bounded weights
• Lower bounds for linear decision trees via an energy complexity argument
• scientific article; zbMATH DE number 741345
• Decision trees with Boolean threshold queries
• Bounds on the depth of decision trees that compute Boolean functions

Cited in

(13)

• Lower bounds for linear decision trees via an energy complexity argument
• Lower bounds for linear decision trees with bounded weights
• On the power of circuits with gates of low \(L_{1}\) norms.
• scientific article; zbMATH DE number 426344 (Why is no real title available?)
• Lower bounds for linear decision lists
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)
• Decision trees with Boolean threshold queries
• Linear threshold functions in decision lists, decision trees, and depth-2 circuits
• scientific article; zbMATH DE number 3858831 (Why is no real title available?)
• On the Decision Tree Complexity of Threshold Functions
• Nearest neighbor representations of Boolean functions
• scientific article; zbMATH DE number 741345 (Why is no real title available?)
• On the decision tree complexity of threshold functions

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 Q4036606)