Computing Boolean functions from multiple faulty copies of input bits

DOI10.1016/j.tcs.2003.07.001zbMath1047.94022OpenAlexW2168377622MaRDI QIDQ596147

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 programmingSensitivityRandomized functions

Mathematics Subject Classification ID

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

Related Items

RELIABLE INTERNET-BASED MASTER-WORKER COMPUTING IN THE PRESENCE OF MALICIOUS WORKERS

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Sensitivity vs. block sensitivity (an average-case study)
• Sensitivity vs. block sensitivity of Boolean functions
• Invariance of complexity measures for networks with unreliable gates
• CREW PRAM<scp>s</scp> and Decision Trees
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates
• ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS
• Noise sensitivity of Boolean functions and applications to percolation