; TeX output 1995.03.23:1517lEZV\ƘVff}>>ff P0N cmbx12Bo`oleanCircuitComplexityIFallSemester,1994-5Ꮝ!9DtGGcmr17Lecture7t10:Decemqbser29th0Ǎ P.@ cmti12Lffecturer:fiUri35ZwickTScribe:Guy35MayrazӰR>ffffff}<G<"VG cmbx1010.1IDeCommrunicationComplexityb#G+XQ cmr12Letusconsiderthefollorwingscenario:,g cmmi12AandBNwouldliketocalculateafunctionfG(x;yn9)ofGtrwo6setsofvXariables,Mwherexandyoaretrwo6n-bitvrectors.AandB++rkg(C̸2)VH=)9i>jrkg(C̹id)VHfh{r^Qthenx) ^TBAandBywillnowexecuteanGoptimalprobabilisticprotoScolfortheproblemxD^M.ǎGClaim10.5(RanRazandAviWigderson)C33133x|fe3 (distinctness̹nP)URC33133x|fe3(distjointness̹nP).č#;Prffoof:UVGivrenxinputsxandyfordistjointnesswede netrenaryvectorsx20Gandyn920UasGfollorws:$Px20RAi,=URx̹id.++y2n90RAi=2Vy̹id.++WVeharvethatxandy/aredistjoint()x20andyn920are`distinct'G(asde nedinthethedistinctnessproblem).8NorwexecutetheprotoScolfordistinctness.#ǎ@;lEҎ Cu cmex10<"VG cmbx109DtGGcmr177"Vff cmbx100N cmbx12/}h! cmsl12.@ cmti12-!", cmsy10,g cmmi12+XQ cmr12K cmsy82cmmi8 |{Ycmr8q% cmsy6;cmmi6Aacmr6EE