Quantum computation 1

0368-4057-01

Course Syllabus

Lecturer: Prof. Amnon Ta-Shma  (Sometimes Prof Oded Regev or Prof Julia Kempe)

Credit:

Prerequisites: no physics background will be assumed. Computational complexity is an advantage.

Course Objectives: Study quantum algorithms and their limitations.

Course Syllabus:

We will start with the notion of a quantum bit, and demonstrate the counter intuitive quantum properties of Teleportation and  Bell inequalities, touching upon non-signaling boxes. We will define the computational model using quantum gates and quantum circuits. The main part of the course will be devoted to quantum algorithms:

·         Fourier transform, Period finding and Shor's factorization algorithm. We will then redo it by demonstrating Shor’s DLOG algorithm with phase estimation.

·         Grover's search algorithm in the Oracle model, which provides a provable quadratic speed up, and the BBBV matching lower bound.

In the second part of the course we will define density matrices and POVMs. Time permitting ,we will do a subset of the following:

·         A general lower-bound on quantum black-box computation by polynomials. Black-box computation cannot provide more than a polynomial speedup for total, Boolean functions.

·         The trace norm and the fidelity functions. Quantum coin flipping.

·         Quantum entropy and random access codes.

·         Quantum interactive proofs, QMA, witness-preserving QMA amplification.

·         Quantum error correcting codes and quantum fault tolerance.

Course requirements: The actual projects for this year will be determined during the first two weeks of the semester.

Required reading:

·         Quantum Computation and Quantum Information, M. Nielsen, I. Chuang.

·          Classical and Quantum Computation, A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi

Recommended reading:

·         Lecture notes on the web:

o   Quantum computation, by Joohn watrous

o   Topics in Quantum Information, by Ashwin Nayak. 

o    Quantum Computation, by John Preskill.

Quantum Computation, by Umesh Vazirani. 

Grade: Based on home assignments..

Link to course site:  http://www.cs.tau.ac.il/~odedr/teaching/quantum_fall_2005/index.html

Foundation of Cryptography, Fall 2011

--------------------------------------------------------------
This is a a graduate-level introduction to the theoretical foundations of Cryptography. We'll study the basic cryptographic primitives (e.g., one-way functions and pseudorandom generators) while focusing on formal definitions and rigorous proofs. Some more advanced topics will be also touched upon.

Prerequisites:
---------------------
Basic complexity (the classes P, NP, BPP), basic probability. Some prior informal-level knowledge of cryptography, such as the undergraduate course 0369.3049, is recommended but not required.

This is a graduate course, where undergrads are encouraged to take 0369.3049. In some special cases, however, undergrads who got my personal permission can take the course.

Course requirements:
---------------------------------

• Homework: 3-5 homework sets
• A final exam

Syllabus:
-------------
The exact syllabus will be determined as the semester proceeds, based on the makeup of the class. A rough superset of the material covered includes:

• Basic primitives: One way functions, Pseudorandom generators, Pseudorandom functions, Collision resistant hash functions, Trapdoor permutations
• Basic protocols I: Message Authentication, Digital signatures, Encryption: Symmetric, asymmetric, Key Exchange, Secure Communication
• Basic protocols II: Commitment schemes, Coin tossing, Zero Knowledge, Oblivious Transfer

This course will cover hot topic is visual computing including recent research results in computer graphics , image processing and geometric modeling.

קורס מתקדם במערכות מחשב.

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

פרטים נוספים באתר האינטרנט.

Advanced Computer Networks: Peer-To-Peer Networks

Abstract

The Internet has drastically changed from the first days it was used by the public. Such changes, many of them very hard to predict 10 years ago, were driven by either technology or users’ needs and interests. While the “pure” WEB + email is still an important part of the internet, many other applications/technologies came into effect. An important such technology is the Peer-to-Peer (P2P) network (e.g. Bittorrent), which accounts these days to the large majority of traffic in the Internet and is likely to have strong impact on the future of the Internet. The course will include some basic theoretical background which will be complemented by reviewing advanced topics on the subject.

Prerequisites: Communications networks 0368-3030-01, or equivalent background is highly preferred/recommended.

בקורס זה אנחנו מתעניינים בהגדרה של שפות מידול (modeling languages) ובשימוש במודלים (models) בהנדסת תוכנה.   נתמקד בהגדרה ובחקירה של שפות מידול, ביחסים בין מודלים, ובשיטות פורמליות מתאימות שנעזרות בניתוח אוטומטי (SAT solvers, BDD-based symbolic algorithms) כדי לספק למהנדסים הפשטות (abstractions) וכלים להתמודדות עם האתגרים של התכנון, הבניה, ההרצה, הבדיקה, התחזוקה, והאבולוציה של מערכות תוכנה.

בין הנושאים שנלמד:

Defining the syntax and semantics of modeling languages
Applications of formal verification and synthesis

בין השפות שנלמד:

Alloy
Temporal logics and SMV
Various sub languages of the UML and their extensions (class diagrams, sequence diagrams etc.)          

---------------------------------------------------------------

סיליבוס לקורס במכירות פומביות

עסקאות במאות מיליארדי דולרים מבוצעות מידי שנה ע"י מכירות פומביות אנו נעסוק בהיבטים כלכליים וחישוביים של התורה העשירה שפותחה בנושא זה אין צורך בידע מוקדם נעקב על הספר "Jason Hartline "Approximation in Economic Design וגם מקורות אחרים.

אבטחת מידע - תאוריה בראי המציאות

Information Security: Theory vs. Reality

סמסטר א

יום ג'   16:00-19:00

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

הקורס מתאים לתלמידי מחקר וכן לתלמידי תואר ראשון מתקדמים (מדמ"ח שנה ג', הנדסה שנה ד'). נדרשים הבנה טובה של מבנה מחשבים (מערכות הפעלה, שפת מכונה, עקרונות שפות תכנות, רשתות תקשורת), נסיון תכנות מעשי, והכרת מושגי בסיס בתורת ההצפנה.

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

הקורס הוא קורס תואר שני, אבל הוא מתאים גם לתלמידי תואר ראשון במדעי המחשב ולתלמידי תואר שני ושלישי במתימטיקה.

Course name:  

Advanced course on Algorithms 

Course Syllabus

Lecturer: Haim Kaplan

Credit: 3 points

Prerequisites: Algorithms, data structures

Course Objectives:

Present the state of the art of the research on basic algorithmic problems and data structures.  

Course Syllabus:

We describe classical data structures such as biased search trees, splay trees, finger search trees, and dynamic trees and some of their algorithmic applications. These applications include algorithms for maximum flow, minimum cost flow and algorithms for dynamic graph problems.

We also cover some geometric applications such as range searching, triangulation, and other geometric problems.

We also cover data structures and algorithms for answering shortest path queries on graphs, and algorithms for  basic problems on strings.

Time permitting we will survey other areas such as persistent data structures and their applications.

Course requirements:

Homework assignments, possibly a final exam

Grade:

According to homework assignment and final exam