Sublinearzeitalgorithmen

• Applicant: Professor Dr. Christian Sohler
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 93860940

• Final Report Year: 2013

Final Report Abstract

Im Rahmen dieses Projekts haben wir erhebliche Fortschritte im Bereich des Property Testing für dünn besetzte Graphen erzielt. Die im Projekt entwickelten Arbeiten tragen zu einem verbesserten Verständnis bei, wie man mit Hilfe von Zufallsprozessen Informationen aus sehr großen Netzwerken extrahieren kann. Insbesondere die Ergebnisse zum Zusammenhang zwischen lokaler und globaler Struktur in gradbeschränkten hyperfiniten Graphen sind über das Property Testing hinaus von Interesse. Die Arbeit zur Testbarkeit von Erfüllbarkeit löst eine bekannte offene Fragestellung, die in mehreren Papieren gestellt wurde.

Publications

• Planar Graphs: Random Walks and Bipartiteness Testing. In Proceedings of FOCS 2011, pp. 423-432, 2011
  Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak and Christian Sohler
  
• Almost Optimal Canonical Property Testers for Satisability. In Proceedings of FOCS 2012, pp. 541-550, 2012
  Christian Sohler
  
• Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph Freeness. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), 2012
  Frank Hellweg and Christian Sohler
  
• Every property of hypernite graphs is testable. SIAM Journal on Computing, 42(3): 1095-1112, 2013
  Ilan Newman and Christian Sohler