Expandergraphen und Derandomisierung

Authors: 
Fetsch, Christian
Year: 
2014
Language: 
German
Abstract in English: 
In this thesis Wigderson and Xiaos article "Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications" is considered in detail. It presents their proof of a matrix-valued Chernoff bound. The gained results, together with Raghavans method of pessimistic estimators, are then applied to derandomize the proof of the Alon-Roichman theorem.
Abstract: 
In der vorliegenden Arbeit wird der Artikel "Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications" von Wigderson und Xiao detailliert nachvollzogen. Es wird aufgezeigt, wie der Beweis der matrixwertigen Chernoff-Ungleichung von Ahlswede und Winter verläuft. Mit diesen Ergebnissen und der Methode der pessimistischen Schätzer wird schließlich der Beweis des Alon-Roichman-Theorems entrandomisiert.
Pubdate / Erscheinungsdatum: 
2014-08-07
Pages / Seitenanzahl: 
38
AttachmentSize
expandergraphen_und_derandomisierung.pdf345.87 KB