STOC2026に参加して4日目にこれを書いている。開催場所はソルトレイキシティで、日本との時差は15時間ある。基本的には夜中の2時に目が覚めて、15時くらいからめちゃくちゃ眠くなる生活が続いている。今回はありがたいことに2本通って2回発表する機会を得たのだが、最後の二日間の夕方のセッションに割り当てられてしまった。一つ目の発表を終えた時点でこれを書いているのだが、発表直前は眠過ぎて寝坊しそうですごい不安で逆に眠れなかった。とりあえず印象的だった内容やその場での自分の思考を思い出しながらメモしているのだが、色々やるべきことを放棄して書いている。ただ、これを書くときに2年前のSTOC参加記を読みおこしているのだが自分で読み直すと意外と楽しいのでこういう参加記はなんとかしてでも残しておくと、未来の自分が楽しめるので頑張ろう（去年のSTOCはプラハですごく楽しかったのに参加記を失念していた）。
最初はワークショップ Algorithmic Frontiers of Graph and Hypergraph Problems via Global Queriesに参加した。まだ時差ボケじゃないので比較的元気な状態で聞けた。グラフ全体が入力として与えられるのではなく、グラフがカットオラクルで与えられる カットクエリモデル と呼ばれる設定で最小カットとかを計算するという話だった。カットオラクルとは、頂点部分集合 $S\subseteq V$ をクエリとして投げると $|E(S,\overline{S})|$ を教えてくれるオラクルで、出来るだけ少ないクエリで最小カットを解きたい。二人目の発表者Puttermanのトークでは、この問題設定の先駆的な結果 Rubinstein, Schramm, Weignberg (ITCS18) の解説をしていた。どうやらカットオラクルを使うと辺を一様ランダムにサンプリングすることができるらしく、これを使ってKargerをする感じらしい。サンプリング辞退は単純な再帰アルゴリズムでできる。ただ、質問したところ固定した頂点に対して接続する辺を一様ランダムにサンプリングできるらしい（？）ので、そもそも次数に比例する確率で頂点を選んでからその接続辺を一様ランダムに選べばもっと簡単にランダムサンプリングできるじゃんとは思った。適当な重みをつけた分布で辺をサンプリングすればカット疎化はできるらしいけどスペクトル疎化は重要な未解決問題らしい。質問したところランダムウォークはサンプリングできるからランダム全域木を何本かサンプリングしてunionをとればspectralを保存できるんじゃなかったっけと思って Kyng, Song, FOCS18 を確認したけど、leverage scoreで重みつけしなきゃらしく、この値の計算が難しそうなのでダメかと思った。あと、カットオラクルは隣接行列 $A$ に対して、二次形式オラクル $(u,v)\mapsto u^\top A v$ にオラクルアクセスできる下でグラフの情報を学習する感じなんだなと思ってたら次の発表者 Mukhopadhyay がまさにそんな感じのことを言ってて確かにそうみなすよなぁと思った。この辺から疲れてきて三つ目の発表はあまり集中できなかった。
ワークショップの終了後はbest paper sessionだった。特に記憶に残っているのは Chen, Chen, Cui, Pires, Stockwell だった。これはboolean function $f\colon\{0,1\}^n\to\{0,1\}$が単調増加関数 ($x\le y \text{ (entry-wise)} \Rightarrow f(x)\le f(y)$) に対する性質検査の結果で、nonadaptive testerではクエリ数の上界と下界は $\widetilde{\Theta}(\sqrt{n})$ であったのだが、nonadaptiveでも $\widetilde{\Omega}(\sqrt{n})$ 必要という下界を示した論文だった。証明はめちゃくちゃ難しそうだが、"monotone"から非常に遠い "anti dictator 関数 $d_i\colon x\mapsto \overline{x_i}$" が重要な役割を果たすらしい。入力全体を適切な手続きに従ってランダムに分割していき、各分割でランダムな $i\sim[n]$ を選び, $d_i$ を貼り合わせて得られる関数を考えるらしい。印象的なbest student paperの発表者はJack Stadeで、art gallaly problemがNPに属することを示す結果だった。平面上の多角形が与えられて、その全てを見渡すために配置すべき警備委員の人数を最小化する問題なのだが、警備員の座標が無理数になる問題例もあるため、NPに属するかはとても非自明な問題である。ところが、座標が無理数であっても適当な形の無理数になるらしく、それをうまく使って証明していた。全くわからなかったがある種の線形不等式系にNP witnessがあるみたいなことを言っててビックリした記憶がある。Stadeといえば最近の論文でETR (existential theory of real; クラスNPの実数版) に対するPCP定理を証明していた。基本的にはDinurのgap amplificationに則るのだが、実数上の誤り訂正符号でPCPP (assignment tester) を構成してアルファベット削減するというところがうまくいかなくて、それをmidpoint codeというBoolean cube上のHadamard codeでなんとかしているのが印象的だった。他にも, Junqiao (Randy) Lin による MIPco=coRE という論文の発表も面白かった。両辺のcoの意味はそれぞれ違っていて、かの有名なMIP*=REではmultiprover同士の相関にある種の制約を仮定するという問題設定を考えているのだが、MIPcoではそれをもっと緩くした (coはcommuteの意) ものを考えるらしい。coREではcoNPと同じ意味のco (complement) なのだが、タイトルの両辺の"co"が違う意味を持つのは面白い。ていうかfull versionが160ページ以上あって、しかも単著ってどういうこと...?
他には Amireddy, Behera, Srinivasan, Sudan, Willumsgaard によるPCPの新しい証明の話が面白かった。PCPのALMSSの証明やDinurの証明は「クエリ数を下げるがアルファベットが増える」「アルファベットを下げる」という二つの種類のPCP (またはPCPP) をめちゃくちゃ巧妙に合成 (composition) して証明するのだが、この論文の手法を使うと一度の合成でPCPを示せるらしい。基本的にはSATの変数や節のindexを二進数で表現したときに得られる $O(\log n)$-variable な関数をmultilinear extensionしてsumcheckとかをすることになる。sumcheckプロトコルではBoolean cube上でのlow-degree polynomialの総和を検証するプロトコルだが、Boolean cubeという構造を少し一般化した空間でもsumcheckみたいなことができるらしい。すごい興味があるので時間があれば読みたい。
この次に聞いたMax Hopkinsによる Dikstein, Hopkins, ,Pitassi, Impagliazzoの発表もめちゃくちゃ面白かった。個人的にはこれがbest paperだと思ってたのだが、去年がHDXだったしそういうのもあったのだろうか。ただ、やはり内容はすごいし応用も広そう。発表後に何度かMaxと話していたのだが、彼はHDXの人という認識だったのだがaverage-case complexityについてもよく知っていて、知識の幅というか守備範囲がひろすぎて感嘆した。
二日目のワークショップも再びグラフのワークショップに参加した。一人目はRobert Krauthgamerで、本とかでしか知らないレジェンドなのだがめちゃくちゃイケおじだった。内容としては、カット疎化に関して、シュタイナー点を許す新しいsparsifierを考えるという内容で面白かった。確か今回のSTOCではその新しいsparsifierに関する下界の結果があったような気がする。二人目はSanjieev Kannaで、彼の最近のマトロイドのブレイクスルーの結果 (FOCS25) とその後の進展 (ICALP26) に関する講演だった。独立オラクルでマトロイドの基を「できるだけ」nonadaptiveに探す問題を考える。普通に要素を一つずつ貪欲に追加していくと全てのqueryがそれ以前のqueryの応答に依存してしまうので、これはめちゃくちゃ適応的である。もうちょっとちゃんと述べると、ラウンド制のオラクルモデルを考える。第一ラウンドではアルゴリズムはクエリ $q^{(1)}_1,q^{(1)}_2,\dots,q^{(1)}_{L_1}$ を作成し、オラクルに投げる。その応答をもとに第二ラウンドでクエリ $q^{(2)}_1,\dots,q^{(2)}_{L_2}$ を作成してオラクルに投げる。さらにその応答をもとに次のラウンドでクエリを作成して... というのを繰り返し、最終的にできるだけ少ないラウンドでマトロイドの基を探してね、という問題である。ただし、一度のラウンドでありうる全てのクエリを投げると必ず1ラウンドで終わるので、基本的には多項式個のクエリを投げて全体で多項式時間で終了するという条件を設ける。貪欲法だと、多項式時間ではあるが、台集合サイズ $n$ に対して $n$ラウンド (各ラウンドで一個ずつクエリを作る)になってしまう。Karp, Upfal, Wigderson, 1988 は、一般のマトロイドに対して $O(n^{1/2})$ラウンドの上界と、$\Omega(n^{1/3}/\log^{1/3} n)$ という情報理論的な下界を示していて、去年のFOCSでKhannaらは $\widetilde{O}(n^{7/15})$ ラウンドの上界を与え、最近の論文 ではとうとう上界が $\widetilde{O}(n^{1/3})$ というnearly-tightな上界を与えた話をしていた。
また、Hair, Sahai によるSVPのdeterministic NP-hardnessの話も面白かった。中身はまったくわからないけどPCPを使ってうまくガジェットを作るらしい。
あと、PKEのworkshopも参加した。最初のSahaiのトークは、基本的にcryptosystemで用いられる困難性の仮定には色々あるが、それを破ることに意義のあるような"useful"なhardnessに基づくPKEを構築しましょうね、みたいな話だった。次のHairのトークはplanted "graph" conjectureに基づくPKEの構築の話をしていた。この問題は大雑把に言えば、固定したexpander graphがランダム二部グラフに含まれるかを判定せよ、という感じの問題であった。
