2.1　学生時代

　前述のように，学部4年時に植松・松本研究室に配属された．研究室に配属されてしばらくたったある日，卒業研究のテーマを決めるためのゼミが開催された．記憶によると，先生方から四つほどテーマが提示された．その中の一つが松本先生から提示された量子暗号に関するテーマであった．当時，量子暗号については新聞の科学記事でキーワードを見聞きしたことがあるだけでほとんど何も知らなかったが，「量子」と「暗号」が掛け合わさった妖しさに魅力を感じ，このテーマを卒業研究として選ぶことにした．

　量子暗号（量子鍵配送）とは，送受信者間で秘密鍵を共有するためのプロトコルで，ランダムに発生させたビット列を光子の偏向に変調させて送る．その過程でもし盗聴者がいたとしても，量子力学の原理に基づき情報の漏えい量を推定できるのが特徴である．そして，情報漏えい量が十分に少ないときは，伝送したビット列に対してディジタルな情報処理を施すことで，安全な秘密鍵を共有することができる．量子暗号は最初の光子を伝送する部分以外はほとんどディジタルな情報処理である．特に，盗聴情報量の推定や秘密鍵生成の手続きは情報理論の守備範囲である．そのような視点から研究を進めていくことで，従来より高い鍵生成レートを有するプロトコルを提案することができ，幾つかの成果を上げることができた^(2)～(4)．

　このような次第で学生時代は松本先生指導の下，量子暗号やそれに関連する情報理論的セキュリティの研究を主に行っていた．量子暗号の研究を始めたきっかけは偶然であったが，学生のうちに量子情報理論に関する基礎的な知識を身に付けることができたのは，その後の研究キャリアにおいて非常に重要なことであったと思う．文献(５)で林先生（名古屋大学・シンガポール国立大学）が述べているように，量子情報理論の知見は，通常の情報理論の研究をする際にも大きなアドバンテージとなるからである．量子暗号の研究をしていたため，林先生とも学生時代から交流があった．そのことがきっかけで，後に有限長解析等について共同研究をさせて頂き様々なことを学んだ．

2.2　徳島大学にて

　博士号取得後は，徳島大学に助教として着任した．当時徳島大学では，大濱先生（現電気通信大学）により情報通信講座が運営されていた．

　情報理論における符号化定理の研究は，通信システムにおいてある通信レートの符号が存在することを証明する符号化順定理と，ある通信レート以上の符号は存在しないことを証明する符号化逆定理に大別することができる．多くの場合，「存在する」ことを証明するより「存在しない」ことを証明する方が困難であり，未解決問題は逆定理が証明できずに未解決となっていることが多い．そのような中，大濱先生は困難なマルチユーザ情報理論における符号化逆定理の研究に熱心に打ち込まれていた．その影響もあり，筆者も次第に逆定理の研究に興味を持っていった．

　ここで，徳島大学にいた頃に行ったマルチユーザ情報理論の研究を一つ紹介したい．マルチメディアコンテンツ配信等の普及により，多数の受信者に対して効率的にデータを送る問題は非常に重要になってきている．特に，動画像の送信において，あるフレームを符号化する際に前のフレームを受信側で補助情報として参照する分散符号化テクニックが注目を集めている．情報理論において，多数の受信者がいる分散符号化の研究は歴史が長く，HeegardとBergerによって1985年に始められた⁽⁶⁾．彼らの研究によって，多数の受信者の間にある種の順序構造を有するモデル（劣化形と呼ばれる）においては，最適な符号化法が明らかにされていたものの，順序構造を有しない一般的なモデルは長い間未解決問題であった．筆者はこの問題の解決の糸口を探るために，順序構造を有しない典型的な場合として，データが二つの統計的に独立なベクトルから成る特殊な場合に取り組み，最適な符号化法を明らかにした⁽⁷⁾．この問題でも困難なのはやはり逆定理の証明であった．この研究を通じて，逆定理を示す大変さ並びに面白さを実感できたように思う．

2.3　メリーランド大学にて

　2013年春から約2年間，日本学術振興会の海外特別研究員制度を使って米国，メリーランド大学に滞在した．現地でのホストはPrakash Narayan先生にお願いした．Narayan先生は情報理論において幅広く研究されているが，特に情報理論的セキュリティを精力的に研究されており，筆者の興味とマッチしたためである．

　Narayan先生のグループは博士課程の学生が二人いるだけだったため，滞在中はディスカッションに多くの時間を取って頂くことができた．密度の濃い研究をするために，学生は一度に二人までしか採らないと決めているそうである．研究グループの大所帯化が進んでいる米国では珍しいことだと思われる．

　メリーランド大学滞在中は当時Narayan先生の学生だったHimanshu Tyagi博士（現Indian Institute of Science, Bangalore）と意気投合し，様々な共同研究を行った．そのうちの一つでは，後述の符号化問題を仮説検定に対応させる方法により（3.2参照），マルチパーティの秘密鍵共有問題に対して，非漸近的な逆定理のバウンドを導出することに成功した⁽⁸⁾．また，その結果を応用することで，暗号理論で活発に研究されている秘匿計算（Oblivious TransferやBit Commitment）に対しても，非漸近的なバウンドを出すことができた．

　Tyagi博士との親交は互いに帰国した後も続き，インドを訪問する機会も何度かあった．インド訪問はカルチャーギャップにより驚きの連続であったが，非常に楽しいものであった．

2.4　東京農工大学にて

　米国から帰国した後，東京農工大学へ異動することとなった．最近は，後述の関数計算の問題（3.2参照）やマルチユーザ情報理論における有限長解析並びに二次オーダ解析に興味を持って取り組んでいる．

　従来の情報理論では遅延を許容し十分に長いブロック長で符号化した際の通信システムの漸近的な性能解析を行うことが多かったが，最近は有限のブロック長での性能解析が盛んに行われるようになってきている^(9),(10)．例えば通信路符号化において，高い信頼性で送ることができるメッセージのビット数は，通信路容量をとしたとき漸近的にのような振舞いをすることはよく知られている．二次オーダ解析とは，許容する誤り確率に対してのように^(注2)，の係数まで求める解析手法であり，有限長性能の良い近似値を与えることから注目を集めている．（有限長解析や二次オーダ解析の詳細については，例えば文献(11)を参照．）

　さて，マルチユーザ情報理論の符号化問題には解析を難しくする二つの要因がある．一つは，マルチユーザネットワークにおいて特殊な符号化法を使うことに起因する補助確率変数の存在である．もう一つは，分散符号化に起因する確率変数間のマルコフ連鎖の条件である．まずは一つ目の困難性を解決するために，筆者はGray-Wynerネットワークと呼ばれる問題に取り組み，最適な二次オーダのレート領域を導出することに成功した⁽¹²⁾．二つの困難性が混在する問題に対する解決の見通しは立っていないものの，難しさの要因が何なのか少しずつ分かってきた．これについては3.3で述べる．

3.1　Single Letter Characterization

　Shannonによって示された通信路符号化定理は，与えられた通信路に対して通信路容量が，入力分布をとしたときの入出力間の相互情報量を用いて^(注3)，

のように通信路を“1回”使用した際の最大相互情報量として表現できることを述べている．さて，この定理はなぜ有用なのだろうか．もし，

のように，通信路を“回”使用した際の最大相互情報量の極限として表現されているだけだったとしたらどうだろうか．情報理論では通称，式(１)のような表現はSingle Letter Characterization（SLC），式(２)のような表現はMulti Letter Characterization（MLC）と呼ばれる．前者はブロック長によらない計算量で通信路容量を計算することができるのに対し，後者を計算するにはブロック長を大きくしながら入力分布に関する最適化問題を解く必要がある．つまり，符号を設計するための指針であるはずの通信路容量を計算するために，符号を実際に作る並の労力が必要になってしまうわけである．このような理由により，情報理論ではSLCを求めることが極めて重要な課題となる．

　さて，情報理論の問題では逆定理においてMLCからSLCを求めるのが困難であることが多い．特にマルチユーザ情報理論の問題では，エントロピーの連鎖則等を極めて技巧的に利用することでSLCは導出される．また，2.4で述べたように，マルチユーザネットワーク特有の補助確率変数をいかに導入するかが困難になる．現在知られているSLCの方法は問題（対象とする通信システム）ごとに経験則に基づき場当たり的に提案されているものがほとんどである．したがって，現在未解決である通信システムの限界を求めるには，よりシステマティックなSLCの導出法の発展が望まれる^(注4)．また，既に漸近的な限界が求まっている通信システムに対しても，有限長解析並びに二次オーダ解析を考える際には，既存のSLCの議論は使えないことが多く，SLCの方法を抜本的に見直す必要があるかもしれない．

　SLCの導出法を探求することの他分野への波及効果についても触れておきたい．例えば，計算機科学におけるcommunication complexityの分野で活発に研究されている直和問題が挙げられる．直和問題では，「ある関数を分散計算するために必要な通信量」に対して，「同じ関数を回まとめて計算するための通信量」がに応じてどのようなオーダで増加するかといったことを考える．そのような問題を解くためのツールとして近年，information complexityと呼ばれる手法が提案されている⁽¹⁵⁾．計算機科学の文献では余り明確には述べられていないが，この手法は情報理論のSLCの考え方に類似のものである^(注5)．また，最近はhypercontractivity係数のテンソル性とSLCの関係も報告されている⁽¹⁹⁾．今後，情報理論の分野で開発されたSLCの導出法が情報理論にとどまらず，他の多くの分野へ展開されることを期待したい．

3.2　Reduction

　Reduction（帰着）とは計算量理論や暗号理論で使われる用語で，あるタスクを解くためのアルゴリズムが与えられたとき，別のタスクを解くためのアルゴリズムをから（効率的に）構築できるならば，「タスクはタスクにreductionされる」といった言い方をする．このような考え方は計算量理論におけるNP完全性の証明や，暗号理論における安全性証明等に頻繁に使われる．例えば，一方向性関数の存在を仮定し構成した擬似乱数生成器の安全性を議論する際には^(注6)，生成した擬似乱数を真性乱数と識別するアルゴリズムがあったとしたら，一方向性関数の逆像を計算するアルゴリズムを構築できてしまうといった論法で証明する．

　上述のようなreductionの考え方は，情報理論において逆定理を示す際にもしばしば有効になる．ある（符号化）問題の符号を用いて別の問題の符号が構成できたとしよう．つまり，問題の方が問題よりある意味で簡単であると言えたとしよう．すると，適当な尺度の対応付けを行うことで，問題の限界を問題の限界で抑えることができる．このような論法で最も成功を収めているものの例としては，通信路符号化におけるmeta converse法が挙げられる^(注7)．Meta converse法では，通信路符号化（問題）を統計学における仮説検定（問題）に関連付けることで逆定理を導く．与えられた通信路符号化のための符号を用いて，実際の通信路と，通信路容量が0である仮想的に与えられた通信路との検定を行うのである．ここで，問題として解析が容易なもの（少なくとも問題よりは解析がしやすい問題）を選ぶことがポイントである．2.3で述べた秘密鍵共有のバウンドも同様な論法で導出されている．また，このような論法は，複数回繰り返すことも有効である．例えば，先の論文(８)では，秘匿計算の問題におけるプロトコルが存在したとしたら，秘密鍵共有のプロトコルを構築することができ，その鍵共有プロトコルから仮説検定法が構築できるといった二段構えのreductionによって，秘匿計算のバウンドを導出している．

　Reductionの考え方が有効な他の問題としては，分散関数計算の問題が挙げられる．この問題では，観測データを分散符号化によって通信することで，復号器側で観測データの関数値を計算することを目的とする．関数計算の問題では復号器で観測データそのものを復元する必要がないため（関数の値域は1bitだけの場合もある），通常の符号化問題において逆定理を示すためのテクニックはほとんど役に立たない．特に，Ahlswede-Csizsárによって示されたsensitiveな関数族に対する結果は証明が非常に難解で⁽²⁰⁾，後にEl Gamalによる平易な証明が示されていたものの⁽²¹⁾，理解するのに非常に苦労した．この問題は2014年頃から興味を持ち始め，葛岡博士（和歌山大学）と共同で研究を開始した⁽²²⁾．そしてようやく最近になって，ある種の構造を有する関数族に対しては，Slepian-Wolf符号化（問題）から関数計算（問題）へのreductionを示すことで，非常に直感的で簡明な証明を与えることができた⁽²³⁾．

　以上幾つか例示してきたように，reductionは逆定理を示す際に非常に有効な考え方である．このような方法ではreductionの段階は操作的な議論なため，情報理論でよく考えられる定常無記憶性等を仮定せずに行えるという利点もある^(注8)．今後このような方法はますます重要になってくるのではないだろうか．本節の冒頭で述べたように，reductionは計算機科学や暗号理論で頻繁に使われる考え方である．したがって，それらの分野からアイデアを取り入れることで，情報理論のテクニックは更に発展することが期待できる．その一方で，情報理論で発展したテクニックを他の分野の問題に適用してみるのも面白い．

3.3　Isoperimetric問題

　Isoperimetric問題（等周問題）とは，「面積が一定の下で周囲の長さが最小になる閉曲線は何か」といった古代から考えられていた幾何学の問題で，円が最適解になることはよく知られている^(注9)．情報理論でもこのような極値問題はしばしば登場する．ここではそのような問題の中から，筆者が最近興味を持っているものを一つ紹介したい．

　通信路を反転確率がの二元対称通信路とする．与えられた入力集合に対して，できるだけ小さな出力集合によって，任意のを通信路で送った際に高確率で受容できるようにしたい．そこで，与えられたに対して，のによるimage sizeとして

のように定義する．このとき，入力集合のサイズが一定の下でimage sizeはどのように表現できるのだろうか．このような問題はimage size characterizationと呼ばれ^{(14) (注10)}，マルチユーザ情報理論における符号化問題の強逆定理を示すための道具として導入された^{(25) (注11)}．漸近的な振舞いについては解決済みで，与えられたに対して，入力集合が

というレート制約を満たす下で，image sizeは

のような不等式を満たすことが知られている．ただし，とは二元エントロピー関数とその逆関数，は二元畳込みである．また，式(５)の不等式は，入力集合として半径の次元ハミング球に取ることで等号が達成される．ここで，をの面積，をの周囲の長さとみなすと，上記の結果は通信路のimage sizeに関するisoperimetric問題と考えることもできる．

　上記のimage size characterization問題をより精密な形で解くことができれば，マルチユーザ情報理論における符号化問題に対して，より精密な解析を行えるのではないかと考え，筆者はこの問題に興味を持った．この問題はisoperimetric問題の一種と考えると，式(５)のような漸近的な場合だけでなく，有限のに対してもハミング球が最小のimage sizeを持つのではないかと予想したくなる．仮に全てのでは成り立たないとしても，が各で満たされているとき，

のような二次オーダのisoperimetric不等式は成り立つのではないだろうか．

　Isoperimetric問題はもっともらしい主張にもかかわらず証明が困難なのが常である．式(６)を証明するためにいろいろな手を試してみたが，今のところ証明の見通しは立っていない．式(５)を証明する際には，blowing-up補題と呼ばれるmeasure concentration⁽²⁸⁾のテクニックが重要な役割を果たすが，式(６)を証明するには不十分なようである．したがって，マルチユーザ情報理論における精密な解析を行うには，blowing-up補題に代わる新しいテクニックの発展が望まれる．

　式(６)の成否は明らかではないものの，組合せ論において以下のような類似の結果が知られている．二元対称通信路の代わりに，通信路では個以下の任意の誤り（反転）が起きるとしよう．そして，を送ったとき，出力を必ず受容できるようにを取りたいとする．すると，image sizeはに含まれるベクトルとハミング距離が高々以下のベクトルを全て集めた集合のサイズになる．このとき，の下で，

が成り立つ．この結果はHarperのvertex isoperimetric不等式と呼ばれている^(注12)．

　タイプの理論をはじめとし，情報理論において組合せ論的な方法が有効なことはよく知られている．その一方で，情報理論で発展した手法が組合せ論においても有効であるといった結果も報告されている^(26),(27)．例えば，前述の不等式(７)のedge版であるHarperのedge isoperimetric不等式は，結合エントロピー間の不等式であるHanの不等式を使うと容易に示すことができる（文献(28)4.4節）．今後は，情報理論と組合せ論はますます交流が盛んになっていくのではないだろうか．