00:00:00 / 00:00:00

Appears in collection : Nexus Trimester - 2016 - Inference Problems Theme

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter eps, a d-bounded degree graph is defined to be (k,F)-clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least F and the (outer) conductance of each part is at most cϵ4F2, where c depends only on d,k. Our main result is a sublinear algorithm with the running time O((√n)poly(F,k,1/ϵ)) that takes asinput a graph with maximum degree bounded by d, parameters k, F, ϵ , and with probability at least 2/3, accepts the graph if it is (k,F)-clusterable and rejects the graph if it is ϵ-far from (k,F∗)-clusterable for F∗=cOF2ϵ4logn , where cO depends only on d,k.

Information about the video

  • Date of recording 07/03/2016
  • Date of publication 28/03/2016
  • Institution IHP
  • Format MP4

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback