תחום הסיבוכיות (או מורכבות חישובים) עוסק בניסיון להבין אילו בעיות מחשבים יכולים לפתור ביעילות. יעילות יכולה להתבטא בזמן החישוב, כמות הזיכרון הנצרכת, כמות התקשורת ומשאבים נוספים הדרושים למחשבים. בשלושים השנה האחרונות נתגלה שהשימוש בהטלות מטבע אקראיות יכול לעזור למחשבים לבצע חישובים מסוימים בצורה יעילה יותר. מהבנה זו נובעת שאלת הצורך והזמינות של הטלות מטבע אקראיות במסגרת עבודת המחשב, ובאופן כללי יותר: סוגיית הקשר בין אקראיות וחישוב. אקראיות היא משאב חשוב בשימושים רבים במדעי המחשב: 1. אקראיות משמשת לחיסכון במשאבי חישוב באלגוריתמים הסתברותיים, שבמקרים מסוימים יכולים להיות יעילים יותר מאלגוריתמים דטרמיניסטיים ידועים. 2. אקראיות חיונית כדי להבטיח פרטיות ושמירה על סודות (למשל בחירת מפתחות לצפנים בקריפטוגרפיה). 3. אקראיות חיונית בחישובים על נתוני עתק, שבהם אין אפשרות לקרוא את כל הקלט ולכן אין ברירה אלא להסתמך על שיטות הסתברותיות הכרוכות באקראיות. שאלות יסודיות במורכבות חישובים הן: 1. מתי אקראיות עוזרת לחישוב? 2. באילו מצבים ניתן להפחית בכמות האקראיות, או אף להיפטר ממנה לגמרי – לטובת אלגוריתמים דטרמיניסטיים – במחיר סביר? 3. איך מחשבים יכולים ליצור ביטים אקראיים? 4. איך לתכנן אלגוריתמים יעילים שיוצרים מבנים קומבינטוריים ש"נראים אקראיים"? מחקר זה נועד לקדם את הבנתנו בשאלות אלה, ובפרט לתכנן גנרטורים פסאודו-אקראיים ומזקקי אקראיות, כמפורט להלן: 1. גנרטורים (מחוללים) פסאודו-אקראיים הם אלגוריתמים שבהינתן קלט של מעט ביטים אקראיים מייצרים פלט של הרבה ביטים "פסאודו-אקראיים" (כך שאלגוריתמים יעילים אינם יכולים להבחין בין ביטים שהם באמת אקראיים לביטים הללו). גנרטורים פסאודו-אקראיים מסוגים שונים ממלאים תפקיד מרכזי בחקר מורכבות חישובים, קריפטוגרפיה וקומבינטוריקה. 2. מזקקי אקראיות הם אלגוריתמים שבהינתן דגימה ממקור אקראיות שיש בו כמות מסוימת של אקראיות, מזקקים את המקור ופולטים ביטים הקרובים לאקראיים (באופן סטטיסטי). מזקקי אקראיות מאפשרים למחשבים ליצור אקראיות (כמעט) מושלמת מדגימות מהתפלגויות הזמינות להם ש"מכילות אקראיות" (כמו למשל רעש אלקטרומגנטי, הקשות המקשים של המשתמש, תזמון של אירועים בחומרה וכדומה). מטרה נוספת של המחקר היא להוכיח שבתנאים מסוימים, אי-אפשר לתכנן אלגוריתמים כאלה. תוצאות כיוון המחקר הזה, וספציפית התוצאות שהמחקר הנוכחי עתיד להניב בהמשך, תורמות ויתרמו למטרת-העל ארוכת הטווח של קידום הבנתנו בתחום הקשר בין אקראיות לחישוב. ההישגים הטכניים העיקריים הם משפטים מתמטיים המראים בניוּת ותוצאות חוסר אפשרות (כלומר היתכנות או חוסר היתכנות) של גנרטורים פסאודו-אקראיים ומחוללי אקראיות מסוגים שונים.