性質検査
課題
担当： 田悠一
平成 26 年 7 月 15 日
問題１
アルゴリズム A を、入力サイズ n、エラーパラメータ ϵ > 0 に対してクエリ計算量 T (n, ϵ) で動作
する、正答確率が 2/3 以上の検査アルゴリズムとする。正答確率が 1 − δ 以上にした同様の検査アルゴリ
ズムで、クエリ計算量が O(T (n, ϵ) log(1/δ)) のものが存在することを示せ。
問題２
x ∈ {0, 1}n が単調とは、任意の i < j に対して、xi ≤ xj であることを言う。単調性を定数クエ
リ (n に依存しない数のクエリ) で検査するアルゴリズムを示せ。
問題３
Szemer´edi の正則性補題に頼らないで、△-freeness に対する O(n/ϵ) クエリ検査アルゴリズムを与
えよ。
[Roth の定理] 以下を証明せよ。任意の ϵ > 0 に対して、ある N = N (ϵ) が存在し、任意の n ≥ N
に対して以下を満たす。大きさ |S| ≥ ϵn 以上の集合 S ⊆ [n] は、長さ 3 の等差数列を持つ。
問題４
ヒント：それぞれ大きさ n の頂点集合 V1 , V2 , V3 を作り、V1 , V2 , V3 の間の三角形が、S 中の長さ 3 の等
差数列に対応するように枝をはる。その後に Triangle removal lemma を適用する。
1

以下は、問題のヒントであり問題の解答ではないことを注意しておく。証明

pptxファイル

内積の定義について

幾何学II / 幾何学概論II：レポート問題その3

レポート#4

[1] 体 K 上のベクトル空間 V が与え

2014年度試験問題

経済学のための数学：宿題

一般の線形空間

5月23日講義ノート( 2014. 5.23, Lecture )

グレブナー基底と統計への応用

PDF版

「解析概論第2中間試験問題解答例– 年 2005 月 12 16

レポート解答2

D006：包除定理とその利用

第1回 復習

3.3 双曲平面とフォードの円

12月4日版

離散最適化基礎論 (5) 2014 年 11 月 7 日 演習問題 岡本 吉央

2014/10/22 0v + (1v + (−v)) = 0v + 0 = 0v に等しく (I-2, I-4, I

情報数学II-A 講義のポイント 10/20 講義(10/20)の内容

集合と位相1・読み書きワークシート 4 論理記号で書かれた命題の文章化3