Nayak's info.theo.argument x∈{0,1}n Index(x,i)=xi ie[n] Alice Px Bob [Nayak'99]Q1(Index)=Q(n). -px contains Q(1)info of x1,since i may be 1. -Regardless of x1,px contains Q(1)info of x2. And so on.Nayak’s info. theo. argument • [Nayak’99] Q1 (Index) = Ω(n). – ρx contains Ω(1) info of x1 , since i may be 1. – Regardless of x1 , ρx contains Ω(1) info of x2 . – And so on. Alice Bob x{0,1}n i[n] Index(x,i) = xi ρx