ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS

DOI10.1142/S0129054190000023zbMATH Open0725.94014OpenAlexW1976540405MaRDI QIDQ5202960FDOQ5202960

Authors: Andrew Chi-Chih Yao, Claire Kenyon 

Publication date: 1990

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054190000023

Recommendations

• On one criterion of the optihality of an algorithm for evaluating monotonic boolean functions
• scientific article; zbMATH DE number 3943711
• Approximate evaluations of characteristic polynomials of Boolean functions
• scientific article; zbMATH DE number 2086255
• Computing Boolean functions from multiple faulty copies of input bits

zbMATH Keywords

lower boundserror correctionboolean functionunreliable tests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fault detection; testing in circuits and networks (94C12)

Cited In (10)

• Searching games with errors -- fifty years of coping with liars
• On the generation of false images of linear Boolean functions
• Evaluation, Strength, and Relevance of Variables of Boolean Functions
• Computing Boolean functions from multiple faulty copies of input bits
• Title not available (Why is that?)
• Three Thresholds for a Liar
• The Maximum Latency and Identification of Positive Boolean Functions
• Least adaptive optimal search with unreliable tests
• Title not available (Why is that?)
• Evaluation of monotone DNF formulas

This page was built for publication: ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5202960)