On read-once threshold formulae and their randomized decision tree complexity
From MaRDI portal
Publication:1208407
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
