In the problems we consider in this group, we usually try to optimize some goal function while dealing with selfish agents that may have separate and conflicting goals, and that may lie to us in order to improve their own goal function. In algorithmic mechanism design, we ensure that it is in the best interest of the agents to tell us the truth. We also examine the price of anarchy and price of stability for various problems.

Most interesting optimization problems are NP-Hard. For such problems, unless P=NP, exact algorithms cannot be efficient. In the field of approximation algorithms, we take the reverse perspective: efficient algorithms cannot be exact. But if we naturally insist on efficient algorithms, how close can we get to an optimal solution? In this group we design efficient algorithms with provable guarantees on the distance between their output and the (unknown) optimal solution. Complementing this, we are also studying the limits of such algorithms.

Efficient computation depends on how data is organized and maintained. We design and analyze data structures that support fast queries and updates while using memory economically. Our research explores the trade-offs between query time, update time, and storage space, including the opportunities offered by randomization. We develop methods for fundamental tasks such as hashing and maintaining ordered data, and establish lower bounds that clarify the limits of achievable performance.

Many computational problems arise on inputs that change over time. Can we maintain a solution efficiently without recomputing it from scratch after every update? We develop dynamic algorithms for fundamental graph and optimization problems, including matching, coloring, set cover, and clustering. Our goal is to obtain strong guarantees on update time and solution quality while limiting the changes made to the maintained solution. We also investigate the power of randomization and connections between dynamic algorithms, sublinear algorithms, and fast static algorithms.

How can resources be allocated fairly among agents with different preferences? We study the existence and efficient computation of fair allocations, with a particular focus on indivisible goods and chores. Since exact fairness is not always attainable, we investigate which guarantees can be achieved through approximation and how they interact with economic efficiency. More broadly, we study allocation and exchange problems at the intersection of computer science and economics, developing algorithms with provable guarantees and investigating their limitations.

Fine-grained Complexity Theory is the design of reductions that prove running time lower bounds assuming a plausible complexity-theoretic conjecture such as the Strong Exponential Time Hypothesis. In this area the design of efficient algorithms goes hand in hand with proving fine-grained lower bounds: our goal is to prove matching upper and lower bounds, thus establishing best-possible algorithms, that achieve the optimal constant in the exponent of the running time. We apply this methodology to problems from various domains such as graphs, strings, geometry and optimization.

Our long-term vision is to develop techniques for designing efficient graph algorithms and use them to understand graph data.  We currently focus on algorithms that work across many models of computation, such as dynamic, distributed, streaming, parallel, and quantum algorithms. We aim to achieve two goals simultaneously: (i) solutions to notorious long-standing open problems, and (ii) efficient algorithms that can fully exploit both the features of modern computing devices and the characteristics of contemporary data.

Many computational decisions must be made before the entire input is known. We study online algorithms, which process requests as they arrive without knowing future requests. A central question is how closely their performance can approach that of an optimal algorithm with advance knowledge of the complete input. We develop algorithms with provable competitive guarantees and investigate lower bounds that capture the inherent cost of uncertainty. Our goal is to understand the possibilities and limitations of making efficient decisions with incomplete information.

Many real world applications are naturally formulated as combinatorial optimization problems, i.e. problems of finding the best solution(s) out of a finite set. Various methods have been developed to tackle such problems: integer programming, fixed-parameter tractable and exact algorithms, approximation algorithms and combinatorial algorithms, among others. D1 works on applying these methods to various problems from different areas, ranging from bioinformatics to geometry, to scheduling, and several others.

Parameterized complexity analyzes how different parameters of the input influence the complexity of hard algorithmic problems. The general goal is to show with fixed-parameter tractability results that the combinatorial explosion can be confined to certain well-defined parameters, or to understand why such algorithms are not possible. An interesting class of hard problems that we consider are counting problems (where the goal is to count all solutions), as they may allow for interesting phenomena that are not observed in the corresponding decision problems.

Machine learning algorithms have many applications. Can we theoretically prove they are consistent and helpful? We focus on two paradigms: algorithmic stability and algorithms with predictions. Stable algorithms, which can tolerate changes in their inputs, can inherit many desirable properties such as generalization, differential privacy, and replicability. Algorithms with predictions use their predictions to circumvent worst-case bounds when the predictions are good, and mitigate the effect of bad predictions

Strings (texts, sequences) appear everywhere in our daily lives, and they constitute some of the biggest datasets generated by humanity (such as the petabytes of genomic data). We develop cutting-edge algorithms for processing huge strings of all kinds, focusing on classical problems such as measuring the similarity of two strings or finding all fragments of a long text that closely resemble a given pattern. We design our algorithms for multiple modern models of computation capable of handling big data. In particular, we develop compression schemes efficiently supporting basic computational tasks on the repetitive sequences.