cryptography presentation, topic 4 揀 1, 12 mins
最後選了 garbled circuits
Alice 和 Bob 各自有 input X, Y, 可以在不洩漏自己 input 下共同 compute f(X, Y)
雖只是 passive adversary 的版本, 不過 construction很巧妙, 所以被吸引了
連帶睇埋 oblivious transfer
presentation rehearsal 了數次, 但到了 present 時仍然開始 overrun, 砍掉最後 1/3, 幸好那 part 砍掉也不影響主題, 沒有人發現
今天同時有 training, 其中一條 turns out 是問 DFA Equivalence
來自 313 的印象, 打算先做 DFA minimization 再 compare, 結果寫起來也有點長
結果做不完, 回家繼續揼, 最後搞了一大輪終於過掉
但其實原來 DFA Equivalence 有更簡單巧妙的做法, 而且接近 linear time!
詳看 Problem D
No comments:
Post a Comment