Score:1

การมีอยู่ของ OWFs เทียบกับ $\mathbf{EXP} \neq \mathbf{BPP}$

ธง us

ใน CRYPTO 2021 Liu และ Pass ได้ตีพิมพ์บทความที่มีชื่อเรื่อง "ความเป็นไปได้ของการใช้การเข้ารหัสบน $\mathbf{EXP} \neq \mathbf{BPP}$.

หนึ่งในผลลัพธ์หลักของงานนี้สามารถตีความได้ว่าเป็นข้อบ่งชี้ว่าการมีอยู่ของ OWF นั้นเทียบเท่ากับ $\mathbf{EXP} \neq \mathbf{BPP}$. $\mathbf{EXP} \neq \mathbf{BPP}$ เป็นสมมติฐานที่อ่อนแอ ความสัมพันธ์ระหว่างสมมติฐานนี้กับความแข็งของกรณีเฉลี่ยคืออะไร ยินดีต้อนรับคำแนะนำและความคิดเห็นเกี่ยวกับงานนี้

Score:2
ธง ng

$\mathsf{EXP}\neq \mathsf{BPP}$ เป็นข้อสันนิษฐานทั่วไปที่ใช้ในวรรณกรรม derandomization คำที่ใช้ค้นหาคือ "Nisan-Widgerson" และ "Impagliazzo-Widgerson" ตัวอย่างเช่นบทคัดย่อของ อิมพัลลิอาซโซ-วิดเกอร์สัน อ่าน:

เราพิสูจน์ว่าถ้า $\mathsf{BPP}\neq \mathsf{EXP}$แล้วทุกปัญหาใน $\mathsf{BPP}$ สามารถแก้ไขได้ในเวลาเชิงเลขชี้กำลังในเกือบทุกอินพุต (ในทุกกลุ่มตัวอย่างสำหรับจำนวนอนันต์ ขนาดอินพุต) นี่เป็นผลการสุ่มครั้งแรกสำหรับ $\mathsf{BPP}$ ขึ้นอยู่กับสมมติฐานความแข็งที่สม่ำเสมอและไม่ใช่การเข้ารหัส มันแสดงถึงช่องว่างต่อไปนี้ในความซับซ้อนของอินสแตนซ์โดยเฉลี่ยของปัญหาใน $\mathsf{BPP}$ : ความซับซ้อนเหล่านี้เป็นเลขชี้กำลังย่อยเสมอ หรือมีฟังก์ชันเอกซ์โปเนนเชียลขนาดใหญ่ตามอำเภอใจ

โดยทั่วไปแล้ว เมื่อมองหาหัวข้อใหม่ วิทยานิพนธ์ระดับปริญญาเอกสามารถอ่านได้ง่ายกว่าบทความเล็กน้อย ดังนั้นหากคุณสนใจมากกว่านี้ วิทยานิพนธ์ของ Marco Carmosino อาจมีประโยชน์

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา