On read-once threshold formulae and their randomized decision tree complexity

DOI10.1016/0304-3975(93)90254-QzbMath0774.68045OpenAlexW2072478536MaRDI QIDQ1208407

Rafi Heiman, Avi Wigderson, Ilan Newman

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90254-q

zbMATH Keywords

lower bounddecision treesthreshold circuitsread-once \(TC^ 0\)

Mathematics Subject Classification ID

Related Items (9)

An algorithm to learn read-once threshold formulas, and transformations between learning models ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ On linear rewriting systems for Boolean logic and some applications to proof theory ⋮ Competitive evaluation of threshold functions in the priced information model ⋮ Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority ⋮ Randomized vs. deterministic decision tree complexity for read-once Boolean functions ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Optimal ordered binary decision diagrams for read-once formulas ⋮ Complexity measures and decision tree complexity: a survey.

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on probabilistic linear decision trees
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• An arithmetic model of computation equivalent to threshold circuits
• On recognizing graph properties from adjacency matrices
• Parity, circuits, and the polynomial-time hierarchy
• CREW PRAM<scp>s</scp> and Decision Trees
• Neural networks and physical systems with emergent collective computational abilities.

This page was built for publication: On read-once threshold formulae and their randomized decision tree complexity