scientific article; zbMATH DE number 176776

MaRDI QIDQ4036606zbMATH OpenFDO

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

Publication date 18 May 1993

zbMATH Keywords

error probabilityinner product \(\mod 2\) of two \(n\)-bit vectorslinear decision treesrandomization

Mathematics Subject Classification ID

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

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

(18)

• Randomized Boolean decision trees: Several remarks
• Bounds on the depth of decision trees that compute Boolean functions
• On the power of circuits with gates of low \(L_{1}\) norms.
• Decision trees with Boolean threshold queries
• On the decision tree complexity of threshold functions
• Nearest neighbor representations of Boolean functions
• Lower bounds for linear decision trees via an energy complexity argument
• scientific article; zbMATH DE number 426344 (Why is no real title available?)
• scientific article; zbMATH DE number 3858831 (Why is no real title available?)
• Products and Help Bits in Decision Trees
• Linear Decision Trees, Subspace Arrangements, and Mobius Functions
• scientific article; zbMATH DE number 741345 (Why is no real title available?)
• scientific article; zbMATH DE number 1775396 (Why is no real title available?)
• Lower bounds for linear decision lists
• On the Decision Tree Complexity of Threshold Functions
• Lower bounds for linear decision trees with bounded weights
• Linear threshold functions in decision lists, decision trees, and depth-2 circuits
• A hierarchy of constant communication complexity

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)