Computing Boolean functions from multiple faulty copies of input bits

DOI10.1016/J.TCS.2003.07.001MaRDI QIDQ596147zbMATH OpenOpenAlexFDO

Authors Xiaomin Chen, Mario Szegedy

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

zbMATH Keywords

Boolean functionsLinear programmingRandomized functionsSensitivity

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(3)

• Bit copying: the ultimate computational simplicity
• scientific article; zbMATH DE number 2086255 (Why is no real title available?)
• RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS

Describes a project that uses

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)