Switching lemma
id:
switching-lemma-163-13556865
title:
Switching lemma
text:
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. It was first introduced by Johan Håstad to prove that AC⁰ Boolean circuits of depth k require size exp to compute the parity function on n bits. He was later awarded the Gödel Prize for this work in 1994. The switching lemma describes the behavior of a depth-2 circuit under random restriction, i.e. when randomly fixing most of the coordinates to 0
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Switching_lemma
date created:
2011-03-29T16:32:29Z
date modified:
2024-08-28T14:06:39Z
main entity:
{"identifier":"Q7659119","url":"https://www.wikidata.org/entity/Q7659119"}
image:
fields total:
13
integrity:
14