โยฮัน ทอร์เคล ฮาสตาด (Johan Torkel Håstad) ( ออกเสียงภาษาสวีเดน: [ ˈjûːan ˈhǒːsta ] ; เกิด 19 พฤศจิกายน 1960) เป็นนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีชาวสวีเดนที่มีชื่อเสียงที่สุดจากผลงานด้านทฤษฎีความซับซ้อนของการ คำนวณ เขาได้รับรางวัล Gödel Prizeในปี 1994 และ 2011 และ รางวัล ACM Doctoral Dissertation Award ในปี 1986 รวมถึงรางวัลอื่นๆ อีกมากมาย เขาเป็นศาสตราจารย์ด้านวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีที่สถาบันเทคโนโลยีแห่งราชวงศ์ KTHในสตอกโฮล์มประเทศสวีเดน ตั้งแต่ปี 1988 และได้รับการแต่งตั้งเป็นศาสตราจารย์เต็มตัวในปี 1992 เขาเป็นสมาชิกของราชบัณฑิตยสถานวิทยาศาสตร์แห่งสวีเดนตั้งแต่ปี 2001

เขาได้รับปริญญาตรี วิทยาศาสตร์ สาขาคณิตศาสตร์จากมหาวิทยาลัยสตอกโฮล์มในปี 1981 ปริญญาโทวิทยาศาสตร์สาขาคณิตศาสตร์จากมหาวิทยาลัยอุปซาลาในปี 1984 และปริญญาเอกวิทยาศาสตร์สาขาคณิตศาสตร์จากMITในปี 1986 ^{[ 2 ]}

วิทยานิพนธ์และ รางวัล Gödel Prizeปี 1994 ของ Håstad เกี่ยวข้องกับงานของเขาเกี่ยวกับขอบเขตล่างของขนาดวงจรบูลีน ที่มีความลึกคงที่ สำหรับฟังก์ชันพาริตีหลังจากที่Andrew Yaoพิสูจน์ว่าวงจรดังกล่าวต้องการขนาดเลขชี้กำลัง Håstad ได้พิสูจน์ขอบเขตล่างที่เกือบจะเหมาะสมที่สุดเกี่ยวกับขนาดที่จำเป็นผ่านเลมมาการสลับ ของเขา ซึ่งกลายเป็นเครื่องมือทางเทคนิคที่สำคัญในความซับซ้อนของวงจรที่มีการประยุกต์ใช้กับความสามารถ ในการเรียนรู้ ลำดับชั้น IPและ ระบบ การพิสูจน์^{[ 3 ]}

เขายังได้รับรางวัล Gödel Prize ประจำปี 2011 จากผลงานของเขาเกี่ยวกับผลลัพธ์ที่ไม่สามารถประมาณค่าได้อย่างเหมาะสม โดยเฉพาะอย่างยิ่ง เขาได้ปรับปรุงทฤษฎีบท PCP (ซึ่งได้รับรางวัลเดียวกันในปี 2001) เพื่อให้ได้ตัวตรวจสอบความน่าจะเป็นสำหรับ ปัญหา NPซึ่งอ่านเพียงสามบิตเท่านั้น นอกจากนี้ เขายังใช้ผลลัพธ์เหล่านี้เพื่อพิสูจน์ผลลัพธ์ในความยากของการประมาณค่า^{[ 4 ]}

ในปี 1998 Håstad ได้รับเชิญให้เป็นวิทยากรในการประชุมนานาชาติของนักคณิตศาสตร์ที่เบอร์ลิน^{[ 5 ]}ในปี 1999 เขาเป็นอาจารย์ Erdősที่มหาวิทยาลัยฮิบรูแห่งเยรูซาเลมในปี 2012 เขาได้เป็นสมาชิกของสมาคมคณิตศาสตร์อเมริกัน [ ^{6 ] เขา}ได้รับเลือกเป็นสมาชิก ACMในปี 2018 จาก "ผลงานด้านความซับซ้อนของวงจร ความสามารถในการประมาณค่าและความไม่สามารถประมาณค่าได้ และรากฐานของความสุ่มเทียม " ^{[ 7 ]}

ในปี 2018 เขาได้รับรางวัล Knuth Prize "สำหรับผลงานอันยาวนานและต่อเนื่องของเขาในการค้นพบครั้งสำคัญในรากฐานของวิทยาศาสตร์คอมพิวเตอร์ ซึ่งมีผลกระทบอย่างมากในหลายด้าน รวมถึงการเพิ่มประสิทธิภาพ การเข้ารหัสการประมวลผลแบบขนานและทฤษฎีความซับซ้อน" ^{[ 8 ]}

• หน้าเว็บของโยฮัน ฮาสตาด
• ผลการแข่งขันของ Johan Håstad ในโอลิมปิกคณิตศาสตร์นานาชาติ