236640

Advanced Quantum Computing

Spring 2024

Tal Mor

Thursday 14:30-16:30

Ullman 601

The course will focus on topics related to complexity classes (quantum and classical), sophisticated algorithms, and cryptography.

Our goal is to reach an understanding of the potentially exponential advantage of quantum computing over classical computing in the near future and in the far future.

Prerequisites: Quantum computing or Complexity theory (may be taken in parallel)

236664

Advanced Topics in Biological Computing

236613

Advanced Topics in Cryptology

236016

Algorithms for Submodular Optimization

Spring 2024

Roy Schwartz

Monday 15:30-17:30

Ullman 101

Submodular functions, which capture the property of diminishing returns, are ubiquitous in various disciplines, including combinatorics, graph theory, machine learning, economics, algorithmic game theory, and information theory. The family of submodular maximization and minimization problems is a prime example of a unified approach that captures both well-known classic problems, e.g., Max-Cut, Max-DiCut, and Generalized Assignment, and real-world applications in diverse settings, e.g., information gathering, image segmentation, viral marketing in social networks, and recommendation systems. This course deals with the algorithmic foundations of submodular optimization, focusing on basic problems and algorithmic techniques.

Prerequisites: Algorithms 1, Theory of Computation, Probability

236755

Distributed Algorithms

Spring 2024

Hagit Attiya

Sunday 14:30-16:30

Ullman 606

The course deals with design of algorithms for multi-processor systems, and analysis of their complexity; study of basic problems in such systems; lower bounds and impossibility results. Specific topics include: Mutual exclusion and resource allocation, agreement problems(Byzantine generals’ problem, approximate agreement, etc.), clock synchronization and logical clocks, broadcast and multicast, lock-free synchronization and concurrent data structures.

236377

Distributed Graph Algorithms

Spring 2024

Keren Censor-Hillel

Wednesday, 10:30-12:30, 14:30-15:30

This course gives an introduction to distributed graph algorithms.

We will see various models of computation and the basic problems in this field.

We will study both algorithms and lower bounds.

This is an algorithmic/mathematical course.

There will be no final exam. The grade will be composed by 3-4 home assignments (submissions in singles) and a final project (submissions in pairs).

Prerequisites: Probability Theory, Algorithms, Computability (צמוד)

Previous:

236011

Dynamic Graph Algorithms

Spring 2024

David Wajc

Tuesday 10:30-12:30, Tutorial 12:30-13:30

Ullman 507

This course will introduce students to advanced algorithms for dynamic graphs. This active research area focuses on questions of the following flavor: “How quickly can we solve algorithmic problems on graphs that change slowly over time? In particular, how much faster than recomputing from scratch after every change in the graph?” This question is central to problems with input that changes over time (for example, in GPS applications, closure and opening of roads changes the road network), but is also key to speeding up algorithms with static inputs (in much the same way that basic data structures can be used to speed up other classic algorithms). The course’s objective is to expose students to techniques and results for basic problems in the field (such as matching, shortest paths, minimum spanning trees, etc). As part of the course, the students will also be exposed to central tools in algorithm design and theory of computer science more broadly that are relevant to the course topic, including linear programming and duality, randomized algorithms and the multiplicative weight update method. The course evaluation will be based on homework and a final project, which includes reading a research paper, summarizing the paper and simplifying it and/or improving on it.

Prerequisites: Algorithms and Probability

236306

Random Graphs

Spring 2024

Yuval Filmus

Mon 14:30-16:30

Ulman 101

Basic course on the theory of random graphs, focusing on the Erdős–Rényi model. Based on the nice Introduction to Random Graphs by Frieze and Karoński.

Grading is based on homework and a final project.

Prerequisites: Linear Algebra, Probability Theory

236313

Complexity Theory

Winter 2024/2025

Eyal Kushilevitz

TBA

TBA

Course covering a wide range of topics in complexity theory, such as space complexity, the polynomial hierarchy, probabilistic computation, interactive proofs, circuit complexity, and more.

Prerequisites: Computability

236017

Constraint Satisfaction Problems

Winter 2024/2025

Yuval Filmus

Monday, 12:30–14:30

TBA

We will discuss three main topics:

– Schaefer’s theorem, which shows that any Boolean CSP is either in P or NP-complete.

– Hardness of approximation: we will find the inapproximability thresholds for MAX-3LIN and for MAX-CUT.

– Proof complexity: we will show that some CNFs, including random ones, are hard to refute in Resolution.

If time permits, we will discuss a few more minor topics.

Prerequisites: Algorithms, Probability Theory

Previous:

236779

Foundations of Algorithms for Massive Datasets

Winter 2024/2025

David Wajc

Tuesdays 10:30-12:30

TBA

This course will introduce students to algorithmic foundations for handling large, high-dimensional datasets.

A sampling of topics and questions that will be covered includes:

**Streaming algorithms:**How much data do we need to solve a problem whose input is revealed gradually?**Dimensionality reduction:**How can we decrease the dimension of the data while preserving its key properties?**MapReduce algorithms:**How can we correlate tens of thousands of machines to solve algorithmic problems?

Prerequisites: Probability, Algebra and Data Structures

236309

Introduction to Coding Theory

Winter 2024/2025

Ronny Roth

Wed 14:30-16:30 + 16:30-17:30

Basic concepts: error correction, error detection and erasure correction. Linear error-correcting codes. Hamming codes. Introduction to finite fields. Reed-Solomon codes, BCH codes and alternant codes. Decoding algorithms. Bounds on the parameters of error-correcting codes.

236374

Probabilistic Methods and Algorithms

Winter 2024/2025

Eldar Fischer

Sunday 14:30-16:30, Wednesday 16:30-18:30

TBD

Probabilistic methods have become a cornerstone of combinatorial theory, while probabilistic algorithms have become central to computer science.

This course introduces an array of already-classical and more modern probabilistic methods, along with their applications to math and CS. The course is centered on proof techniques and problem solving. Among the covered topics: basic methods, concentration inequalities, martingales, the local lemma, information entropy.

Prerequisites: Probability Theory, Algorithms

236813

Seminar in Algorithms

Winter 2024/2025

Hadas Shachnai

Monday 16:30-18:30

TBA

The topic of the seminar is Algorithms for Sustainable Resource Allocation.

We will review new variants of classic resource allocation problems arising in modern computing paradigms aimed at sustainable allocation of resources, and the challenges they present from algorithmic viewpoint. Background material on approximation techniques for resource allocation problems which are known to be hard to solve will be presented in several introductory lectures at the beginning of the seminar.

Prerequisites: Theory of Computation (236343)

236825

Seminar in Distributed Computing

Winter 2024/2025

Hagit Attiya

Sunday 14:30-16:30

The seminar deals with distributed computing in modern computing systems, in the presence of different kinds of failures. Grades are based (mostly) on presenting in-depth a paper from the recent research literature.