Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Switching_lemma> ?p ?o. }
Showing items 1 to 18 of
18
with 100 items per page.
- Switching_lemma abstract "In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.Using the switching lemma, Johan Håstad (1987) showed that Boolean circuits of depth k in which only AND, OR, and NOT logic gates are allowed require size for computing the parity function.The switching lemma says that depth-2 circuits in which some fraction of the variables have been set randomly depend with high probability only on very few variables after the restriction. The name of the switching lemma stems from the following observation: Take an arbitrary formula in conjunctive normal form, which is in particular a depth-2 circuit. Now the switching lemma guarantees that after setting some variables randomly, we end up with a Boolean function that depends only on few variables, i.e., it can be computed by a decision tree of some small depth . This allows us to write the restricted function as a small formula in disjunctive normal form. A formula in conjunctive normal form hit by a random restriction of the variables can therefore be "switched" to a small formula in disjunctive normal form.The original proof of the switching lemma (Håstad 1987) involves an argument with conditional probabilities.Arguably simpler proofs have been subsequently given by Razborov (1993) and Beame (1994). For an introduction, see Chapter 14 in Arora & Barak (2009).".
- Switching_lemma wikiPageExternalLink complexity.
- Switching_lemma wikiPageID "31332864".
- Switching_lemma wikiPageRevisionID "589423254".
- Switching_lemma authorlink "Johan Håstad".
- Switching_lemma first "Johan".
- Switching_lemma hasPhotoCollection Switching_lemma.
- Switching_lemma last "Håstad".
- Switching_lemma year "1987".
- Switching_lemma subject Category:Circuit_complexity.
- Switching_lemma subject Category:Computational_complexity_theory.
- Switching_lemma comment "In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits.Using the switching lemma, Johan Håstad (1987) showed that Boolean circuits of depth k in which only AND, OR, and NOT logic gates are allowed require size for computing the parity function.The switching lemma says that depth-2 circuits in which some fraction of the variables have been set randomly depend with high probability only on very few variables after the restriction. ".
- Switching_lemma label "Switching lemma".
- Switching_lemma sameAs m.0gkz30m.
- Switching_lemma sameAs Q7659119.
- Switching_lemma sameAs Q7659119.
- Switching_lemma wasDerivedFrom Switching_lemma?oldid=589423254.
- Switching_lemma isPrimaryTopicOf Switching_lemma.