Advanced Randomization
Haoqiang Fan
IIIS, Tsinghua
Hello
▶ More stories about Xiaoqiang and Ameba!
2/106
Recovering Linear Function
▶ mod 2
▶ f(x
1
,x
2
,...,x
n
)=x
1
⊕x
2
⊕x
5
▶ given access to a noisy version of f
▶ f(x)=f(x)⊕g(x)
▶ g is non-zero on only 30% inputs
▶ can you recover f?
~
3/106
Little Secret
▶ Familiar?
▶ If you only have random samples
▶ Last year's CTSC. Collision + FFT, time
complexity is
▶
▶ where the noise ratio is 1/2-γ
▶ not polynomial
▶ let's forget about it
4/106
Little Secret
▶ If we can query arbitrary point
▶ f(x)
▶ can we do better?
▶ Polynomial?
~
5/106
