הכלות בין גופים קמורים וקיום של ערוצים קוונטים

בתחום של אופטימיזציה קמורה, הרבה בעיות פרקטיות ניתן למדל כבעיות הכלה בין קבוצות קמורות שמוגדרות ע“י אי-שיוויון לינארי מטריציאלי. זהו תחום חדש יחסית, אך ישנם שימושים וקשרים רבים לתורת האינפורמציה הקוונטית, גיאומטריה אלגברית ממשית, ותורת המטריצות.

באופן כללי, לבדיקת ההכלה בין קבוצות קמורות כאלו יכולה להיות סיבוכיות גבוהה (NP-Hard). לעומת זאת, מסתבר שאפשר ”להחליש“ את הבעיה לבעיית הכלה בין קבוצות קמורות מטריציאלית, כך שבדיקת ההכלה נעשית כמעט בזמן ריצה פולינומיאלי.

בהרצאה נסקור בעיקר היבטים תיאורטים וגיאומטרים של הבעיות הללו. נסביר איך לעבור מהבעיה המקורית לבעיה הנוחה יותר, ואת הקשרים והשימושים לתורת האינפורמציה הקוונטית. במידה והזמן יאפשר, נסביר איך לכמת את השגיאה שבמעבר בין הבעיות, וכיצד סימטריה של גופים קמורים במרחב מאפשרת להעריך את השגיאה הזאת. הרקע הנדרש להרצאה הוא קורס באלגברה 2.