Graph decompositions are ubiquitous and powerful algorithmic tools with applications in many settings of network algorithms: sequential, parallel, distributed, dynamic, and streaming algorithms. They also give rise to simpler structures for approximating networks such as spanners, hop-sets and shortcuts, oblivious routings, metric embeddings, and (vertex) sparsifiers. Length-constrained expanders and length-constrained expander

decompositions are a recent versatile and powerful and generalization of both

- low-diameter decomposition, which captures l_1-quantities like lengths and costs, and
- expander decomposition, which captures l_infinity-quantities like flows and congestion.

Length-constrained expander decompositions significantly broaden and extend the range of applications for network decomposition techniques, including recent breakthroughs in dynamic distance oracles and computing multi-commodity flows. This talk will give a broad introduction to graph decompositions and various aspects of

length-constrained expanders and explain their applications within the broader TCS community.

Petri nets, also known as vector addition systems, are an established model of concurrency with extensive applications in modelling and analysis of a wide range of systems. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of this problem was remaining for decades one of the most prominent open questions in the theory of verification. The complexity has been settled only recently.

After recalling briefly the recent breakthrough complexity bounds, we will focus on four key extensions of Petri nets: with data, with a pushdown stack, with branching, and with richer transition relations. Until very recently, the decidability status of all these extensions remained unknown. We will briefly overview the rapid progress that has been brought about in last years, and outline the most important questions which are still open.

The study of how incentives reshape classic algorithmic problems has been at the heart of algorithmic game theory (AGT) since its inception. In their seminal work, Nisan and Ronen famously conjectured that adding incentives for truthfulness to the optimization problem of scheduling would make the problem extremely hard to approximate, as was finally proven by Christodoulou et al in 2023. 

Recently, a new frontier for AGT has emerged: Algorithmic Contract Design. The community is beginning to explore a new-to-us class of incentives: the incentives for an agent to earnestly invest true effort in a delegated task. These kinds of incentives are crucial for any kind of collaboration and delegation, for both human as well as AI agents.

In this talk I describe some of our recent progress on understanding the intersection of algorithm design with incentives for exerting true effort, using the classic budget maximization problem as our algorithmic starting point. This includes an algorithm-to-contract transformation framework, which transforms algorithms for combinatorial problems like budgeted maximization to tackle incentive constraints that arise in contract design. 

Based on joint works with: Zohar Barak, Asnat Berlin, Ilan Reuven Cohen, Ilan Doron-Arad, Alon Eden, Omri Porat, Hadas Shachnai, Gilad Shmerler.

• Algorithmic Game Theory

• Algorithmic Learning Theory

• Algorithmic Randomness

• Algorithms and Data Structures

• Algorithms for Big Data

• Approximation Algorithms

• Automata Theory

• Average-Case Analysis

• Combinatorics and Graph Theory

• Combinatorial Generation, Enumeration and Counting

• Combinatorial Optimization

• Combinatorics of Words

• Complexity Theory

• Computational Biology

• Computational Geometry

• Computational Learning Theory

• Computational Social Choice

• Computability, Recursion Theory

• Concurrency

• Data Compression

• Database Theory

• Descriptional Complexity

• Discrete Event Systems

• Discrete Optimization

• Distributed, Parallel and Network Algorithms

• Energy-Aware Algorithms

• Error-Correcting Codes

• Fine-grained Complexity

• Formal Languages

• Formal Specification and Verification

• Foundations of Artificial Intelligence and Machine Learning

• Graph Algorithms and Modelling with Graphs

• Graph Drawing and Graph Labeling

• Grammatical Inference

• Integer and Linear Programming

• Logic in Computer Science

• Model-Checking

• Models of Computation

• Network Theory and Temporal Graphs

• Online Algorithms

• Parameterized Algorithms and Complexity

• Probabilistic and Randomized Algorithms

• Program Semantics

• Quantum Algorithms

• String Algorithms

• Sublinear Time and Streaming Algorithms

• Telecommunication Algorithms

• Theorem Provers and Automated Reasoning

• Voting Theory