Αλεξάντερ Ραζμπόροφ

Ο Αλεξάντρ Αλεξάντροβιτς Ραζμπόροφ (, γεννηθείς στις 16 Φεβρουαρίου 1963), μερικές φορές γνωστός ως Σάσα Ραζμπόροφ, είναι Σοβιετικός και Ρώσος μαθηματικός και υπολογιστικός θεωρητικός. Είναι Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις στο Πανεπιστήμιο του Σικάγο.

Έρευνα 
Το πιο γνωστό έργο του, από κοινού με τον Στίβεν Ρούντιτς, εισήγαγαν την έννοια των φυσικών αποδείξεων, μια τάξη στρατηγικών που χρησιμοποιούνται για να αποδείξουν τα θεμελιώδη κάτω όρια στην υπολογιστική πολυπλοκότητα. Ειδικότερα, ο Ραζμπόροφ και ο Ρούντιτς έδειξαν ότι, κάτω από την υπόθεση ότι ορισμένων ειδών μονόδρομων συναρτήσεων υπάρχουν τέτοιες αποδείξεις που δεν μπορούν να δώσουν λύση στο πρόβλημα P=NP, έτσι θα απαιτηθούν νέες τεχνικές για να λύσουν αυτό το ζήτημα.

Βραβεύσεις 

 Βραβείο Νεβάνλινα (1990) για την εισαγωγή της "μεθόδου προσέγγισης" στην απόδειξη των κάτω ορίων του κυκλώματος Μπουλίαν ορισμένων βασικών αλγοριθμικών προβλημάτων,
 Λέκτορας Έρντος, Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ, 1998.
 Αντεπιστέλλον μέλος της Ρωσικής Ακαδημίας Επιστημών (2000)
 Βραβείο Ντέιβιντ Π. Ρόμπινς για το βιβλίο "Σχετικά με την ελάχιστη πυκνότητα των τριγώνων σε γραφήματα" (Συνδυαστική, Πιθανότητες και Πληροφορική 17 (2008), αριθ. 4, 603-618), και για την εισαγωγή μιας νέας ισχυρής μεθόδου, αναφοράς αλγεβρών, για να λύσει προβλήματα σε ακραία συνδυαστική
 Βραβείο Γκέντελ (2007, με τον Στίβεν Ρούντιτς) για την εφημερίδα "Φυσικές Αποδείξεις."
 Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις (2008) στο Τμήμα Επιστήμης Υπολογιστών του Πανεπιστήμιου του Σικάγο.

Δείτε επίσης 

Άβι Ουίγκντερσον
Πολυπλοκότητα κυκλώματος
Ελεύθερη ομάδα
Φυσικές αποδείξεις
Μονόδρομη λειτουργία
Ψευδοτυχαία οικογένεια εξίσωσης
Ψήφισμα (λογική)

Βιβλιογραφία 

 
 
  (PhD thesis. 32.56MB)
 
 
 
 
 
  (Survey paper for  JACM's 50th anniversary)

Παραπομπές

Εξωτερικοί σύνδεσμοι 
 .
 Alexander Razborov's Home Page.
 All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich.
 Biography sketch in the Toyota Technological Institute at Chicago.
 Curricula Vitae at the Department of Computer Science, University of Chicago.
 DBLP: Alexander A. Razborov.
 
MathSciNet: "Items authored by Razborov, A. A."
 The Work of A.A. Razborov – an article by László Lovász in the Proceedings of the International Congress of Mathematicians, Kyoto, Japan, 1990.

Μαθηματικοί του 20ού αιώνα
Μαθηματικοί του 21ου αιώνα
Ρώσοι μαθηματικοί
Σοβιετικοί μαθηματικοί