기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2017 Discrete Math 세미나
Title Property testing for hypergraphs
Speaker 김재훈 ( Birmingham University, UK ) Date 2017-07-27
Host KAIST Place KAIST
VOD
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.

이 페이지에서 제공하는 정보에 만족하십니까?

  • 수리과학연구정보센터
  • 환경지질연구정보센터
  • 해양수산연구정보센터
  • 자연과학분야
  • 한국연구제단