ACAC'23 | Aug. 24-25, 2023

Abstract:

Given a CNF formula with n variables, Schöning’s algorithm starts by chosing a uniformly random truth assignment. If that assignment happens to be satisfying, it stops. Otherwise, it tries to convert the chosen assignment into a satisfying one, by repeating the following for 3*n steps: pick any violated clause and flip a random variable in it. If the iterated variable flipping fails to produce a satisfying assignment, restart, i.e., select a new random initial assignment, try for another 3*n variables flips, etc.

The legs of Issus Coleoptratus are directly under its body. As a result, unless both legs fire with exactly the same force and within microseconds of each other when it jumps, Issus would spin through the air like a poorly thrown Frisbee. Yet, Issus jumps perfectly from flower to flower, experiencing acceleration well over 500 Gs with each jump. Fifteen years ago, scientists made a remarkable discovery unveiling the mechanism allowing Issus to accomplish this amazing feat.

In this talk, I will try to connect the above two paragraphs.

Profile / bio URL: Dimitris Achlioptas

Abstract:

We present a fully polynomial-time approximation scheme (FPTAS) for computing equilibria in congestion games, under smoothed running-time analysis. More precisely, we prove that if the resource costs of a congestion game are randomly perturbed by independent noises, whose density is at most $\phi$, then any sequence of $(1+\varepsilon)$-improving dynamics will reach an $(1+\varepsilon)$-approximate pure Nash equilibrium (PNE) after an expected number of steps which is strongly polynomial in $\frac{1}{\varepsilon}$, $\phi$, and the size of the game's description. Our results establish a sharp contrast to the traditional worst-case analysis setting, where it is known that better-response dynamics take exponentially long to converge to $\alpha$-approximate PNE, for any constant factor $\alpha\geq 1$. As a matter of fact, computing $\alpha$-approximate PNE in congestion games is PLS-hard.

We demonstrate how our analysis can be applied to various different models of congestion games including general, step-function, and polynomial cost, as well as fair cost-sharing games (where the resource costs are decreasing). It is important to note that our bounds do not depend explicitly on the cardinality of the players' strategy sets, and thus the smoothed FPTAS is readily applicable to network congestion games as well.

Profile / bio URL: Yiannis Giannakopoulos

Abstract:

We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are $p$-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability $p$, where $p$ is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to the distance of the hidden target to the origin (competitive analysis). Hence, searching with one $0$-faulty agent is the celebrated linear search (cow-path) problem that admits optimal $9$ and $4.59112$ competitive ratios, with deterministic and randomized algorithms, respectively.

First, we study linear search with one deterministic $p$-faulty agent. Our strongest result for this problem pertains to a deterministic search algorithm which, as $p\to 0$, has optimal performance $4.59112+\epsilon$, up to the additive term $\epsilon$ that can be arbitrarily small. Additionally, it has performance less than $9$ for $p\leq 0.390388$. Second, we consider linear search with two $p$-faulty agents, $p\in (0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $p\rightarrow 1/2$.

This is joint work with Evangelos Kranakis and Nikos Giachoudis. The results were presented in the 30th International Colloquium on Structural Information and Communication Complexity (SIROCCO’23).

Profile / bio URL: Konstantinos Georgiou

Abstract:

Establishing and interpreting causal relationships between actions and outcomes is fundamental to accountable decision-making. More so in the context of multi-agent sequential decision-making, where the effect of an agent's action on the outcome of a trajectory depends on how other agents respond to that action. Hence, when determining an agent's contribution to the outcome, it becomes important to consider the degree to which the impact of its actions should be attributed to the influence it exerts on other agents. Focusing on multi-agent Markov decision processes, in this paper we aim to isolate and quantify the effect of an agent's action on the outcome that propagates through other agents' actions. To this end, we introduce agent-specific effects (ASE), a novel causal quantity that can be used to express the causal effect of an action on the outcome through a selected subset of agents. We then turn to the counterfactual counterpart of ASE (cf-ASE), provide a sufficient set of conditions for the identification of cf-ASE, and propose a practical sampling-based algorithm for its estimation. Finally, we experimentally evaluate the utility of cf-ASE through a simulation-based testbed.

Profile / bio URL: Stelios Triantafyllou

Abstract:

In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting.

Previous work had established the sufficiency of finiteness of the fat shattering dimension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards a more complete characterization since the work of Simon (SICOMP ’97). To this end, we first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. We then identify a combinatorial dimension related to the Graph dimension that characterizes ERM learnability in the realizable setting. Finally, we establish a necessary condition for learnability based on a combinatorial dimension related to the DS dimension, and conjecture that it may also be sufficient in this context.

Additionally, in the context of online learning we provide a dimension that characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression, thus resolving an open question raised by Daskalakis and Golowich in STOC ’22.

Abstract:

Subset Sum is one of the most fundamental computational problems, already studied for more than a century. In this talk we will survey recent algorithmic breakthroughs for Subset Sum, due to Koiliaris-Xu [SODA 2017], Bringmann [SODA 2017], and Bringmann-Nakos [SODA 2021]. We will then show how to obtain faster exact and approximation algorithms for interesting variants of Subset Sum building upon these novel techniques. We will mainly focus on the following problems: k-Subset Sum, where we ask, given a set of positive integers, for k subsets of specific weights, Subset Sum Ratio, where we ask for two or more sets of similar weight, and Multiple Subset Sum, a special case of Multiple Knapsack.

[In collaboration with: Giannis Alonistiotis, Antonis Antonopoulos, Nikos Melissinos, Stavros Petsalakis, Theofilos Triommatis, and Manolis Vasilakis]

Profile / bio URL: Aris Pagourtzis

Abstract:

The current availability of data from various sources, together with the development of new AI methods for analyzing them, has started transforming multiple disciplines in the physical and life sciences, and even in the humanities. Of particular importance, is the recent development of explainability approaches in AI, which make possible such multidisciplinary research, as they allow to identify the features in the data that are responsible for the results and present them to the experts in the field, who in turn can interpret them and guide the design choices of the system. Sometimes, they may even have a more active role in the system design.

In this talk I will present some recent work that offers new ways of analysis in the areas of genetics and bioinformatics. In particular, we will see some some neural-network approaches for discovering epistatic interactions between genes and gene-disease associations.

Profile / bio:

Aris Anagnostopoulos (http://aris.me) is a Professor at the Dept. of Computer, Control, and Management Engineering of Sapienza University of Rome. He graduated from the Computer Engineering and Informatics Department of Univesity of Patras, Greece, he obtained his Ph.D. from Brown University, and afterwards he did a postdoc at Yahoo! Research in Santa Clara, CA. His main research interests include randomized and approximation algorithms as well as the application of machine-learning approaches on data-science problems.

Abstract:

Given a graph $G$, we denote by $\chi(G)$ and $\omega(G)$ the chromatic number and the clique number of $G$, respectively. A class $\mathcal{G}$ of graphs is $\chi$-bounded if there exists a function $f:\mathbb{N} \to \mathbb{N}$, such that for all $G\in \mathcal{G}$, we have: $\chi(H) \leq f(\omega(H))$ for every induced subgraph $H$ of $G$. For $k$ graphs $G_{1}, \ldots , G_{k}$, on the same vertex set $V$, we define their intersection to be the graph $\bigcap_{i\in [k]} G_{i}:=(V,\bigcap_{i\in[k]}E(G_{i}))$. For $k$ graph classes $\mathcal{G}_{i}, i \in [k]$, we define their intersection as the class $\{\bigcap_{i\in [k]} G_{i}:G_{i} \in \mathcal{G}_{i} \text{ and } V(G_{i}) = V(G_{1}) \text{ for every } i \in [k]\}$, which we denote by $\bigcap_{i\in [k]} \mathcal{G}_{i}$. In the seminal paper "Problems from the world surrounding perfect graphs" (1985), András Gyárfás raised specific instances of the following general question:

Let $\mathcal{G}_{1}, \ldots , \mathcal{G}_{k}$ be graph classes. Is $\bigcap_{i\in [k]} \mathcal{G}_{i}$ is $\chi$-bounded?

We present results from our ongoing work on the above question. This talk is based on joint work with Rimma Hämäläinen, Hidde Koerts, Bobby Babak Miraftab and Sophie Spirkl.

Abstract:

In the 1970s, Győri and Lovász showed that for a $k$-connected $n$-vertex graph, a given set of terminal vertices $t_1, \dots, t_k$ and natural numbers $n_1, \dots, n_k$ satisfying $\sum_{i=1}^{k} n_i = n$, a connected vertex partition $S_1, \dots, S_k$ satisfying $t_i \in S_i$ and $|S_i| = n_i$ exists. However, polynomial time algorithms to actually compute such partitions are known so far only for $k \leq 4$. This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of $k$. More precisely, we consider $k$-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with $\mathcal{O}(n^2)$ running time that solves the problem exactly, and for the second, an algorithm with $\mathcal{O}(n^4)$ running time that deviates on at most one vertex from the required vertex partition sizes.

Joint work with Katrin Casel, Tobias Friedrich, Davis Issac and Ziena Zeif.

Abstract:

Given a graph $G$ and an integer $k$, Max Min FVS asks whether there exists a minimal set of vertices of size at least $k$ whose deletion destroys all cycles. We present several results that improve upon the state of the art of the parameterized complexity of this problem with respect to both structural and natural parameters.

Using standard DP techniques, we first present an algorithm of complexity $\textrm{tw}^{\mathcal{O}(\textrm{tw})}n^{\mathcal{O}(1)}$, significantly generalizing a recent algorithm of Gaikwad et al.~of time $\textrm{vc}^{\mathcal{O}(\textrm{vc})}n^{\mathcal{O}(1)}$, where $\textrm{tw}, \textrm{vc}$ denote the input graph's treewidth and vertex cover respectively. Subsequently, we show that both of these algorithms are essentially optimal, since a $\textrm{vc}^{o(\textrm{vc})}n^{\mathcal{O}(1)}$ algorithm would refute the ETH.

With respect to the natural parameter $k$, the aforementioned recent work by Gaikwad et al. claimed an FPT branching algorithm with complexity $10^k n^{\mathcal{O}(1)}$. We point out that this algorithm is incorrect and present a branching algorithm of complexity $9.34^k n^{\mathcal{O}(1)}$.

Profile / bio URL: Manolis Vasilakis

Abstract:

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows.

We give a randomized algorithm, that given a colored $n$-vertex undirected graph, vertices $s$ and $t$, and an integer $k$, finds an $(s,t)$-path containing at least $k$ different colors in time $2^k n^{\mathcal{O}(1)}$. This is the first FPT algorithm for this problem, and it generalizes the algorithm of Bj\"orklund, Husfeldt, and Taslaman~[SODA~2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{\mathcal{O}(1)}$ time algorithm for finding an $(s,t)$-path of length at least $k$.

Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$-vertex undirected graph $G$, a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$, a positive integer weight function on the vertices of $G$, two sets of vertices $S,T \subseteq V(G)$, and integers $p,k,w$, and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$, while minimizing the sum of the lengths of the paths. We give a $2^{p+\mathcal{O}(k^2 \log (q+k))} n^{\mathcal{O}(1)} w$ time randomized algorithm for this problem.

Profile / bio URL: Giannos Stamoulis

Abstract:

There is little doubt that cognitive phenomena are the result of neural activity, and yet there has been slow progress toward articulating an computational theory of how exactly this happens. I will discuss a simplified mathematical model of the brain, which we call NEMO, involving brain areas, spiking neurons, random synapses, local inhibition, Hebbian plasticity, and long-range interneurons -- crucially, there is no backpropagation in NEMO. Emergent behaviors of the resulting dynamical system -- established both analytically and through simulations -- include assemblies of neurons, sequence memorization, one-shot learning, and universal computation. NEMO is also a software-based neuromorphic system that can be simulated efficiently at the scale of tens of millions of neurons, emulating certain high-level cognitive phenomena such as planning and parsing of natural language. I will describe current work aiming at creating through NEMO a *neuromorphic language organ:* a neural tabula rasa which, on input consisting of a modest amount of grounded language, is capable of language acquisition: learning lexicon, syntax, semantics, comprehension, and generation. Finally, and on the plane of scientific methodology, I will argue that experimenting with such brain-like devices, devoid of backpropagation, can reveal novel avenues to learning, and may end up advancing AI.

Profile / bio URL: Christos Papadimitriou

Abstract:

In this talk, I will present some recent (and some less recent) results concerning the long-run behavior of regularized, no-regret learning in finite games. A well-known result in the field states that the empirical frequencies of no-regret play converge to the game's set of coarse correlated equilibria (also known as the Hannan set), and a significant body of work has studied the speed of this convergence. We will discuss some limitations of this correlated, time-average guarantee, and we will then seek to characterize the structural, game-theoretic properties of the sets (or points) that attract the agents' actual sequence of play under regularized learning.

Profile / bio URL: Panayiotis Mertikopoulos

Abstract:

In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the [0,1] interval, and a set of n agents with heterogeneous preferences over pieces of the cake. The goal is to divide the cake among the n agents such that no agent is envious of any other agent. Even under a very general preferences model, this fundamental fair division problem is known to always admit an exact solution where each agent obtains a connected piece of the cake; we study the complexity of finding an approximate solution, i.e., a connected ε-envy-free allocation.

For monotone valuations of cake pieces, Deng, Qi, and Saberi (2012) gave an efficient algorithm for three agents, and it was conjectured by Brânzei and Nisan (2022) that the problem for four agents is hard. We present an efficient algorithm for the case of four agents. We also prove that as soon as the valuations are allowed to be non-monotone, the problem becomes hard, even in the communication model.

Based on joint work with Aviad Rubinstein.

Abstract:

We study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents.

Profile / bio URL: Alkmini Sgouritsa

Abstract:

Our work studies the fair allocation of indivisible items to a set of agents, and falls within the scope of establishing improved approximation guarantees. It is well known by now that the classic solution concepts in fair division, such as envy-freeness and proportionality, fail to exist in the presence of indivisible items. Unfortunately, the lack of existence remains unresolved even for some relaxations of envy-freeness, and most notably for the notion of EFX, which has attracted significant attention in the relevant literature. This in turn has motivated the quest for approximation algorithms, resulting in the currently best known (φ-1)-approximation guarantee by Amanatidis et al (2020), where φ equals the golden ratio. So far, it has been notoriously hard to obtain any further advancements beyond this factor. Our main contribution is that we achieve better approximations, for certain special cases, where the agents agree on their perception of some items in terms of their worth. In particular, we first provide an algorithm with a 2/3-approximation, when the agents agree on what are the top n items (but not necessarily on their exact ranking), with n being the number of agents. To do so, we also study a general framework that can be of independent interest for obtaining further guarantees.

Secondly, we establish the existence of exact EFX allocations in a different scenario, where the agents view the items as split into tiers w.r.t. their value, and they agree on which items belong to each tier. Overall, our results provide evidence that improved guarantees can still be possible by exploiting ordinal information of the valuations.

Profile / bio URL: Christodoulos Santorinaios

Abstract:

We study the problem of fairly allocating indivisible goods among agents which are equipped with leveled valuation functions. Such preferences, that have been studied before in economics and fair division literature, capture a simple and intuitive economic behavior; larger bundles are always preferred to smaller ones. We provide a fine-grained analysis for various subclasses of leveled valuations focusing on two extensively studied notions of fairness, (approximate) MMS and EFX. In particular, we present a general positive result, showing the existence of 2/3-MMS allocations under valuations that are both leveled and submodular. We also show how some of our ideas can be used beyond the class of leveled valuations; for the case of two submodular (not necessarily leveled) agents we show that there is always a 2/3-MMS allocation, complementing a recent previous impossibility result. Then, we switch to the case of subadditive leveled agents, where we are able to show tight (lower and upper) bounds of 1/2 on the approximation factor of MMS. Finally, we show the existence of exact EFX allocations under general leveled valuations via a simple protocol that in addition satisfies several natural economic properties, like incentive compatibility and efficiency.

Joint work with George Christodoulou

Abstract:

Distributed algorithms and architectures are everywhere, and along with them bring faster computation and harder verification. In the heart of the verification effort lies always the the understanding of how exactly a piece of software can execute, and it is exactly there where parallelism and concurrency introduce extra potential execution scenarios and complicate the process. The concept of weak memory approaches this issue from an applied perspective, where the underlying hardware defines what potential executions can occur. Unfortunately the outcome is usually that many, program behaviours are present, additional to the expected ones, and thus the program's safety is even more at risk. In this talk we will first look at exactly how weak memory presents itself through different implementations and then discuss some important concepts and complexity problems concerning the verification of programs in those circumstances.

Profile / bio URL: Elli Anastasiadi

Abstract:

We study the intractability of computing the clearing payments for financial networks consisting of debt contracts and credit default swaps (CDS). Leveraging a novel toolkit named Pure-Circuit (FOCS'22) for proving strong inapproximability in PPAD, we provide explicit higher bounds for the clearing problem.

Profile / bio URL: Stavros Ioannidis

Abstract:

We provide time- and sample-efficient algorithms for learning and testing latent-tree Ising models, i.e. Ising models that may only be observed at their leaf nodes. On the learning side, we obtain efficient algorithms for learning a tree-structured Ising model whose leaf node distribution is close in Total Variation Distance, improving on the results of prior work. On the testing side, we provide an efficient algorithm with fewer samples for testing whether two latent-tree Ising models have leaf-node distributions that are close or far in Total Variation distance. We obtain our algorithms by showing novel localization results for the total variation distance between the leaf-node distributions of tree-structured Ising models, in terms of their marginals on pairs of leaves.

Profile / bio:

Vardis Kandiros is a fifth year graduate student at MIT, working under the supervision of Costis Daskalakis. His research interests are in machine learning theory and high dimensional statistics, and more specifically learning in graphical models. Before coming to MIT, he obtained his bachelors degree in Electrical and Computer Engineering from the National Technical University of Athens.

Abstract:

Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for n unrelated machines is n. In this talk we will provide an outline of a proof that validates the conjecture.

Profile / bio URL: Georgios Christodoulou

Abstract:

Block elimination distance is a parameter on graphs that measures the distance of the biconnected components of a graph from a given class of graphs. When the indicated graph class is the class of edgeless graphs, we call the parameter block treedepth. We prove that block treedepth is equivalent to the minimum number of colors needed to color a graph such that every biconnected subgraph has a vertex of unique color. Additionally, we introduce a special kind of non-proper edge coloring that can serve as an alternative for block treedepth, called cycle edge ranking. Moreover, we make a connection between block treedepth and graph searching games by introducing two versions of the cops and robbers game that can be used to calculate the block treedepth of a graph. Finally, we prove that block treedepth has a polynomial kernel when parameterized by the vertex cover number.

Profile / bio URL: Filippos Mavropoulos

Abstract:

In Partial Positive Influence Domination, given a graph $G=(V,E)$, we seek a minimum-size set of nodes $S\subseteq V$, such that every node $v\in V\setminus S$ has at least $\lceil N_S(v)/2 \rceil$ neighbors in $S$. This definition comes from social networks and the "Majority Illusion" paradox, which has applications in many fields, where there exists a group with a small number of people in the network that every other person has at least half of their friends in this group.

We define the Total version of Partial Positive Influence Domination, where we extend the requirement for nodes in $S$. Any node in $S$ must have at least one neighbor in $S$.

Let $\Delta$ denote the maximum degree in $G$. We prove a first $1 + \ln(\lceil\frac{3}{2}\Delta \rceil - 1)$ approximation for Partial Positive Influence Total Domination.

Abstract:

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) $G^*$ while minimizing the number of interventions made. In our setting, we are additionally given side information about $G^*$ as advice, e.g.\ a DAG $G$ purported to be $G^*$. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG $G$, we design an adaptive search algorithm to recover $G^*$ whose intervention cost is at most $\mathcal{O}(\max\{1, \log \psi\})$ times the cost for verifying $G^*$; here, $\psi$ is a distance measure between $G$ and $G^*$ that is upper bounded by the number of variables $n$, and is exactly 0 when $G=G^*$. Our approximation factor matches the state-of-the-art for the advice-less setting.

Profile / bio URL: Themis Gouleakis

Abstract:

This paper studies delegation in a model of discrete choice. In the delegation problem, an uninformed principal must consult an informed agent to make a decision. Both the agent and principal have preferences over the decided-upon action which vary based on the state of the world, and which may not be aligned. The principal may commit to a mechanism, which maps reports of the agent to actions. When this mechanism is deterministic, it can take the form of a menu of actions, from which the agent simply chooses upon observing the state. In this case, the principal is said to have delegated the choice of action to the agent. We consider a setting where the decision being delegated is a choice of a utility-maximizing action from a set of several options. We assume the shared portion of the agent's and principal's utilities is drawn from a distribution known to the principal, and that utility misalignment takes the form of a known bias for or against each action. We provide tight approximation analyses for simple threshold policies under three increasingly general sets of assumptions. With independently-distributed utilities, we prove a 3-approximation. When the agent has an outside option the principal cannot rule out, the constant-approximation fails, but we prove a log⁡ρ/log⁡log⁡ρ-approximation, where ρ is the ratio of the maximum value to the optimal utility. We also give a weaker but tight bound that holds for correlated values, and complement our upper bounds with hardness results. One special case of our model is utility-based assortment optimization, for which our results are new.

Profile / bio URL: Manolis Pountourakis

Abstract:

Multi-agent learning applications motivate the study of games that have infinitely many strategies or have non-concave utilities. Equilibrium existence in these games is not guaranteed, and when equilibria do not exist it is not clear what solutions should be targeted by learning. We provide conditions characterizing when min-max and coarse correlated equilibria exist in terms of complexity measures of the function classes wherein the players utility functions reside, and provide practical algorithms whose iterations are efficiently computable and which have guaranteed convergence to equilibrium when our conditions are met.

Profile / bio:

Constantinos (aka "Costis") Daskalakis is the Avanessians Professor of Electrical Engineering and Computer Science at MIT. He holds a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, and a PhD in Electrical Engineering and Computer Science from UC Berkeley. He works on Computation Theory and its interface with Game Theory, Economics, Probability Theory, Machine Learning and Statistics. He has resolved long-standing open problems about the computational complexity of Nash equilibrium, and the mathematical structure and computational complexity of multi-item auctions. His current work focuses on multi-agent learning, high-dimensional statistics, learning from biased and dependent data, causal inference and econometrics. He has been honored with the ACM Doctoral Dissertation Award, the Kalai Prize from the Game Theory Society, the Sloan Fellowship in Computer Science, the SIAM Outstanding Paper Prize, the Microsoft Research Faculty Fellowship, the Simons Investigator Award, the Rolf Nevanlinna (now called Abacus) Prize from the International Mathematical Union, the ACM Grace Murray Hopper Award, the Bodossaki Foundation Distinguished Young Scientists Award, the ACM SIGECOM Test of Time Award, and the FOCS 2022 Test of Time Award. He is a fellow of ACM.