Αλεξάντερ Ραζμπόροφ
| Αλεξάντερ Ραζμπόροφ | |
|---|---|
| Γενικές πληροφορίες | |
| Γέννηση | 16 Φεβρουαρίου 1963 Belovo |
| Χώρα πολιτογράφησης | Ρωσία |
| Εκπαίδευση και γλώσσες | |
| Ομιλούμενες γλώσσες | Ρωσικά |
| Σπουδές | Σχολή Μηχανικής και Μαθηματικών του Πανεπιστημίου της Μόσχας Κρατικό Πανεπιστήμιο της Μόσχας[1] |
| Πληροφορίες ασχολίας | |
| Ιδιότητα | μαθηματικός επιστήμονας υπολογιστών |
| Εργοδότης | Μαθηματικό Ινστιτούτο Στέκλοβ Πανεπιστήμιο του Σικάγου[2] |
| Αξιώματα και βραβεύσεις | |
| Βραβεύσεις | βραβείο Γκέντελ (2007)[3] Gödel Lecturer (2010) βραβείο Ρόμπινς (2013) Βραβείο Νεβάλνινα (1990) O'Reilly Open Source Award (1990) |
| Ιστότοπος | |
| people | |
Ο Αλεξάντρ Αλεξάντροβιτς Ραζμπόροφ (ρωσικά: Алекса́ндр Алекса́ндрович Разбо́ров, γεννηθείς στις 16 Φεβρουαρίου 1963), μερικές φορές γνωστός ως Σάσα Ραζμπόροφ, είναι Σοβιετικός και Ρώσος μαθηματικός και υπολογιστικός θεωρητικός. Είναι Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις στο Πανεπιστήμιο του Σικάγο.
Έρευνα[Επεξεργασία | επεξεργασία κώδικα]
Το πιο γνωστό έργο του, από κοινού με τον Στίβεν Ρούντιτς, εισήγαγαν την έννοια των φυσικών αποδείξεων, μια τάξη στρατηγικών που χρησιμοποιούνται για να αποδείξουν τα θεμελιώδη κάτω όρια στην υπολογιστική πολυπλοκότητα. Ειδικότερα, ο Ραζμπόροφ και ο Ρούντιτς έδειξαν ότι, κάτω από την υπόθεση ότι ορισμένων ειδών μονόδρομων συναρτήσεων υπάρχουν τέτοιες αποδείξεις που δεν μπορούν να δώσουν λύση στο πρόβλημα P=NP, έτσι θα απαιτηθούν νέες τεχνικές για να λύσουν αυτό το ζήτημα.
Βραβεύσεις[Επεξεργασία | επεξεργασία κώδικα]
- Βραβείο Νεβάνλινα (1990) για την εισαγωγή της "μεθόδου προσέγγισης" στην απόδειξη των κάτω ορίων του κυκλώματος Μπουλίαν ορισμένων βασικών αλγοριθμικών προβλημάτων,[4]
- Λέκτορας Έρντος, Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ, 1998.
- Αντεπιστέλλον μέλος της Ρωσικής Ακαδημίας Επιστημών (2000)[5][6]
- Βραβείο Ντέιβιντ Π. Ρόμπινς για το βιβλίο "Σχετικά με την ελάχιστη πυκνότητα των τριγώνων σε γραφήματα" (Συνδυαστική, Πιθανότητες και Πληροφορική 17 (2008), αριθ. 4, 603-618), και για την εισαγωγή μιας νέας ισχυρής μεθόδου, αναφοράς αλγεβρών, για να λύσει προβλήματα σε ακραία συνδυαστική
- Βραβείο Γκέντελ (2007, με τον Στίβεν Ρούντιτς) για την εφημερίδα "Φυσικές Αποδείξεις."[7][8]
- Καθηγητής Διακεκριμένης Υπηρεσίας Άντριου ΜακΛις (2008) στο Τμήμα Επιστήμης Υπολογιστών του Πανεπιστήμιου του Σικάγο.
Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]
- Άβι Ουίγκντερσον
- Πολυπλοκότητα κυκλώματος
- Ελεύθερη ομάδα
- Φυσικές αποδείξεις
- Μονόδρομη λειτουργία
- Ψευδοτυχαία οικογένεια εξίσωσης
- Ψήφισμα (λογική)
Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]
- Razborov, A. A. (1985). «Lower bounds for the monotone complexity of some Boolean functions» (PDF). Soviet Mathematics - Doklady 31: 354–357. http://www.mi.ras.ru/~razborov/clique.pdf.
- Razborov, A. A. (June 1985). «Lower bounds on monotone complexity of the logical permanent». Mathematical Notes of the Academy of Sciences of the USSR 37 (6): 485–493. doi:.
- Разборов, Александр Александрович (1987). (PDF) (στα Russian). Московский государственный университет http://www.mi.ras.ru/~razborov/phd.pdf. Missing or empty
|title=(βοήθεια) (PhD thesis. 32.56MB) - Razborov, A. A. (April 1987). «Lower bounds on the size of bounded depth circuits over a complete basis with logical addition». Mathematical Notes of the Academy of Sciences of the USSR 41 (4): 333–338. doi:.
- Razborov, Alexander A. (May 1989). «On the method of approximations» (PDF. 1.41MB). Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. Seattle, Washington, United States, pp. 167–176. doi:. http://www.mi.ras.ru/~razborov/approx.pdf.
- Razborov, A. A. (December 1990). «Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits». Mathematical Notes of the Academy of Sciences of the USSR 48 (6): 1226–1234. doi:.
- Razborov, Alexander A.; Rudich, Stephen (May 1994). «Natural proofs» (PostScript). Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Canada, pp. 204–213. doi:. http://www.mi.ras.ru/~razborov/int.ps.
- Razborov, Alexander A. (December 1998). «Lower Bounds for the Polynomial Calculus» (PostScript). Computational Complexity 7 (4): 291–324. doi:. http://www.mi.ras.ru/~razborov/polynom.ps.
- Razborov, Alexander A. (January 2003). «Propositional proof complexity» (PostScript). Journal of the ACM 50 (1): 80–82. doi:. http://www.mi.ras.ru/~razborov/jacm50.ps. (Survey paper for JACM's 50th anniversary)
Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]
- ↑ (Αγγλικά) Mathematics Genealogy Project.
- ↑ Ανακτήθηκε στις 3 Ιουλίου 2019.
- ↑ sigact
.org /prizes /g%C3%B6del .html. - ↑ «International Mathematical Union: Rolf Nevanlinna Prize Winners». Αρχειοθετήθηκε από το πρωτότυπο στις 17 Δεκεμβρίου 2007.
- ↑ «Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History».
- ↑ «Russian Genealogy Agencies Tree: R» (στα Russian). Αρχειοθετήθηκε από το πρωτότυπο στις 21 Δεκεμβρίου 2007. Ανακτήθηκε στις 4 Αυγούστου 2018.
- ↑ «ACM-SIGACT Awards and Prizes: 2007 Gödel Prize».
- ↑ «EATCS: Gödel Prize - 2007». Αρχειοθετήθηκε από το πρωτότυπο στις 1 Δεκεμβρίου 2007.
Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]
- Αλεξάντερ Ραζμπόροφ στο Mathematics Genealogy Project.
- 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.
- Πρότυπο:IMO results
- 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.
|