MarriageTheoremのこと

_ arXiv:math 1月2日分まで、IACR ePrint 2013/087まで確認済み

_ 気になった論文１：On the computational complexity of finding hard tautologies, Jan Krajicek, http://jp.arxiv.org/abs/1212.1789

It is well-known (cf. K.-Pudlak (1989)) that a polynomial time algorithm finding tautologies hard for a propositional proof system $P$ exists iff $P$ is not optimal. Such an algorithm takes $1^{(k)}$ and outputs a tautology $\tau_k$ of size at least $k$ such that $P$ is not p-bounded on the set of all $\tau_k$'s.

We consider two more general search problems involving finding a hard formula, {\bf Cert} and {\bf Find}, motivated by two hypothetical situations: that one can prove that $\np \neq co\np$ and that no optimal proof system exists. In {\bf Cert} one is asked to find a witness that a given non-deterministic circuit with $k$ inputs does not define $TAUT \cap \kk$. In {\bf Find}, given $1^{(k)}$ and a tautology $\alpha$ of size at most $k^{c_0}$, one should output a size $k$ tautology $\beta$ that has no size $k^{c_1}$ $P$-proof from substitution instances of $\alpha$.

We shall prove, assuming the existence of an exponentially hard one-way permutation, that {\bf Cert} cannot be solved by a time $2^{O(k)}$ algorithm. Using a stronger hypothesis about the proof complexity of Nisan-Wigderson generator we show that both problems {\bf Cert} and {\bf Find} are actually undefined for infinitely many $k$. The results are based on interpreting the Nisan-Wigderson generator as a proof system.

_ 気になった論文２：Freeness of hyperplane arrangements and related topics, Masahiko Yoshinaga, http://jp.arxiv.org/abs/1212.3523

This is the expanded notes of the lecture by the author in "Arrangements in Pyrenees", June 2012. We are discussing relations of freeness and splitting problems of vector bundles, several techniques proving freeness of hyperplane arrangements, K. Saito's theory of primitive derivations for Coxeter arrangements, their application to combinatorial problems and related conjectures.

_ 気になった論文３：Accumulation points of infinite Coxeter groups of rank 3, Akihiro Higashitani, Ryosuke Mineyama, Norihiro Nakashima, http://jp.arxiv.org/abs/1212.6617

In this paper, we investigate the limit set of normalized roots of infinite Coxeter groups of rank 3. Moreover, we obtain that the set of such accumulation points coinsides with the closure of the orbit of one point of normalized limit roots.