scientific article; zbMATH DE number 176867

zbMATH Open0764.06006MaRDI QIDQ4036698FDOQ4036698

Authors: Ilan Newman 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• Bounding the randomized decision tree complexity of read-once Boolean functions
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Functions that are read-once on a subset of their inputs
• Critical properties and complexity measures of read-once Boolean functions
• An improvement on the complexity of factoring read-once Boolean functions

zbMATH Keywords

read-once functionsread-once Boolean functionsrandomized Boolean decision tree complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (06E30) Boolean functions (94D10)

Cited In (9)

• Functions that are read-once on a subset of their inputs
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• Read-Once Functions Revisited and the Readability Number of a Boolean Function
• Certificates of Non-Membership for Classes of Read-Once Functions
• An improvement on the complexity of factoring read-once Boolean functions
• Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games
• Non-deterministic communication complexity with few witnesses
• On read-once threshold formulae and their randomized decision tree complexity
• Combinatorial characterization of read-once formulae

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