Sublinearzeitalgorithmen

• Antragsteller: Professor Dr. Christian Sohler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2008 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 93860940

• Erstellungsjahr: 2013

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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