Courses

Current Semester

236640
Advanced Quantum Computing
Spring 2021
Tal Mor
Monday 14:30-16:30

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)
Previous:
Spring 2020
236640
Tal Mor
236644
Advanced topics in scientific computing: The origin of the genetic code
Spring 2021
Tal Mor
Wednesday 14:30-16:30

The course will focus on topics related to the origins of life and in particular the origins of the genetic code.
As we all know when we see a code – someone wrote it; With one exception – the genetic code.
Relying on the notion of “autocatalytic sets” we shall explore this topic.

Prerequisites: Biology 1, Algorithms 1
236606
Algorithmic Game Theory
Spring 2021
Inbal Talgam-Cohen
Mondays 10:30-13:30

An introductory course to the topic of Algorithmic Game Theory, the study of algorithms coupled with incentives. In light of the growing influence of algorithms on the economy and society, algorithm design must take into account the interaction with strategic players on top of traditional considerations like runtime complexity. As a prime example think of eBay auctions, which solicit bids from self-interested buyers.
The first half of the course will be dedicated to mechanism design, the science of designing such online auctions and markets. In the second half we will discuss the fundamental notion of equilibrium, including reaching it through centralized computation and decentralized learning.

Time: Mondays 10:30-12:30 (lecture) + Mondays 12:30-13:30 (recitation by Konstantin Zabarnyi)

Prerequisites: Algorithms 1
Previous:
Winter 2018/2019
236602
Inbal Talgam-Cohen
236359
Algorithms 2
Spring 2021
Seffi Naor
Tue 10:30-12:30, 13:30-14:30

This course is the natural follow-up to the basic algorithms course. We will consider basic topics and fundamental techniques in the theory of algorithms, such as randomization and algebraic tools. Possible topics include network flow, cuts in graphs, matchings, linear programming, approximation algorithms, and online algorithms.

Prerequisites: Algorithms
Previous:
Spring 2020
236359
Seffi Naor
236621
Algorithms and Non-Linear Mathematical Programming
Spring 2021
Roy Schwartz
Monday 13:30-14:30, 15:30-17:30

The use of mathematical programming is of paramount importance to the design and analysis of algorithms in general, and approximation algorithms in particular. While linear programming (LP) is the prototypical type of mathematical programming that is utilized, non-linear mathematical programming is also vastly used. This course will focus mainly on semi-definite programming (SDP) and survey its basic uses in the design and analysis of approximation algorithms as well as its applications to various topics such as: graph coloring, satisfiability, graph cuts, and clustering.

read more...
Prerequisites: Algorithms 1, Computability, Probability Theory
236646
Boolean Function Analysis
Spring 2021
Yuval Filmus
Sunday, 12:30–14:30
Zoom

Boolean function analysis is the study of functions on the Boolean cube and related domains from a spectral perspective. It has become an indispensable tool in theoretical computer science, combinatorics, and probability theory.

The course will be based on a mix of classical topics and more recent work on domains other than the Boolean cube. We will also discuss several applications.

Due to the circumstances, the course will probably be given via Zoom. The link to the Zoom meetings can be found on webcourse (accessible only to Technion students).

Prerequisites: Probability Theory
Previous:
Spring 2019
236646
Yuval Filmus
Winter 2015/2016
236646
Yuval Filmus
106716
Combinatorial Methods in Machine Learning
Spring 2021
Shay Moran
Monday 12:30-13:30 , Wednesday 9:30-11:30

We will study basic mathematical models in machine learning, including supervised learning, online learning, interactive learning, and distribution learning.
We will focus on combinatorial characterizations of the complexity of learning.

The course requires mathematical maturity and will involve discussions about open problems and active research directions.

Prerequisites: Combinatorics and Probability Theory.

236508
Cryptography and Complexity
Spring 2021
Yuval Ishai
Sunday 10:30-12:30

Basic topics in theoretical cryptography.

read more...
Previous:
Winter 2018/2019
236508
Yuval Ishai
236755
Distributed Algorithms
Spring 2021
Hagit Attiya
Sunday 14:30-16:30, Tuesday 15:30-16:30

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
Introduction to Distributed Graph Algorithms
Spring 2021
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:
Spring 2020
236377
Keren Censor-Hillel
Spring 2019
236606
Prof. Keren Censor-Hillel
Spring 2018
236610
Prof. Keren Censor-Hillel
Spring 2017
236358
Prof. Keren Censor-Hillel
Spring 2016
236610
Prof. Keren Censor-Hillel
236620
Introduction to Property Testing
Spring 2021
Eldar Fischer

Suppose we are interested in figuring out whether a given input satisfies a given property, but we are only allowed to read a small part of the input. Can we still solve the problem, at least approximately? In many cases the answer is positive: it is possible to distinguish, with high probability, between inputs satisfying the property and inputs which are far from every input satisfying it. Such algorithms are known as property testers.

Prerequisites: Probability Theory, Algorithms
Previous:
Spring 2020
236622
Eldar Fischer
236829
Local Ratio Technique for Combinatorial Optimization
Spring 2021
Reuven Bar-Yehuda
Wednesday, 14:30-16:30

This is a seminar course on combinatorial optimization. The course will focus on two different methodologies: local ratio and primal-dual.
The first three lectures will serve as an introduction to approximation algorithms, via linear programming.
In the fourth lecture we will explore primal-dual techniques, and in the fifth the competing methodology, local ratio.
During the rest of the semester we will encounter many different applications to various optimization problems, such as vertex cover, set cover, Steiner trees, cycle cover, assignment problem, resource allocation, and more.

Future Semester

236331
Computability and Definability
Winter 2021/2022
Prof. J.A. Makowsky

Definability deals with the expressive power of description languages which are used in program specification, databases and axiomatic mathematics. These languages include Regular Expressions, First Order Logic, Relational Algebra, Second Order Logic and various Temporal and Modal Logics.
Computability deals with computations and the resources needed to execute them in various models of computations. These include Finite Automata, Turing Machines, Register Machines, and the like.
The course deals with the interplay between definability in various descriptive languages and computability with various computing devices. It brings together theoretical aspects of Database Theory, Computability Theory, Complexity Theory and Logic.

Prerequisites: Logic and Sets for CS (234293) , Computability (236343)

Other

Advanced Proof Systems
Show and Hide Ext. Content for Advanced Proof Systems

Proof-systems are at the very heart of theoretical computer science. For example the P vs NP question asks whether every statement that someone can prove to you, you could have actually solved by yourself.

In this course we will discuss advanced proof-systems such as:
* Interactive proofs, which are a natural generalization of NP proofs in which the verifier can interact with the prover.
* Zero-knowledge proofs, which allow one to prove the correctness of a statement without revealing anything else.
* Probabilistically Checkable Proofs (PCPs), which are proofs that can be verified by reading only a small number of bits.
* Doubly efficient proofs, which allow one to delegate expensive computations to an untrusted server.

Requirements: roughly 3 homework assignments and an exam.

Prerequisites: Computability
Winter 2020/2021
236601
Ron Rothblum
Spring 2019
236601
Ron Rothblum
Approximation Algorithms
Show and Hide Ext. Content for Approximation Algorithms

In classic complexity theory, coping with NP-hard optimization problems often translates to the following fundamental question: “What is the best approximate solution that we can get in polynomial time?” We will present basic techniques for the design and analysis of approximation algorithms.
This includes combinatorial techniques (such as local search and local ratio) and techniques based on linear programming. We will demonstrate the use of these techniques for solving packing and scheduling problems, as well as problems on graphs.

Prerequisites: Introduction to Algorithms (234247), Theory of Computation (236343)
Communication Complexity
Show and Hide Ext. Content for Communication Complexity

Communication complexity studies the number of bits that should be exchanged in order to perform a computation whose input is distributed among two or more parties. This is studied under a spectrum of computational models: deterministic, non-deterministic, randomized etc.
Beyond the immediate implications that such questions have to understanding distributed computations, we will present various surprising applications to seemingly unrelated questions, mostly in Complexity Theory.
The course will use methods from Combinatorics, Probability Theory and Algebra.

read more...
Prerequisites: Complexity Theory, Probability
Probabilistic Methods and Algorithms
Show and Hide Ext. Content for Probabilistic Methods and Algorithms

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.

read more...
Prerequisites: Probability Theory, Algorithms
Winter 2020/2021
236374
Eldar Fischer
Winter 2019/2020
236374
Eldar Fischer
Seminar in Algorithms
Show and Hide Ext. Content for Seminar in Algorithms

The topic of the seminar is Algorithms for Constrained Resource Allocation.
We will review new variants of classic resource allocation problems arising in modern computing paradigms (such as Clouds and large data centers), 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)
Seminar on Algorithmic Game Theory (AGT) and Learning
Show and Hide Ext. Content for Seminar on Algorithmic Game Theory (AGT) and Learning

This seminar covers recent research in two complementing directions: First, how can learning theory contribute to AGT? Learning is relevant to a wide range of issues including convergence to equilibrium, pricing in auctions, and strategic behavior of buyers. Second, how can AGT contribute to learning? AGT is relevant to any situation in which learning relies on strategic players (one example we’ll discuss is Waze relying on drivers to learn new routes).

Prerequisites: Algorithms 1
The Metric Method and its Algorithmic Applications
Show and Hide Ext. Content for The Metric Method and its Algorithmic Applications

The metric method is a powerful tool that has been used extensively in the last two decades in the design and analysis of algorithms.

This course will survey some of the basic techniques in the metric approach, as well as its applications to various topics such as: clustering and graph cuts, balanced graph partitioning, network routing, and online algorithms.

read more...
Prerequisites: Algorithms 1, Computability, Probability Theory
Winter 2020/2021
236621
Roy Schwartz
Winter 2019/2020
236605
Roy Schwartz
Uncertainty in Algorithms
Show and Hide Ext. Content for Uncertainty in Algorithms

The topic of this course is uncertainty in algorithms. Given a computational problem, the traditional design and analysis of algorithms assumes that complete knowledge of the input is known in advance. However, this is not the case in many applications, including resource management and allocation, data structures, and game dynamics. In these scenarios making decisions in the face of uncertainty is of major importance. Take, for example, managing a cache memory; when there is a page miss, the decision which page to evict from the cache is made without knowing future requests for pages.

In the course we will go over advanced techniques developed in recent years for dealing with such settings, where information about the future is unavailable or limited. We will mainly focus on competitive analysis of online algorithms and online learning, and study surprising connections between them. We will see how techniques from linear programming and convex optimization are useful for developing online algorithms.

Prerequisites: Algorithms 1, Theory of Computation, Introduction to Probability
Advanced Property Testing
Show and Hide Ext. Content for Advanced Property Testing

Property testing algorithms are used to decide if some mathematical object (such as a graph or a Boolean function) has a “global” property, or is “far” from having this property, using only a small number of “local” queries to the object.

Prerequisites: Probability Theory
Complexity Theory
Show and Hide Ext. Content for Complexity Theory

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
Local Ratio Technique for Combinatorial Optimization
Show and Hide Ext. Content for Local Ratio Technique for Combinatorial Optimization

This is a seminar course on combinatorial optimization. The course will focus on two different methodologies: local ratio and primal-dual.

read more...
Prerequisites: Algorithms
Advanced Topics in Cryptology
Show and Hide Ext. Content for Advanced Topics in Cryptology

Advanced topics in theoretical cryptography.

Random Graphs
Show and Hide Ext. Content for Random Graphs

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.

read more...
Prerequisites: Linear Algebra, Probability Theory
Winter 2019/2020
236306
Yuval Filmus
Winter 2017/2018
236646
Yuval Filmus
Winter 2016/2017
236646
Yuval Filmus
Seminar on Pseudorandomness
Show and Hide Ext. Content for Seminar on Pseudorandomness

Topics in pseudorandomness.

Submodular Optimization
Show and Hide Ext. Content for Submodular Optimization

Submodular optimization generalizes classical problems such as maximum cut and the generalized assignment problem (GAP).

We will explore fundamental techniques and various approximation algorithms, some of them developed at the Technion.

Prerequisites: Algorithms
Seminar in Algorithmic Game Theory
Show and Hide Ext. Content for Seminar in Algorithmic Game Theory

Seminar in Algorithmic Game Theory.

The students will present cutting-edge research papers on various topics in Algorithmic Game Theory.

Theory Lab
Show and Hide Ext. Content for Theory Lab

Discovery-based class, on a variety of topics. Students work in groups on handouts, with online help from the lecturer.

Grading based on final project.

Prerequisites: Probability Theory
Algebraic Algorithms
Show and Hide Ext. Content for Algebraic Algorithms

Algorithms involving numbers, polynomials and matrices: FFT, fast integer multiplication, fast matrix multiplication, primality testing, integer factorization.

Prerequisites: Linear Algebra, Probability Theory