2006-07-05から1日間の記事一覧

$\Pr[collision]$ is negligible in $n$

三日唸ってようやく思いついたので, やっと確率の評価が出来た. Impagliazzo and Zuckerman ``How to recycle random bits'' (FOCS '89) *1にRegularity Lemmaが載っているのでそれを使って何とか既存の証明を参考にしながらやりくり. 向こうの証明に難しい…