Under construction. Many exciting theory courses this semester (list to be updated and filled soon)!
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.
The course will cover advanced algorithmic techniques developed for solving various (discrete) optimization problems. We will discuss linear programming, semidefinite programming, convex programming, and more. We will see applications of these techniques to a variety of applications, e.g., developing approximation algorithms for NP-hard problems, coloring (optimally) perfect graphs. Connections to learning theory will also be discussed.
Requirements: grades will be determined based on homework assignments.
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.
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.
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).
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.
The seminar focuses on learning-augmented algorithms, i.e., algorithms equipped with predictions. The main challenge is to improve their performance when predictions are accurate while maintaining provable worst-case guarantees when predictions are inaccurate. We will review recent papers in this rapidly evolving field, covering both online and offline models, the algorithmic techniques used, and the trade-offs between prediction quality and algorithmic guarantees. The seminar will also highlight current challenges and promising directions for future research.
This seminar course will provide a broad exposure to cutting-edge and classic algorithmic results in various computational models, drawn from the ten years of the SOSA conference (symposium of simplicity in algorithms). The course requires mathematical maturity, and will pay back the time investment with some beautiful and elegant results.
More information can be found here.
Auditing to get exposure to algorithms research is welcome, and even encouraged.
To be considered for registration, email David (wajc@technion.ac.il).