square1001 🍎 retweeted
✏️ニュースリリース
理論計算機科学のトップ会議「FOCS 2026」で国立情報学研究所から論文3本が採択 うち四色定理に新たな証明を与えた論文が Best Paper を受賞
nii.ac.jp/news/release/2026/…
大学共同利用機関法人 情報・システム研究機構 国立情報学研究所の研究者が関わる論文が、理論計算機科学分野のトップカンファレンスである「The 67th Annual Symposium on Foundations of Computer Science (FOCS 2026)」 において、3本が採択され、うちNII情報学プリンシプル研究系の河原林 健一教授らの四色定理に関する論文が Best Paper を受賞しました。
square1001 🍎 retweeted
最近は社会に目を向ければ、世の中の目は厳しいでしょう。我々の大学そのものや、大学院生の研究生産性について、疑念を持っている人が多いのを認識しています。
国民の血税で研究が支えられているのであれば、その期待に応える責任がある、というプレッシャーは持っています。
square1001 🍎 retweeted
これはただの “40 年未解決だった問題” ではない。
文字列アルゴリズム・近似アルゴリズムの多くの教科書に載っている中心的予想である。
これは世界を動かす大きな論文だ!
arxiv.org/abs/2609.01365
新作出ました!
すべての入力文字列を部分文字列として含む最短の文字列を求める最短超文字列問題において、単純な貪欲法の解が最適解の2倍より長くなることはない、という約40年間未解決だった予想に対し、(AIの力を借り)初の反例を与えることで予想を解決しました。
square1001 🍎 retweeted
🎊国際会議 SODA 2027 採択!🎊
「どんな地図も 4 色あれば塗れる」という四色定理は有名ですが、実際にはどの色も全体の半分未満でしか使わずにバランス良く塗れる、ということを証明する論文を書きました!
一般向けの研究紹介記事も書きましたので、ぜひお読みください!
qiita.com/square1001/items/4…
皆様、こちら、Qiita のトレンドに載せて一般に広めたいので、ぜひ LGTM お願いします! 私は一般に広める価値のある研究だと思っています。
teapawt.org/square10011/status/210…
🎊国際会議 SODA 2027 採択!🎊
「どんな地図も 4 色あれば塗れる」という四色定理は有名ですが、実際にはどの色も全体の半分未満でしか使わずにバランス良く塗れる、ということを証明する論文を書きました!
一般向けの研究紹介記事も書きましたので、ぜひお読みください!
qiita.com/square1001/items/4…
【🎉SODA2027 採択🎉】
The Balanced Four-Color Theorem
arxiv.org/pdf/2607.13025
地図を 4 色で塗る "四色定理"。150 年の歴史がある難問ですが、それについて、できる限り色をバランスよく使う新手法を考案しました。一般向けの解説を書いたので、ぜひお読みください。
qiita.com/square1001/items/4…
square1001 🍎 retweeted
【100 年かかる問題を 0.01 秒で解く「アルゴリズム」】
ICPC世界大会2位の競技プログラマーであるE869120さんに、アルゴリズムの奥深さが学べる記事を寄稿していただきました。
記事後半では、プログラミング的思考力を鍛えられるパズルもお楽しみいただけます。
mirapub.or.jp/2026/10/02/alg…
square1001 🍎 retweeted
自分は 2015 年に競プロを始めたが、その後のそれこそ 2018 年とかに競プロを始めて強くなった人で、自分よりも社会の最前線で世の中に貢献している人を何人も見てきたし、きっと多くがそうなんだと思う。
自分は遅いが、何が何でも使命を果たさなければならないんだ。
皆さん、OpenAI が未解決問題を次々と解いている今こそ、ミレニアム未解決問題の最強格「P 対 NP 問題」について知るべきです。
以下のスライドでわかりやすく解説されています。最初の概要部分は 10 分で読めますので、皆さんぜひご覧ください。
speakerdeck.com/e869120/p-vs…
【告知】
本日、国際会議 #ESA2026 にて以下の採択論文の発表を行います (双子の @square10011 と一緒に取り組んだ Student Paper です!)。
arxiv.org/abs/2604.27690
発表は 16 時 10 分頃からです。会場に来られている皆さんはぜひご覧ください。
【記事公開】
今話題の「競技プログラミング」とは、一体どのようなものでしょうか。
高校生・中学生向けにわかりやすく書いてみました。興味のある方は是非お読みください。
e869120.hatenablog.com/entry…















