Title    name
2017 Discrete Math 세미나
 
  Title
  Speaker 김재훈
  Date 2017-07-27
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.   
 
Abstract : We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).
Here, a k-graph property $p$ is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy $p$ and those that are far from satisfying $p$. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.