Zum Inhalt springen

Ravi Kannan

aus Wikipedia, der freien Enzyklopädie

{{#if: befasst sich mit dem Informatiker Ravi Kannan. Zum Mediziner siehe R. Ravi Kannan (Mediziner). 

 | Vorlage:Hinweisbaustein 
 | {{#ifeq: 0 | 0 |}}

}}

Datei:RavindranKannan.tiff
Ravidran Kannan (2013)

Ravindran Kannan, genannt Ravi, (* 12. März 1953 in Madras)<ref>Lebensdaten nach Marquis, Who’s Who in Frontiers in Science and Technology 1985</ref> ist ein indischer Informatiker und Mathematiker.

Leben

Kannan studierte am Indian Institute of Technology Bombay und wurde 1980 an der Cornell University bei Leslie Earl Trotter promoviert (The size of numbers in the analysis of certain algorithms).<ref>{{#invoke:WLink|getArticleBase}} im Mathematics Genealogy Project (englisch){{#if: | {{{Kommentar}}} }} {{#if: 50099 | {{#ifeq: {{#property:P549}} | 50099 | | {{#if: {{#property:P549}} | {{#if: | | }} | {{#if: | | }} }} }} }}{{#if: 50099 | Vorlage:MathGenealogyProject/Wartung/id verwendet}}{{#if: | Vorlage:MathGenealogyProject/Wartung/name verwendet}}{{#ifeq:|{{#invoke:WLink|getArticleBase}}|Vorlage:MathGenealogyProject/Wartung/unnötige Verwendung von Parameter 2|}}</ref> Er lehrte am Massachusetts Institute of Technology, war in den 1990er Jahren Professor an der Carnegie Mellon University und danach an der Yale University. Er ist zurzeit Principal Research Scientist bei Microsoft Research in Indien (wo er die Forschungsgruppe für Algorithmen leitet) und lehrt am Indian Institute of Science in Bangalore.

Werk

Mit Alan M. Frieze fand er eine algorithmische Version des Regularitätslemmas von Endre Szemerédi.<ref>Frieze, Kannan: The regularity lemma and approximation schemes for dense problems, Proc. 37. Symposium Foundations of Computer Science (FOCS) 1996. Frieze, Kannan: A simple algorithm for constructing Szemeredis regularity partition, Electronic J. Combinatorics, Band 6, 1999</ref> In ihrer Arbeit führten sie das schwache Regularitätslemma ein, das ein wichtiges kombinatorisches Werkzeug für verschiedene Algorithmen wurde (Streaming Algorithms, Graph Limits, Sublinear Algorithms).

2011 erhielt er den Knuth-Preis für die Entwicklung einflussreicher algorithmischer Verfahren zur Lösung lange offener Berechnungsprobleme<ref><templatestyles src="Webarchiv/styles.css" />{{#if:20110429172628 

      | {{#ifeq: 20110429172628 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20110429172628}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-09 08:47:10 InternetArchiveBot | 2019-05-09 08:47:10 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20110429172628}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-09 08:47:10 InternetArchiveBot | 2019-05-09 08:47:10 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-09 08:47:10 InternetArchiveBot | 2019-05-09 08:47:10 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }} (Memento{{#if: {{#if: 2019-05-09 08:47:10 InternetArchiveBot | 2019-05-09 08:47:10 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: SIGACT, Würdigung für Knuth Preis 2011 | {{#invoke:WLink|getEscapedTitle|SIGACT, Würdigung für Knuth Preis 2011}} | {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}} }}  
                 }}}}}}}}{{#if:2019-05-09 08:47:10 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20110429172628|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011}}
    || {{#if:  || }}
  }}{{#if: SIGACT, Würdigung für Knuth Preis 2011
    | {{#if: {{#invoke:WLink|isBracketedLink|SIGACT, Würdigung für Knuth Preis 2011}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.acm.org/press-room/news-releases/2011/sigact-knuth-prize-2011 }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}</ref> mit Anwendungen auf die Verarbeitung umfangreicher Datenmengen, wobei er grundlegende Beiträge in sehr unterschiedlichen Bereichen der Informatik wie Gitter und ihre Anwendungen, geometrische Algorithmen, Maschinenlernen und numerische lineare Algebra leistete. Er befasste sich auch mit Markov-Ketten und deren Mischungszeiten, Clustering.<ref>Frieze, Petros Drineas, Kannan, Vempala, V. Vinay: Clustering in large graphs and matrices, Symposium on Discrete Algorithms (SODA) 1999</ref>

1995 stellte er mit László Lovász und Miklós Simonovits die KLS-Vermutung (benannt nach den drei Mathematikern) auf, bei der bis 2021 mit Hilfe der Methoden der stochastischen Lokalisierung von Ronen Eldan (siehe dessen Artikel) bedeutende Fortschritte erzielt wurden. Sie ist eine zentrale Vermutung der konvexen Geometrie.<ref> R. Alonzo-Gutierez, J. Bastero, Approaching the Kannan-Lovasz-Simonovits and variance conjectures, Lecture Notes in Mathematics 2131, Springer 2015</ref>

1991 bekam er den Fulkerson-Preis mit Martin Dyer und Frieze für einen polynomzeitlichen Algorithmus zur Berechnung des Volumens beliebiger konvexer Körper.<ref>Für: Martin E. Dyer, Alan M. Frieze and Ravindran Kannan: A random polynomial time algorithm for approximating the volume of convex bodies, Journal of the ACM, Bd. 38, 1991, S. 1–17</ref>

Ebenfalls 1991 löste er das Münzproblem von Frobenius und gab einen effizienten (polynomzeitlichen) Algorithmus zur Bestimmung der Frobenius-Zahl.<ref>Kannan: Lattice translates of a polytope and the Frobenius problem, Combinatorica, Band 12, 1992, S. 161–177</ref> Das nach Ferdinand Georg Frobenius benannte Problem fragt nach der größten Zahl, die nicht aus n gegebenen Zahlen durch Addition erzeugt werden kann (diese Zahl ist die Frobeniuszahl).

Mit Frieze und Santosh Vempala untersuchte er Näherungen niedrigen Rangs an Matrizen.<ref>Frieze, Kannan, Vempala: Fast Monte Carlo algorithms for finding low rank approximants, Proc. FOCS 1998</ref>

Gemeinsam mit John E. Hopcroft arbeitet er an einem Buch Computer Science Theory for the Information Age, dessen Vorabversion online abgerufen werden kann.<ref>John E. Hopcroft, Ravi Kannan, Foundations of Data Science, 2014, pdf</ref>

2002 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Peking (Rapid mixing in Markov chains). 2015 wurde er in die American Academy of Arts and Sciences gewählt, 2016 zum Fellow der Association for Computing Machinery und 2025 zum Mitglied der National Academy of Sciences.

Weblinks

Einzelnachweise

<references />

{{#ifeq: p | p | | {{#if: 170020525n2019052257105275912 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: p | p | | {{#if: 170020525n2019052257105275912 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: p | p | {{#if: 170020525 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: p | p | {{#if: 170020525 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: p | p | {{#if: n2019052257 | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: p | p | {{#if: n2019052257 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: p | p | {{#if: 105275912 | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: p | p | {{#if: 105275912 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

{{#if: Kannan, Ravi | {{#if: Kannan, Ravindran | {{#if: indischer Informatiker | {{#if: 12. März 1953 | {{#if: Madras | {{#if: | {{#if: |
Personendaten
NAME Kannan, Ravi

}}

ALTERNATIVNAMEN Kannan, Ravindran

}}

KURZBESCHREIBUNG indischer Informatiker

}}

GEBURTSDATUM 12. März 1953

}}

GEBURTSORT Madras

}}

STERBEDATUM

}}

STERBEORT

}}

Vorlage:Wikidata-Registrierung

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Ravi_Kannan&oldid=2642767“