Topics in the Frontiers of Computer Science for Honor Students

The objective of the course is for advanced students to gain an appreciation of some facets of advanced research in computer science The subject consists of a series of lectures in 4 topics in computer science. The course is intended for 3rd year students in the honors program of the CS department, and for excellent M.Sc. Students. This is a 2 credits course.

Exercises:

• Ex 1
• Ex 2 (ps), (pdf),

Lectures:

1. Mike Codish: Topics on Program Analysis

   Prerequisites: I will be using logic programming as a vehicle to demonstrate the topics in this chapter. If you have no background in logic programming, then you better brush up on your Prolog. The material in this chapter can be very dense and will require a lot of work between the lectures to keep up and fill in material.

   Lecture 1:
   * Brief survey on semantics based program analysis
   * Brief survey on semantics for logic programming languages
   Lecture 2:
   * Specifying the semantics of logic programs as interpreters
   * Specifying analysers for logic programs as abstract interpreters
   * On the use of Boolean functions as a descriptions domain for program properties
   Lecture 3:
   * the class of Positive Boolean functions
   * the class of definite Boolean functions
   * worst case groundness analysis for logic programs

2. Amos Beimel: Secret Sharing Schemes - Cryptographic Applications and Computational Complexity aspects.

   Secret sharing schemes enable a dealer to distribute a secret among a set of parties such that only some predefined authorized subsets of parties can reconstruct the secret. For example, the collection of authorized subsets can be all the subsets that are bigger than some threshold. On one hand, efficient secret sharing schemes are known for some collection of authorized subsets. Most of the known schemes are based on simple linear algebra, and are connected to a computational complexity model called monotone span programs. On the other hand, no efficient secret sharing schemes are known for most collection of authorized subsets, and it is not known if such schemes exists. In this chapter I'll describe the known schemes and some lower bounds on the efficiency of such schemes.

3. Michael Elhadad: Automatic Summarization: Techniques and Current Challenges

   This series of three lectures will introduce the field of automatic text summarization and discuss recent techniques that have been developed. We will pay special attention on the basic models of text that underly the different approaches -- cohesion, coherence, topical representations. Evaluation methods will be introduced. Finally, we will present operational methods for single and multi-document summarization.

4. Jihad El-Sana:

Grades and Requirements:

Each topic in the course will be self-contained and does not require special background. However, students who took electives with one of the lecturers might find one of the sections easier.

Information: