ABSTRACT
| 8月3日（木） | 8月4日（金） |
佐久間 淳筑波大学
Differentially Private Chi-squared Test by Unit Circle Mechanism（ICML'17）
差分プライバシーを保証する独立性カイ二乗検定のメカニズムを提案する｡既存の差分プライバシーを保証する検定手法では主にtype-I errorの制御が検討されていた｡この研究では､これに加えて､差分プライバシーを保証する検定メカニズムのtype-II errorを解析した｡この解析結果および検定統計量の幾何的性質に基づき､メカニズムである単位円メカニズムを提案する｡既存の出力摂動法においては､type-II errorを支配する項のサンプル複雑度がO(1)であったところ､提案法ではこれをO(exp(−√N))(Nはサンプル数)に改善された｡さらに､単位円メカニズムを疎ベクトル法や指数メカニズムと組み合わせることで､差分プライバシーを保証する多重カイ二乗検定メカニズムを構成することができることを示した｡これらの手法は差分プライバシーを保証しつつfamily-wise error rateを制御できる初めて多重検定メカニズムである｡
坂井 智哉東京大学
正例とラベルなしデータからの分類に基づく半教師付き分類（ICML'17）
ラベル付けをしたデータを大量に収集するには多くの労力とコストがかかる。一方、ラベルのないデータは比較的容易に集めることができる。そこで、ラベルなしデータを活用することで、少ないラベル付きデータから高い分類精度を得ようとする半教師付き分類が研究されてきた。しかし従来の手法は、データがクラスタ構造を持つといった、データ分布に対する強い仮定を必要とする。そのため、そのような仮定が成り立たない現実のデータでは、期待した性能が出ないという問題があった。そこで本発表では、従来手法が要求するようなデータ分布に対する仮定を必要としない半教師付き分類手法を提案する。
胡 緯華東京大学
Learning Discrete Representations via Information Maximizing Self-Augmented Training（ICML'17）
データの離散表現を教師なしで学習することは、非常に重要で一般的なタスクであり、クラスタリングとハッシュ学習を内包するタスクである。本講演では、ニューラルネットワークを用いた離散表現学習の手法を提案する。提案法では、データと離散表現の相互情報量を最大化しつつ、データの微小な摂動に対して離散表現が不変になるように学習を行う。多くのベンチマークデータを用いた実験を通して、提案法が、クラスタリングとハッシュ学習でstate-of-the-artの性能を達成することを示す。
Emtiyaz Khan理化学研究所
Approximate Bayesian Inference in large and complex models (such as deep generative model and spatiotemporal models) is computationally challenging. Modern methods rely on stochastic-gradient algorithms and can scale to huge datasets, but they do not always lead to computationally efficient and modular updates. In this work, we present the Conjugate-computation Variational Inference (CVI) algorithm. CVI is derived using proximal-gradient methods. We show that CVI is a generalization of existing SG methods and message passing algorithm (e.g, VMP and SVI). Overall, CVI enables efficient, modular, scalable, and convergent natural-gradient updates for models that contain probabilistic graphical models and deep generative models.
小林 佑輔筑波大学
A Weighted Linear Matroid Parity Algorithm（STOC'17）
マトロイドパリティ問題はマッチング問題とマトロイド交叉問題の共通の一般化として1970年代に導入された問題である。この問題は一般のマトロイドにおいては指数回のオラクル呼び出しを必要とするが、線形マトロイド上の問題に対しては Lovasz (1980) が多項式時間アルゴリズムを与えている。マッチングアルゴリズムやマトロイド交叉アルゴリズムは重み付き問題へ拡張がなされているのに対して、重み付きの線形マトロイドパリティ問題に対する多項式時間アルゴリズムは30年以上知られていなかった。本研究では、重み付き線形マトロイドパリティ問題に対して初の多項式時間アルゴリズムを与える。提案アルゴリズムは、多項式行列の Pfaffian を用いた定式化に基づくものであり、重み無し線形マトロイドパリティ問題に対する Gabow and Stallmann (1986) の増加道アルゴリズムを基にした主双対アルゴリズムである。本研究は東京大学の岩田覚教授との共同研究である。
藤井 海斗東京大学
Budgeted stream-based active learning via adaptive submodular maximization（NIPS'16）
能動学習と呼ばれる機械学習の設定では、ラベルを付与するサンプルを適応的に選ぶことによって、訓練データの作成コストを下げることができる。能動学習には、プール型とストリーム型と呼ばれる二種類の設定がある。これまで、適応的劣モジュラ性を満たす目的関数を設計することで、プール型能動学習に対して理論保証のあるアルゴリズムが設計されてきた。しかし一方で、ストリーム型能動学習に対する同様のアプローチは知られていなかった。本研究では、方策適応的劣モジュラ関数という新しい関数のクラスを提案する。方策適応的劣モジュラ性は、適応的劣モジュラ性よりも強い性質だが、応用で用いられる適応的劣モジュラ関数のほとんどで成り立っている。この性質を用いて、既存のプール型能動学習に対するアルゴリズムをストリーム型能動学習に対するアルゴリズムへと変換する汎用的な手法を提案する。
吉田 悠一国立情報学研究所
Minimizing Quadratic Functions in Constant Time (coauthored with Kohei Hayashi)（NIPS'16）
二次関数に対するサンプリングに基づく最適化手法を提案する。本手法は以下のn次元二次関数最小化問題をnに依存しない定数時間で近似的に解く: z*=min_{v∈R^n}<v, Av>+n<bv, diag(d)v>+n<b,v>。ここでA ∈ R^{n×n}は行列、d, b ∈ R^nはベクトルである。近似値zが確率1-δで|z−z*|=O(ϵn^2)となるサンプル数k(δ,ϵ)を理論解析により示す。数値実験により実際の性能(精度と実効時間)が高いことを示す。
Man-Kwun Chiu国立情報学研究所
High Dimensional Consistent Digital Segments（SoCG'17）
We consider the problem of digitalizing Euclidean line segments from Rd to Zd. Christ et al. (DCG, 2012) showed how to construct a set of consistent digital segments (CDS) for d = 2: a collection of segments connecting any two points in Z2 that satisfies the natural extension of the Euclidean axioms to Zd. In this paper we study the construction of CDSs in higher dimensions. We extend their result to higher dimensions. Specifically we show that any total order can be used to create a set of consistent digital rays CDR in Zd (a set of rays emanating from a fixed point p that satisfies the extension of the Euclidean axioms). Then we use the same approach to create CDS in Zd, and observe that it only works in some cases. We fully characterize for which total orders the construction is consistent (and thus gives a CDS). In particular, this particular positively answers the question posed by Christ et al.
大坂 直人東京大学
Portfolio Optimization for Influence Spread（WWW'17）
ソーシャルネットワーク上の「情報拡散」現象は、マーケティング戦略などへの応用可能性から解析の重要性を増してきている。バイラルマーケティングと呼ばれるマーケティング戦略は、高影響力集団から始まる口コミを通し、高広告効果を狙う。影響最大化はこのバイラルマーケティングに動機づけられたグラフ上の離散最適化問題である。情報拡散が確率的現象であるため、影響力＝「情報が伝わる人数の期待値」の最大化を目標とする。期待値は最適化の観点で望ましい性質を有する一方、実用上は“無視できない確率で情報流布失敗に繋がる”といった好ましくない事態に陥る可能性（リスク）がある。そこで本研究は期待値の代わりにConditional Value at Risk (CVaR)という金融経済・保険数理のリスク尺度を導入し、CVaR最大化のための新たなポートフォリオ最適化手法を提案した。計算機実験により、提案手法がリスク回避の意味で既存の期待値最大化手法の性能を大きく上回ることを示した。
稲荷場 渉東京大学
Random-Radius Ball Method for Estimating Closeness Centrality（AAAI'17）
実世界のネットワークの解析において、重要度の高い頂点を特定することは最も基礎的な処理の一つである。頂点の重要度を測る指標は中心性と呼ばれ、さまざまな観点から研究がなされてきた。ネットワーク中の距離情報を用いた中心性の多くは非連結なネットワークの扱いなどに問題を抱えていたが、近年提案された調和中心性 (harmonic centrality) はそういった問題を自然に解決する優れた指標である。そこで本研究では、調和中心性を含む中心性の族に対し、高速に精度良く推定を行える新たな手法を提案する。提案手法は実装が容易であり、推定の誤差や計算量に関する理論的な保証を備えている。また実ネットワークを用いた評価実験によって、提案手法の有効性も示す。
原 聡国立情報学研究所
特徴選択のためのLasso解列挙（AAAI'17）
Lasso解を列挙する方法を提案する。通常のLassoでは大域解を一つ見つけて、そこで選ばれた特徴量が重要な特徴量であると解釈される。しかしながら、この方法ではLasso解に含まれなかった重要な特徴量を見落とす恐れがある。これに対し、提案手法ではLasso解を複数列挙することで多様な特徴量を見つけることができ、結果的に見落としを避けることができる。本研究ではまたLasso解列挙により真に重要な特徴量が復元できることを示す。最後に、遺伝子データとテキストデータでの実験において、提案法を使うことで実際に多様な特徴量が見つけられることを示す。
相馬 輔東京大学
Regret Ratio Minimization in Multi-objective Submodular Function Maximization（AAAI'17）
劣モジュラ最大化は、機械学習やネットワーク解析などの分野で盛んに研究されてきた。実際の意思決定においては、最適化したい基準は1つではなく複数ある場合が多い(多目的最適化)。一般に多目的最適化では、全ての目的関数を同時に最大化する解があるとは限らず、多数の Pareto 最適解が存在する。また、これらの Pareto 最適解を事前に全て計算して保持するのは困難である。本研究では、リグレット比と呼ばれる指標を多目的劣モジュラ最大化に対して拡張し、リグレット比の小さな実行可能解集合を求めるアルゴリズムを提案する。本研究はNIIの吉田悠一准教授との共同研究である。
伊藤 伸志NEC データサイエンス研究所
Large-Scale Price Optimization via Network Flow（NIPS'16）
This paper deals with price optimization, which is to find the best pricing strategy that maximizes revenue or profit, on the basis of demand forecasting models. Though recent advances in regression technologies have made it possible to reveal price-demand relationship of a number of multiple products, most existing price optimization methods, such as mixed integer programming formulation, cannot handle tens or hundreds of products because of their high computational costs. To cope with this problem, this paper proposes a novel approach based on network flow algorithms. We reveal a connection between supermodularity of the revenue and cross elasticity of demand. On the basis of this connection, we propose an efficient algorithm that employs network flow algorithms. The proposed algorithm can handle hundreds or thousands of products, and returns an exact optimal solution under an assumption regarding cross elasticity of demand. Even in case in which the assumption does not hold, the proposed algorithm can efficiently find approximate solutions as good as can other state-of-the-art methods, as empirical results show.
矢部 顕大NEC データサイエンス研究所
Robust Quadratic Programming for Price Optimization（IJCAI'17）
価格最適化の目的は、売上高を最大化する価格戦略を求めることである。機械学習の発達により価格と売上間の複雑な関係をモデル化することが可能となったが、一方で機械学習により生み出される統計的誤差の影響を最適化において取り扱う必要性が生じた。この論文では、価格最適化における予測誤差が行列正規分布で表されることを示し、この誤差に対するロバスト2次最適化アルゴリズムを提案する。ロバスト最適解が持つ漸近的な確率保証も提示する。実験において、提案するロバスト最適化機は安全で高効率な価格戦略を求めることができることを示す。
石畠 正和北海道大学
Statistical Emerging Pattern Mining with Multiple Testing Correction（KDD'17）
Emerging patterns are patterns whose support significantly differs between two databases. We study the problem of listing emerging patterns with a multiple testing guarantee. Recently, Terada et al. proposed the Limitless Arity Multiple-testing Procedure (LAMP) that controls the family-wise error rate (FWER) in statistical association mining. LAMP reduces the number of ``untestable'' hypotheses without compromising its statistical power. Still, FWER is restrictive, and as a result, its statistical power is inherently unsatisfying when the number of patterns is large.
On the other hand, the false discovery rate (FDR) is less restrictive than FWER, and thus controlling FDR yields a larger number of significant patterns. We propose two emerging pattern mining methods: the first one controls FWER, and the second one controls FDR. The effectiveness of the methods is verified in computer simulations with real-world datasets.
丸茂 直貴NTTコミュニケーション科学基礎研究所
SVD-Based Screening for the Graphical Lasso（IJCAI'17）
データの共分散行列から特徴量間のスパースな相関を推定する Graphical Lassoは様々な分野に応用を持つ重要な問題だが、特にデータサイズが大きい場合、既存手法では計算時間が膨大になってしまう。そこで、本論文では Graphical Lasso を高速に解く手法 Sting を提案する。Sting ではデータ行列の特異値分解を用いることによって、相関が非ゼロになりうる部分を事前に特定（スクリーニング）し、非ゼロになりうる箇所のみ反復法でその値を求める。共分散行列の計算を避けていること、スクリーニングにより無駄な反復を避けていることで、Sting は高速になっている。また、これは最適保証スクリーニングであるため、Sting は既存手法と同様、必ず最適解に収束する。実験により、提案手法が既存手法より数倍から100倍程度高速であることを確認した。
岩田 具治NTTコミュニケーション科学基礎研究所
Multi-view Anomaly Detection via Robust Probabilistic Latent Variable Models（NIPS'16）
多情報源（マルチビュー）データにおける異常を検出するための潜在変数モデルを提案する。多情報源データでは情報源間の関係が一貫していない事例を異常とみなす。例えば、多言語コーパスにおいて、ある言語だけ他の言語と異なる内容となっている文書を異常とみなす。提案モデルでは、正常事例は全情報源が１つの共通する潜在ベクトルから生成されると仮定する。一方、異常事例は情報源によって異なる潜在ベクトルから生成されると仮定する。ディリクレ過程を用いて各事例における潜在ベクトル数を推定することにより、異常スコアを算出する。提案モデルは、確率的正準相関分析を頑健化したモデルと見なすこともできる。
熊谷 充敏NTTセキュアプラットフォーム研究所
Learning Latest Classifiers without Additional Labeled Data（IJCAI'17）
様々なドメインにおいて分類器の性能は経年劣化してしまう。その対策として、ラベルありデータを用いた分類器の更新が有効であるが、データへのラベル付与は一般に専門家が人手で行う必要があるため、ラベルありデータの収集コストは高くなる。そこで、本研究では、ある時刻までに収集されたラベルありデータに加え、それ以降の時刻に収集した比較的収集が容易なラベルなしデータを用いて、最新時刻のデータに適した分類器を学習する手法を提案する。具体的には、経年劣化の主要因である、(1) 学習フェーズでは現れなかった新たな特徴量の増加、および、(2) 学習/テストでのデータ分布の変化という2つの問題について考え、両問題を同時に解決する分類器学習法を提案する。人工データおよび実データを用いた実験を通じて、提案法の有効性を示す。
横井 祥東北大学
Learning Co-Substructures by Kernel Dependence Maximization（IJCAI'17）
ペアをペアたらしめている部分構造対を見つけるタスクを提案し、これを教師なしで解く。提案手法では、目的関数に Hilbert--Schmidt independence criterion (HSIC) を用い、これをエネルギー（のマイナス）だと思って Gibbs分布の密度の大きい点を MCMCで探す。実験では「事態間関係知識をコーパスから獲得するとき元文中のどの単語を知識に埋め込むべきか」を決める為に提案手法を用い、知識の可読性の面でも予測精度の面でも提案手法が利点を持つことを示す。
河瀬 康志東京工業大学
Near-feasible stable matchings with budget constraints（IJCAI'17）
本研究では、病院と研修医の間での給与額を考慮した割当のモデル化である、予算制約付きの安定マッチング問題を扱う。標準的なモデルでは、１つの病院に割り当てることのできる研修医の人数に上限がある。一方、我々のモデルでは、各病院に予算があり、割り当てられた研修医の給与の合計が予算を超えないようにする必要がある。このような予算制約のある状況では、安定マッチングは存在するとは限らず、存在性を判定することすら困難である。この困難性を解決するため、HatfieldとMilgromによる「契約付きマッチングモデル」を、予算をある程度破るマッチングを扱えるように拡張する。その上で、効率的にほぼ実行可能な安定マッチングを求めるメカニズムを2つ提案する。
杉山 麿人国立情報学研究所
Tensor Balancing on Statistical Manifold（ICML'17）
テンソルをバランス化する。これは、N階テンソルにN-1階テンソルをN個掛けることで、すべてのファイバーに対して総和が1になるように正規化する操作である。2階テンソルである行列のバランス化は、行列同士を比べる際の前処理や、Wasserstein距離を効率的に近似するために用いられており、その一般化となっている。本研究では、ニュートン法を用いた2次収束する効率的なアルゴリズムを提案し、数値実験によって、既存手法より1,000倍から100,000倍程度高速にバランス化が達成できることを示す。このアルゴリズムの正当性を理論的に示すために、テンソルを統計多様体上の確率分布としてモデル化し、バランス化を部分多様体への射影として実現する。すると、ニュートン法で用いるヤコビ行列、すなわち多様体上での勾配が、メビウス反転公式と呼ばれる数え上げ理論での基礎定理を使って解析的に求まる。提案したモデルは、テンソルのバランス化に限らず、重み付きDAGやボルツマンマシンなど、様々な統計的機械学習のモデルを含んでいる。
澄田 範奈国立情報学研究所
Online Optimization of Video-Ad Allocation（IJCAI'17）
本研究では、インターネット広告において近年急速に普及しつつある動画広告に着目する。従来のディスプレイ広告では、各ユーザーに対して割当てる広告と広告主からの支払額を決めて収益を最大にする問題は、理論と応用の両方から盛んに研究されている。従来の広告と異なり、動画広告が効果を発揮するためにはユーザーにある程度広告を観てもらう必要がある。しかし、既存手法は広告の表示時間を扱えないという問題がある。本研究では動画広告割当問題を新たに導入し、割当と価格が無羨望性を満たす中で最大収益の(1-1/e)倍を保証するアルゴリズムを与える。
阿部 真人国立情報学研究所
Optimizing mating encounters by sexually dimorphic movements（Journal of the Royal Society Interface）
近年、ヒトを含めた動物の大規模な移動データが得られるようになり、移動のパターンが明らかになってきた。一方、どのようなパターンを示すことが個体にとって利益をもたらすかを理論的に明らかにすることも移動パターンの理解にとって重要である。
本講演では、生物でのオスとメスのような、互いに探索し合うような場合にどのような動き方をすれば遭遇率が高まるかの理論解析を行った結果を報告する。この問題設定は生物個体に限らず、酵素と補酵素のような分子運動や、探索ロボットの移動アルゴリズムにも当てはまる。結果として、条件によって一方が高い拡散性をもち、もう一方が低い拡散性をもつように異なった移動パターンを示すことが最適であることが明らかになった。
山田 誠理化学研究所
Convex Factorization Machine for Toxicogenomics Prediction（KDD'17）
We introduce the convex factorization machine (CFM), which is a convex variant of the widely used Factorization Machines (FMs). Specifically, we employ a linear+quadratic model and regularize the linear term with the L2-regularizer and the quadratic term with the trace norm regularizer. Then, we formulate the CFM optimization as a semidefinite programming problem and propose an efficient optimization procedure with Hazan's algorithm. A key advantage of CFM over existing FMs is that it can find a globally optimal solution, while FMs may get a poor locally optimal solution since the objective function of FMs is non-convex. In addition, the proposed algorithm is simple yet effective and can be implemented easily. Finally, CFM is a general factorization method and can also be used for other factorization problems, including multi-view matrix factorization and tensor completion problems, in various domains including toxicogenomics and bioinformatics. Through synthetic and traditionally used movielens datasets, we first show that the proposed CFM achieves results competitive to FMs. We then show in a toxicogenomics prediction task that CFM predicts the toxic outcomes of a collection of drugs better than a state-of-the-art tensor factorization method.
今泉 允聡統計数理研究所
Tensor Decomposition with Smoothness（ICML'17）
本研究では、テンソルデータと呼ばれる多次元配列で表されるデータ構造を扱う。実応用上で与えられるテンソルデータの多くは高次元性を持っているが、それらは本質的には低次元空間を用いて表現できることが多い。特に、時系列や空間構造に依存するデータは、隣接する要素が近い値を取るといった、「滑らかさ」と表現される一種の連続性が存在する。この研究では、"Smoothed Tucker Decomposition (STD)"という滑らかさの構造を活用したテンソル分解方法を提案した。STDは基底関数の和でテンソルを表現することで、テンソルデータの持つ高次元性を緩和する。我々はSTDを凸最適化問題の形で定式化し、その解を求めるための交互方向乗数法によるアルゴリズムを導出した。また我々はSTDの推定誤差を理論的に解析し、テンソルデータが十分な滑らかさを持つ状況下では、STDが誤差を小さくすることを示した。この結果は数値実験によっても確認された。
波多野 大督国立情報学研究所
Computing Least Cores of Supermodular Cooperative Games（AAAI'17）
本研究で扱う協力ゲームは、複数の合理的なプレイヤーが存在したときに、協力関係を分析するための一つの問題である。協力ゲームでは、ある協力関係により得られる利得が与えられるときに、その利得をどのように分配すれば、その協力関係が維持されるかを分析する。例えば、タクシーをシェアする場合を考えると、ある人が、複数人で乗ったときに支払う額と一人で乗ったときに支払う額を比較し、一人の場合の方が安い場合はこの協力関係は維持されず、タクシーに一人で乗るだろう。この協力関係を表現する重要な解概念に”コア”というものが存在する。コアがあるかどうかを判定するのは、一般的に難しく、NP完全である。本研究では、優モジュラ協力ゲームと呼ばれる特殊な問題に着目する。この問題では、必ずコアが存在することが保証されている。そこで、本研究では、コアの中でもより良いコアである、弱双対コアと強双対コアを求めることを目的とする。本研究の貢献はこれら２つのコアの最適値を簡単な数式で表現できるようにしたことである。
山口 祐人Indeed
When Does Label Propagation Fail? A View from a Network Generative Model（IJCAI'17）
ラベル伝搬法は、ネットワーク上のノードのラベルを推定する手法の一つである。本研究では、ラベル伝搬法を確率的ネットワーク生成モデルの観点から解釈しなおすことで、ラベル伝搬法がどのようなデータに対してうまく動作するか、あるいはしないかを理論的に示す。
前原 貴憲理化学研究所
Exact Computation of Influence Spread by Binary Decision Diagrams（WWW'17）
ソーシャルネットワークでの影響拡散の推定は、バイラルマーケティングにおける口コミ効果を見積もるための基本的な手続きである。この問題についてこれまで多くの研究が行われてきたが、標準的な確率モデルのもと、影響拡散量の厳密計算は非常に難しいため(#P-hard)、既存研究は厳密計算を避けてMonte-Carlo近似を用いていた。
本研究では、標準的な確率モデルのもと、影響拡散量を厳密に計算する初のアルゴリズムを提案する。アルゴリズムは可能なすべての拡散経路を保存する二分決定木(BDD) を新たに設計したフロンティア法を用いて構築し、構築された BDD 上で動的計画法を行うことで厳密計算を行う。構築した BDDは影響拡散に関連する様々な問題を解くために利用できる。
計算実験の結果、提案アルゴリズムは数百枝からなる小規模グラフに対して現実的な時間で影響拡散を計算できることがわかった。また、厳密計算結果と比較することで、従来使われているモンテカルロ近似の実用的な精度の評価も行った。
藤原 靖宏NTTソフトウェアイノベーションセンタ
Scaling Locally Linear Embedding（SIGMOD'17）
Locally Linear Embedding (LLE) は多次元データの非線形な構造を表現するための代表的な次元削減の手法である。LLE は多くのアプリケーションにおいて利用されているが、計算コストが高いという問題がある。そのため LLE のための高速化アルゴリズムとして Ripple を提案する。実験において Ripple が従来の手法と同じ次元削減の結果を保証しながら計算時間を大幅に削減できることを示す。
薗部 知大国立情報学研究所
Coarsening Massive Influence Networks for Scalable Diffusion Analysis（SIGMOD'17）
ソーシャルネットワーク上の情報拡散は、その規模の拡大に伴い解析の重要性が増している。しかし、現実のネットワークは巨大であるため、解析における計算効率の改善が必要である。本研究では、対象のグラフを、影響力解析の精度を落とすこと無く、複数個の頂点を一つの頂点に合併した頂点重み付きグラフとして小型化する手法を提案する。実験の結果、提案手法で小型化したグラフは影響力推定/最大化の手法の精度をほぼ保ちつつ、ネットワークのサイズを最大で4%まで削減し、影響力推定/最大化の処理時間の短縮に成功した。
玉置 卓京都大学
Beating Brute Force for Systems of Polynomial Equations over Finite Fields（SODA'17）
有限体上の多変数連立代数方程式系を解くことは、 数学、 科学および工学における基本的な問題である。有限体の位数を q、 変数の個数を n とする。このとき、 q^n通りの解候補を総当たり探索することにより問題を解くことができる。
本研究では、 最悪時に q^n より指数的に速い計算時間でこの問題を解く初めてのアルゴリズムを示す。我々のアルゴリズムは解の個数を数えることもできる。このアルゴリズムの計算時間は、 方程式の最大次数が d の場合、 およそ q^{n(1-1/O(d))} である。
本研究では、 方程式が多項式ではなくある種の算術回路で定義されるような一般化された問題も扱い、 それに対するアルゴリズムも与える。
平原 秀一東京大学
On the average-case complexity of MCSP and its variants（CCC'17）
回路最小化問題（MCSP）には長い研究の歴史があるにもかかわらず、NP完全性など多くの基本的な疑問が未解決なままである。本講演では回路最小化問題の平均的計算量に着目して、回路最小化問題の計算の難しさの新しい証拠を与える。具体的には、ランダム3SAT問題や埋め込みクリーク問題などの有名な平均計算量の問題が、回路最小化問題の一種であるMKTPに帰着できることを示す。このことはMKTPがcoNPに属さないことの初めての証拠を与える。また、一方向性関数の存在の下で、MCSPの最悪計算量から平均計算量への（弱い形の）帰着が構成できることを示す。
