SODA'18読み会に参加した

先月ですが、理研AIPでSODA2018読み会なるものが開催されたので、自分も論文を読んできました。

読んだ論文：
Blais, et al. (2018) Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism (URL)

スライド：

内容としては性質検査 (property testing) という分野に属する研究で、与えられたブール関数がk-juntaという性質をもつかどうかを、入力長によらない定数時間で判定するアルゴリズムを提案したものです。（もう少し正確には、tolerant testingという設定で、kの多項式回のクエリアクセスでの検査が可能であることが示された点が新しいです）。

個人的には、SODA (理論CS) の論文にちゃんと触れるのは初めてだったので、どの発表もとても勉強になりました。