Computing Boolean functions from multiple faulty copies of input bits

DOI10.1016/J.TCS.2003.07.001zbMATH Open1047.94022OpenAlexW2168377622MaRDI QIDQ596147FDOQ596147

Mario Szegedy, Xiaomin Chen

Publication date: 10 August 2004

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.07.001

Recommendations

• scientific article; zbMATH DE number 2086255
• On boolean decision trees with faulty nodes
• scientific article; zbMATH DE number 2123418
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• Reliable computation by formulas in the presence of noise

zbMATH Keywords

Boolean functionsLinear programmingRandomized functionsSensitivity

Mathematics Subject Classification ID

Linear programming (90C05) Boolean functions (06E30)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Noise sensitivity of Boolean functions and applications to percolation
• Sensitivity vs. block sensitivity of Boolean functions
• CREW PRAM<scp>s</scp> and Decision Trees
• Sensitivity vs. block sensitivity (an average-case study)
• Invariance of complexity measures for networks with unreliable gates
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS

Cited In (3)

• Bit copying: the ultimate computational simplicity
• Title not available (Why is that?)
• RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS

Uses Software

• CPLEX

This page was built for publication: Computing Boolean functions from multiple faulty copies of input bits

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