סילבוס הקורס נושאים באלגוריתמים - תשע"ד, פקולטה להנדסה, אוניברסיטת ת"א

שנה"ל תשע"ד

נושאים באלגוריתמים
Topics in Algorithms

0510-7410-01

הנדסה | ביה"ס להנדסת חשמל


סמ' ב'	1500-1700	'ג	118	וולפסון - הנדסה	שיעור	ד"ר אפלבאום בני

D:\Inetpub\shared\yedion\syllabus\05\2013\0510\0510741001_desc.txt סילבוס מקוצר משקל: 2 דרישות קדם: תכנון וניתוח אלגוריתמים בעיות סיפוק אילוצים אקראיות בעיות סיפוק אילוצים (Constraint Satisfaction Problems) ממלאות תפקיד מרכזי בתחומים רבים כגון מדעי המחשב, הנדסת חשמל, מתמטיקה, ופיזיקה סטטיסטית. הקורס יעסוק בקושי של בעיות סיפוק אילוצים במקרה הממוצע – דהיינו במקרים בהם הקלטים נבחרים באקראי מתוך התפלגות פשוטה. ננתח כיצד אלגוריתמים שונים (כגון DPLL, local serach, message passing ) מתמודדים עם קלטים כאלה, ונדון בקשר לשאלות בקריפטוגרפיה, קודים לתקון שגיאות ואופטימיזציה קומבינטורית. החומר יהיו מבוסס על מאמרים שיחולקו לסטודנטים. Course description Random Satisfiability. Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them. In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will be distributed to the students. General Information: Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them. In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will be distributed to the students. During the course, we will present research questions suitable for projects or MSc and PhD theses. Prerequisites: Students are expected to be familiar with algorithms, and to have basic background in probability theory and combinatorics. Detailed Syllabus: - Overview: Constraint satisfaction problems, SAT and the P vs. NP problem, Random SAT, (slides). - The simple story of 2SAT - efficient algorithms, and threshold phenomena. - The Unit Clause heuristic, analysis via differential equations. Basic notation and probability. - The Pure Literal heuristic viewed as a (trivial) Message Passing Algorithm. - Random Walk over 2-SAT and 3-SAT - When and why heuristics fail? Lower bounds on DPLLs via Resolution, The geometry of solutions - Algorithms for Planted 3-SAT: Flaxman's algorithm, Random Walk (Vilenchik-Feige), Warning Propagation (Vilenchik-Feige-Mossel) - Fast Cryptography: Goldreich's function, The MST/ABW generators, Hardness for DPLLs, Amplification theorems, One-wayness implies pseudorandomness - Fast error correcting codes: LDPCs, iterative decoding, Spielman's linear-time encodable and decodable codes - Refuting 3SAT: Feige's assumption and its applications

סילבוס מקוצר

משקל: 2

דרישות קדם: תכנון וניתוח אלגוריתמים

בעיות סיפוק אילוצים אקראיות
בעיות סיפוק אילוצים (Constraint Satisfaction Problems) ממלאות תפקיד מרכזי בתחומים רבים כגון מדעי המחשב, הנדסת חשמל, מתמטיקה, ופיזיקה סטטיסטית. הקורס יעסוק בקושי של בעיות סיפוק אילוצים במקרה הממוצע – דהיינו במקרים בהם הקלטים נבחרים באקראי מתוך התפלגות פשוטה. ננתח כיצד אלגוריתמים שונים (כגון DPLL, local serach, message passing ) מתמודדים עם קלטים כאלה, ונדון בקשר לשאלות בקריפטוגרפיה, קודים לתקון שגיאות ואופטימיזציה קומבינטורית. החומר יהיו מבוסס על מאמרים שיחולקו לסטודנטים.

Course description

Random Satisfiability.
Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them. In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will be distributed to the students.

General Information:

Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and

statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them.

In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these

results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will

be distributed to the students. During the course, we will present research questions suitable for projects or MSc and PhD theses.

Prerequisites: Students are expected to be familiar with algorithms, and to have basic background in probability theory and combinatorics.

Detailed Syllabus:

- Overview: Constraint satisfaction problems, SAT and the P vs. NP problem, Random SAT, (slides).

- The simple story of 2SAT - efficient algorithms, and threshold phenomena.

- The Unit Clause heuristic, analysis via differential equations. Basic notation and probability.

- The Pure Literal heuristic viewed as a (trivial) Message Passing Algorithm.

- Random Walk over 2-SAT and 3-SAT

- When and why heuristics fail? Lower bounds on DPLLs via Resolution, The geometry of solutions

- Algorithms for Planted 3-SAT: Flaxman's algorithm, Random Walk (Vilenchik-Feige), Warning Propagation (Vilenchik-Feige-Mossel)

- Fast Cryptography: Goldreich's function, The MST/ABW generators, Hardness for DPLLs, Amplification theorems, One-wayness implies pseudorandomness

- Fast error correcting codes: LDPCs, iterative decoding, Spielman's linear-time encodable and decodable codes

- Refuting 3SAT: Feige's assumption and its applications

להצהרת הנגישות