修士論文

2015年度

• 劉鵬宇, Local Search Approaches for the Hospitals/Residents Problem (研修医配属問題に対する局所探索アルゴリズム).
• 江原昌吾, Average Complexity of Merge-Based Sorting Algorithms (マージ操作を基本とする整列アルゴリズムの平均複雑さ).
• 岡智洋, Algorithms for Graphs Parameterized by the Number of Large Degree Vertices (次数の大きな頂点の個数をパラメータとしたグラフに対するアルゴリズム).
• 森本翔大, Three-Server Problems on Two Lines (2直線上の3サーバ問題).

2014年度

• 鈴木洋介, The Number of Creases in the ε-Fold-and-Cut Problem (ε折り切り問題における折り筋の本数).
• 酒井隆行, Improved Exponential Algorithms for Max SAT (最大充足可能性問題に対する指数時間アルゴリズムの改良).
• 清水さよ, Graph 3-Colorability and Normalized Laplacian Eigenvalues (グラフの3彩色可能性と正規化ラプラシアンの固有値).
• 田中翔, Local Conditions for Non-Nash Equilibrium in PageRank Games on Undirected Graphs (無向グラフPageRankゲームにおける非ナッシュ均衡をもたらす局所条件)
• 津山竣太郎, Randomized Algorithms for Reconstructing Strings from Substrings (部分列からの列再構成問題に対する乱択アルゴリズム).

2013年度

• 李旼宣, Finding Witnesses for Stability in the Hospitals/Residents Problem (研修医配属問題における安定性の証拠探索).
• 程隆, Multiple Nash Equilibria of Atomic Splittable Selfish Routing Game (分割可能な利己的ルーティングゲームに対する複数のナッシュ均衡).
• 上田孝弘, Algorithms for Sublinear-Time Assignment for the Cake Cutting Problem (ケーキ分割問題に対する劣線形時間割当てアルゴリズム).
• 楠本充, Testing Forest-Isomorphism in the Adjacency List Model (隣接リストモデルにおける森の同型性検査).
• 田村隆太郎, Lower Bounds for AC⁰ Circuits Computing Clique and Modulo Functions (クリーク及び剰余関数を計算するAC⁰回路の下界).
• 曹洋, Distribution-Free k-Edge-Connectivity Testing for Bounded Degree Graphs (定数次数グラフに対する重み分布によらないk枝連結性検査).

2012年度

• 王堯, On the Size of Matrix Forcing Monotone Submatrix (単調部分行列を必然に有する行列の規模について).
• 稲田陽光, Mixing Time with Guaranteed Minimum for Various Quantum Walks (様々な量子ウォークに対する最小値保証ミキシングタイム).
• 堺谷光, Design and Analysis of Winning Strategies for Variants of Harary's Generalized Tic-Tac-Toe (ハラリィの一般化三並べの変種に対する必勝法の設計と解析).
• 笹沼亮介, Design and Analysis of Randomized Algorithms for the Two Server Problem on the Line (直線上2サーバ問題に対する乱択アルゴリズムの設計と解析).
• 古川勇輔, Competitive Analysis of Action Algorithms against Multiple Price Omniscient Auction (オークションアルゴリズムの複数価格全知オークションに対する競合比解析).
• 朱傲, On-line Stable Marriage Problems with Limited Revokes (制限された改竄を許すオンライン安定結婚問題).
• 井下貴雄, Improving Man-Optimal Stable Matchings in the Stable Marriage Problem. (安定結婚問題における男性最良安定マッチングの改善).

2011年度

• 長尾篤樹, Lower Bounds for the Complexity of Tree Evaluation Problems (木構造関数値評価問題の計算複雑さに対する下限の研究).
• 西田尚平, Quantum Query Complexity for Evaluation of Depth-2 AC⁰ Circuits (2段AC⁰回路値評価問題の量子質問計算量).
• 朴大地, Verifying Nash Equilibria in PageRank Games on Undirected Web Graph (無向ウェブグラフ上のPageRankゲームにおけるナッシュ均衡判定).
• 八田 直樹, Online Algorithms Optimally Self-tuning to Congestion for Power Management Problems and Their Analyses (消費電力問題における混雑度に最適に追従するオンラインアルゴリズムとその解析).

2010年度

• 太田圭亮, Flow Time Analysis for Online Elevator Problems (オンラインエレベータ問題の待ち時間解析).
• 後藤順一, An Extension of the Poset Game Periodicity Theorem (半順序集合ゲーム周期性定理の拡張).
• 添島琢己, Exact Algorithms for the Traveling Salesman Problem on 4-Regular Graphs (4-正則グラフの巡回セールスマン問題に対する厳密アルゴリズム)
• 前田圭介, Exact Algorithms for Dualization of Monotone DNF Formulas (単調DNF論理式の双対化に対する厳密アルゴリズム).
• 謝明敏, Digital-Goods Auctions with Purchase Probability (購入確率を導入したデジタル商品オークション).

2009年度

• 木下直紀, Inapproximability of Systems of Linear Equations over Two Variables (2変数の線型方程式系の近似困難性).
• 髙井唯史, Improved Randomized Algorithms for 3-Satisfiability. (3充足可能性問題に対する乱択アルゴリズムの改良).
• 照山順一, Quantum query complexity of counterfeit coin problems (偽コイン問題の量子クエリ計算量).
• 陳晶, Online bin packing using (1,1) and (2,R) bins ((1,1) と (2,R) ビンを使うオンラインビンパッキング).

2008年度

• 市場孝之, Competitive Auctions with Collusion (正直なオークションと談合).
• 濱田浩気, The Hospitals/Residents Problem with Quota Lower Bounds (配属人数下限付き研修医配属問題).
• 吉田悠一, Constant-Time Algorithms for Graph Problems (グラフの問題に対する定数時間アルゴリズム).
• 吉永直生, Restriction of Boolean Circuits and Nonlinear Lower Bounds (制限された論理回路に対する非線形下限).
• 徐ユン頴, Online Algorithms for Packing Splittable Items with Cardinality Constraints (基数制限を付き分割可能なアイテムをパッキングするオンラインアルゴリズム).

2007年度

• 門下雅一, Combinatorial Problems on Unit Disk Graphs with Small Area (小領域上の単位円盤グラフにおける組み合わせ問題).
• 高田智史, Computational Complexity of Weighted Poset Games (重み付き半順序集合ゲームの計算量).
• 田坂豊隆, Online Auctions for Digital Goods (デジタル商品のためのオンラインオークション).
• 中島拓也, Exact algorithms for the traveling salesman problem in restricted graphs (制限されたグラフ上での巡回セールスマン問題に対する厳密アルゴリズム).
• 宮川博光, Enumeration of Isolated Bicliques (孤立2部クリークの列挙).

2006年度

• 井上嵩浩, Discrete-time Quantum Walks on Several Graphs (いくつかのグラフにおける離散時間量子ウォークについて).
• 角田大輔, Truthful Auctions with Limited Range of Bids (入札額の範囲が制限された正直なオークション).
• 脊戸和寿, Constant Depth Circuits for Symmetric Boolean Functions (対称関数を実現する定数段数回路について).
• 山内直哉, An Improved Approximation Algorithm for the Stable Marriage Problem and Its Tight Analysis (安定結婚問題に対する近似アルゴリズムの改良とその厳密な解析).

2005年度

• 阿武孝文, Maximum Power Consumption Ratio on Two-Level Circuits (組合せ二段回路の最大動作率).
• 川原純, Automated Competitive Analysis of Online Algorithms (オンラインアルゴリズムにおける競合比の自動解析).

2004年度

• 沖田正樹, Routing Algorithms for Flat Networks (平坦なネットワークに対するルーティングアルゴリズム).
• 大隅剛史, Enumerating Isolated Cliques (孤立したクリークの列挙).
• 杉原堅也, Maximum-Cover Source-Location Problems (最大被覆供給点配置問題).
• 花谷陽一, Instance Generation of Graph Coloring and Satisfiability (彩色問題および充足可能性問題に対する例題生成).
• 増田裕之, Quantum Identification of Boolean Oracles (2値オラクルの量子同定).

2003年度

• 飯尾佳之, On Traveling Plainer Graphs by Quantum Walk (量子ウォークによる平面グラフの横断について).
• 今村友和, Approximation Algorithms for the Vertex Cover Problem (最小頂点被覆問題の近似アルゴリズム).
• 正西申悟, Automated Competitive Analysis of Online Problems (オンライン問題の競合比解析の自動化について).

2002年度

• 玉置卓, Improved Algorithms for CNF Satisfiability Problems (和積形論理式の充足可能性問題に対するアルゴリズムの改良).
• 田村武幸, Minimum Fragment Sets for Fixing DNA Probe Sequences (DNAのプローブ順序固定に必要な最小フラグメント集合).
• 藤原洋志, Average-Case Competitive Analyses for Online Problems (オンライン問題に対する平均的競合比の解析).
• 柳沢弘揮, Approximation Algorithms for Stable Marriage Problems (安定結婚問題に対する近似アルゴリズム).
• Rudy Raymond Harry Putra, Quantum Query Complexity of Noisy Oracles (ノイズ付き量子オラクルの質問回数について).

2001年度

• 梅本潤, Linear Programming Relaxations of Max-Cut (Max-Cutの線形計画緩和).
• 武富史郎, Multi-Solution Models for Online Problems (複数個の解候補を保持できるオンライン問題).
• 西村知洋, Approximability of Partial MAX SAT and Related Problems (部分MAX SAT及びその関連問題の近似可能性).
• 松田健, Approximation Algorithms for Maximum Power Consumption Problems (最大消費電力問題に対する近似アルゴリズム).

2000年度

• 天野正己, On the space-efficiency of quantum computational models (量子計算モデルの領域計算量について).
• 小田真一郎, Tree-Like Resolution proofs for Pigeonhole formulas (鳩の巣原理に対する木状導出原理の証明サイズの解析).
• 関口隆昭, Hierarchical Algorithms for QoS Multicast Routing (QoS保証マルチキャストルーティングの階層化アルゴリズム).
• 米澤弘毅, Competitive Analyses of the CNN Problem (CNN問題の競合比解析).

1999年度

• 河合大輔, Vectorized Local Search for CNF Satisfiability (SATに対する局所探索法のベクトル化).
• 高瀬俊郎, Expotential Sepalation on the Length of Oblivious and Non-Oblivious BPs (順序付きプログラムと順序なし分岐プログラムの計算時間における指数的分離).
• 盛田保文, Intractability and Approximability of Stable Marriage Problems (安定結婚問題の複雑さと近似可能性).
• 吉廣卓哉, Traffic Sensitive Adaptive Routing on DiffServ Framework (DiffServフレームワークにおける通信状況に応じた適応ルーティング).

1997年度

• 農添三資, Optimal Variable Ordering of Binary Decision Diagrams for Threshold and Monotone Functions (しきい値関数と単調関数を表す2分決定グラフの最適な変数順序).
• 坊野博典, Improved Upper Bounds for the Unsatisfiability Threshold in Random CNF Formulas (ランダムに生成された和積形論理式が充足不能となるしきい値の上限の改良).