University of Cambridge > Talks.cam > Combinatorics Seminar > Local algorithms on bounded degree graphs

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Local algorithms on bounded degree graphs

Download to your calendar using vCal

  • UserEndre Csóka (Rényi Institute and University of Warwick)
  • ClockThursday 17 January 2013, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason .

We focus on the question of which properties and parameters of a very large bounded-degree graph can be estimated by a constant-time sampling from the graph. A strongly related concept is the local algorithm on bounded-degree graphs, which means that we construct a structure, say a large independent set, in such a way that we decide about each vertex depending only on its constant radius neighbourhood.

I will give a brief introduction to these topics with some recent results, open questions, and connections to other topics.

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Babbage Lecture Room - David Attenborough Building, New Museums Site. Pembroke Street. Cambridge, Cambridgeshire CB2 3QZ GB Business in Africa Conference 2016 mp3foot

Other talks

TBC TBC The Jiangmen Underground Neutrino Observatory (JUNO): Status and First Physics Results A scientists guide to the art of radiation therapy and Neurosurgery for the oncologist Tea and Coffee Break Talk TBC
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity