NDLI: Reliable computation with noisy circuits and decision trees-a general n log n lower bound

Content Provider	IEEE Xplore Digital Library
Author	Reischuk, R. Schmeltz, B.
Copyright Year	1991
Description	Author affiliation: Tech. Hochschule Darmstadt, Germany (Reischuk, R.; Schmeltz, B.)
Abstract	Boolean circuits in which gates independently make errors with probability (at most) epsilon are considered. It is shown that the critical number crit(f) of a function f yields lower bound Omega (crit(f) log crit (f)) for the noisy circuit size. The lower bound is proved for an even stronger computational model, static Boolean decision trees with erroneous answers. A decision tree is static if the questions it asks do not depend on previous answers. The depth of such a tree provides a lower bound on the number of gates that depend directly on some input and hence on the size of a noisy circuit. Furthermore, it is shown that an Omega (n log n) lower bound holds for almost all Boolean n-input functions with respect to the depth of noisy dynamic decision trees. This bound is the best possible and implies that almost all n-input Boolean functions have noisy decision tree complexity Theta (n log n) in the static as well as in the dynamic case.<>
Starting Page	602
Ending Page	611
File Size	578894
Page Count	10
File Format	PDF
ISBN	0818624450
DOI	10.1109/SFCS.1991.185425
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1991-10-01
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Circuit noise Decision trees Error probability Upper bound Computational modeling Boolean functions Redundancy Circuit faults
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower bounds for the complexity of reliable Boolean circuits with noisy gates

On a lower bound for the redundancy of reliable networks with noisy gates

Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates (1994)

Approximating Boolean Functions with Depth-2 Circuits

Can large fanin circuits perform reliable computations in the presence of noise?.

Can large fanin circuits perform reliable computations in the presence of faults? (1998).

Reliable cellular automata with self-organization

Lower bounds for the complexity of reliable boolean circuits with noisy gates (1994).

On the reliable computation of certain boolean functions by noisy decision trees.

Reliable computation with noisy circuits and decision trees-a general n log n lower bound

Similar Documents

Lower bounds for the complexity of reliable Boolean circuits with noisy gates

On a lower bound for the redundancy of reliable networks with noisy gates

Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates (1994)

Approximating Boolean Functions with Depth-2 Circuits

Can large fanin circuits perform reliable computations in the presence of noise?.

Can large fanin circuits perform reliable computations in the presence of faults? (1998).

Reliable cellular automata with self-organization

Lower bounds for the complexity of reliable boolean circuits with noisy gates (1994).

On the reliable computation of certain boolean functions by noisy decision trees.

Reliable computation with noisy circuits and decision trees-a general n log n lower bound