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

No abstract is available for this paper.

• Publication year

  1990

• Venue

  Proceedings Fifth Annual Structure in Complexity Theory Conference

• Publication date

  1990-07-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SCT.1990.113956
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Monte Carlo Boolean decision tree complexity of read-once formulae

  1991cited by this paper
• Circuits and local computation

  1989cited by this paper
• A note on the power of threshold circuits

  1989cited by this paper
• On the computational power of PP and (+)P

  1989cited by this paper
• CREW PRAMS and decision trees

  1989cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper
• Lower bounds on the complexity of graph properties

  1988cited by this paper
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

  1987cited by this paper
• Algebraic methods in the theory of lower bounds for Boolean circuit complexity

  1987cited by this paper
• On Threshold Circuits and Polynomial Computation

  1987cited by this paper
• Threshold circuits of bounded depth

  1987cited by this paper
• Lower bounds to randomized algorithms for graph properties

  1987cited by this paper
• Probabilistic Boolean decision trees and the complexity of evaluating game trees

  1986influential reference
• Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations

  1986cited by this paper
• Lower Bounds on Probabilistic Linear Decision Trees

  1985cited by this paper
• ∑11-Formulae on finite structures

  1983cited by this paper
• Neural networks and physical systems with emergent collective computational abilities.

  1982cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981cited by this paper
• On Recognizing Graph Properties from Adjacency Matrices

  1976cited by this paper

• Lower bounds for uniform read-once threshold formulae in the randomized decision tree model

  2022influential citation
• On linear rewriting systems for Boolean logic and some applications to proof theory

  2016cites this paper
• No complete linear term rewriting system for propositional logic

  2015cites this paper
• Analytic Methods in Concrete Complexity

  2014cites this paper
• An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority,

  2013influential citation
• A Composition Theorem for the Fourier Entropy-Influence Conjecture

  2013cites this paper
• Information theory methods in communication complexity

  2012cites this paper
• Competitive evaluation of threshold functions in the priced information model

  2011cites this paper
• Improved bounds for the randomized decision tree Complexity of recursive majority

  2011influential citation
• Bounding the randomized decision tree complexity of read-once Boolean functions

  2011cites this paper
• On Directional vs. General Randomized Decision Tree Complexity for Read-Once Formulas

  2011influential citation
• Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

  2010cites this paper
• On Directional vs. Undirectional Randomized Decision Tree Complexity for Read-Once Formulas

  2010influential citation
• Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas

  2009cites this paper
• Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

  2009cites this paper
• On the Communication Complexity of Read-Once AC^0 Formulae

  2009cites this paper
• Function Evaluation Via Linear Programming in the Priced Information Model

  2008cites this paper
• Read-Once Threshold Formulas , JustifyingAssignments , and Generic Transformations ( Revised Version )

  2007cites this paper
• On Randomized and Quantum Query Complexities

  2005cites this paper
• An algorithm to learn read-once threshold formulas, and transformations between learning models

  2005cites this paper
• Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

  2004cites this paper
• UNIVERSITY OF DORTMUND REIHE COMPUTATIONAL INTELLIGENCE COLLABORATIVE RESEARCH CENTER 531 Design and Management of Complex Technical Processes and Systems by means of Computational Intelligence Methods Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

  2004cites this paper
• Two applications of information complexity

  2003cites this paper
• about the Internet and Networking : 2010 – 2019

  2003cites this paper
• Complexity measures and decision tree complexity: a survey

  2002cites this paper
• Quantum Computing and Communication Complexity

  2001cites this paper
• Quantum Computing and Communication Complexity

  2001cites this paper
• Optimal ordered binary decision diagrams for read-once formulas

  2000cites this paper
• Reducing Error Probability in Quantum Algorithms ( Extended Abstract )

  1999cites this paper
• Bounds for small-error and zero-error quantum algorithms

  1999influential citation
• Circuit Complexity before the Dawn of the New Millennium

  1996cites this paper
• An Algorithm to Learn Read-Once Threshold Formulas, and some Generic Transformations between Learning Models

  1993influential citation
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions

  1991cites this paper
• On the Monte Carlo Boolean decision tree complexity of read-once formulae

  1991cites this paper
• Read-Once Threshold Formulas, Justifying Assignments, and Generic Transformations

  1991cites this paper
• Computational Complexity of Learning Read-Once Formulas over Different Bases

  1990cites this paper