This course will introduce modern, state of the art research on algorithms for massive data. We shall put an emphasis on works that sit on the border “between theory and practice” and on algorithmic problems with applications in machine learning, complex networks, and data science.
Modern computational systems (such as LLMs, social networks, and e-commerce systems) are required to process and analyze huge amounts of highly-structured data, and make decisions in split seconds that affect the lives of humans and the society as a whole. The amount of data, the complex structure, and the importance of fast decision making together often require the use of heuristics and algorithms that are efficient in the real world, but where the theoretical understanding is currently lacking.
We shall discuss several algorithmic problems where there is a large (and increasing) gap between theory and practice, and study and propose “optimistic” tools from the beyond worst case analysis literature to close this gap.
The course this year will focus on quantum algorithms and on
complexity classes (quantum and classical). We will learn
Shor’s factoring algorithm (in polynomial time), as well as some
highly popular quantum algorithms that might provide quantum
advantage in the near future. We will also learn the complexity class
QMA which is similar to NP, but when the verifier has a quantum
computer and the prover can send classical data as well as
quantum states.
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.
There will be two home exercises and a (personal or by a pair) final
work.
Registration is via Prof. Tal Mor talmo@cs.technion.ac.il.
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.
The course will focus on online allocation problems in stochastic settings, exemplified by the following basic scenario:
Suppose you have an item you wish to sell, and impatient buyers arrive sequentially, with each arriving buyer making a take-it-or-leave it offer for your item. Were you to know the future, you could sell to the highest bidder and get the optimal revenue from selling your item. Unfortunately, without knowing the future, and without any further assumption, you cannot even approximate the optimal revenue within any finite ratio. To overcome such pathological worst-case examples, economists (and computer scientists, and operations researchers) study such problems under probabilistic models: adversarial input revealed in random order, or stochastic input drawn from some known/unknown distribution.
The first few lectures will be given by the lecturer, who will give background on the area and on building and presenting effective lectures (see also https://www.davidwajc.com/advice for more tips). The majority of the seminar will be dedicated to students’ presentations of research papers in the area and in-class discussion. See more details here.
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.
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.
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).
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.
Meta-complexity refers to the computational complexity of problems that
are themselves about computations and their complexity. Such problems
include the Minimum Circuit Size Problem and the Time-bounded
Kolmogorov Complexity Problem, the study of which originated in the
1950s/60s and predate the modern study of Complexity theory.
Meta-complexity provides a unifying framework for a variety of central
tasks in several areas of computer science, including computational
complexity, cryptography, and learning theory, and there has been a recent
explosion of works connecting these areas through the lens of Metacomplexity.
In this course, we will focus on these recent development, with
a particular focus on connections with Cryptography.
Course will be taught in English, online, and will follow an unusual schedule.
See more info here.
Every week, one or two graduate students in TCS (writ large) will present their research topic.
Everyone is welcome!
This course studies structural aspects and algorithmic problems in modern social networks. The course involves both theoretical work and (lightweight) hands-on data analysis of real-world social networks data, using Python.
Detailed description: https://cs.technion.ac.il/courses/all/224/236020.pdf