질문, 건의, 요청 사항은 방명록(guest)에 올려 주십시오.

개요

probabilistic method들 중 method of conditional probability에 대해서 소개한다. global structure의 한 속성의 평균이 local structure들의 그 속성의 평균의 합으로 표현될 수 있을 때, randomized approach에서 randomness를 어느정도 derandomization시킬 수 있다.
가령, random graph의 edge coloring을 할 때, monochromatic한 size-4 clique의 개수가 일정 수준의 개수에 bound되도록 coloring하는 방식이 존재한다는 proposition을 예로 들 수 있다.

목차

- A Starting Example
- Generalization
- Pessimistic Estimator
- Example of Pessimistic Estimator
신고
Posted by AALab