9:30  10:30 
Two Models for Scheduling under Uncertainty
Evripidis Bampis, Sorbonne University
Abstract:

10:30  11:00 
Coffee Break 
11:00  12:15 
Descriptive complexity of counting problems the decision version of which is easy
Aggeliki Chalki, NTUA
Abstract:
The class #P is the class of functions that count the number of solutions to problems in NP. Since very few counting problems can be exactly computed in polynomial time (e.g. counting spanning trees), the interest of the community has
turned to the complexity of approximating them. To this end the class #PE of problems in #P the decision version of which is in P, is of great significance.
We focus on a subclass of #PE, namely TotP, which is the class of functions that count the total number of paths of NPTMs. TotP contains all selfreducible #PE functions and it is robust, in the sense that it has natural complete
problems and it is closed under addition, multiplication and subtraction by one.
We present logical characterizations of TotP and two other robust subclasses of this class building upon two seminal works in the area of descriptive complexity for counting problems (by Saluja et al. 1995 and Arenas et al. 2020).
Specifically, to capture TotP, we use recursion on functions over secondorder variables which, we believe, is of independent interest.
Joint work with Antonis Achilleos, Eleni Bakali, and Aris Pagourtzis
PureCircuit: Strong Inapproximability for PPAD
Alexandros Hollender, University of Oxford
Abstract:
We introduce the PureCircuit problem: a new tool for proving hardness of approximation for problems in the class PPAD. We apply this new technique to show tight inapproximability results for various Nash equilibrium computation
problems. Namely, the following problems are all PPADcomplete:
 computing an $\varepsilon$Nash equilibrium in a graphical game for any $\varepsilon < 1/2$,
 computing an $\varepsilon$wellsupported Nash equilibrium in a graphical game for any $\varepsilon < 1$,
 computing an $\varepsilon$wellsupported Nash equilibrium in a polymatrix game for any $\varepsilon < 1/3$. We show that these hardness results are tight for the case of twoaction games by providing matching upper bounds.
Joint work with Argyrios Deligkas, John Fearnley, and Themistoklis Melissourgos.
Almost Universally Optimal Distributed Laplacian Solvers via LowCongestion Shortcuts
Themis Gouleakis, National University of Singapore
Abstract:
In this talk, we refine the distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) via the GhaffariHaeupler framework (SODA `16) of lowcongestion shortcuts. Specifically, if
$\varepsilon > 0$ is the error of the Laplacian solver, we obtain two main results:
 In the supported version of the CONGEST model, we establish an almost universally optimal Laplacian solver. Namely, we show that any Laplacian system on an $n$node graph with shortcut quality $\text{SQ}(G)$ can be
solved after $n^{o(1)} \text{SQ}(G) \log(1/\varepsilon)$ rounds, almost matching our lower bound of $\widetilde{\Omega}(\textrm{SQ}(G))$ rounds on any graph $G$. Our techniques also imply almost universally optimal Laplacian
solvers
in the full generality of CONGEST, conditional on the efficient construction of shortcuts. In particular, they unconditionally imply a novel $D n^{o(1)} \log (1/\varepsilon)$ Laplacian solver for excludedminor graphs with
hopdiameter $D$.
 Following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the nodecapacitated clique (NCC) model. In this model, we show
the
existence of a Laplacian solver with round complexity $n^{o(1)} \log(1/\varepsilon)$.
The unifying thread of these results, and our main technical contribution, is the development of nearlyoptimal distributed algorithms for a novel congested generalization of the standard partwise aggregation problem.
This primitive accelerates the Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye, and we believe it will find further applications in the future.

12:15  12:30 
Short break 
12:30  13:45 
Full Analysis of Nakamoto Consensus in BoundedDelay Networks
Nikos Leonardos, NKUA
Abstract:
Nakamoto consensus, arguably the most exciting development in
distributed computing in the last few years, is in a sense a recasting
of the traditional statemachinereplication problem in an
unauthenticated setting, where furthermore parties come and go without
warning. The protocol relies on a cryptographic primitive known as
proof of work (PoW) which is used to throttle message passing with the
PoW difficulty level being appropriately adjusted throughout the
course of the protocol execution. While the original formulation was
only accompanied by rudimentary analysis, significant and steady
progress has been made in abstracting the protocol’s properties and
providing a formal analysis under various restrictions and protocol
simplifications. Still, a full analysis of the protocol that includes
its target recalculation and, notably, the timestamp adjustment
mechanisms which equip it to operate in its intended setting of
bounded communication delays, imperfect clocks and dynamic
participation, has remained open. This paper’s main result fills this
final gap in terms of its analysis in the Byzantine setting presenting
a proof that Nakamoto’s protocol achieves, under suitable conditions,
consistency and liveness in the above setting. A number of technical
tools and techniques are introduced that may be of independent
interest in the analysis of blockchain protocols.
Joint work with Juan Garay and Aggelos Kiayias.
MAXCUT for Trianglefree Graphs
Felix Clemen, Karlsruher Institut für Technologie
Abstract:
A wellknown conjecture by Erdős states that every trianglefree graph on n vertices can be made bipartite by removing at most $(n^2)/25$ edges. We will present progress on this conjecture in different directions. In particular, we
explore a connection of this conjecture to spectral theory.
Denote by $q_n(G)$ the smallest eigenvalue of the signless laplacian of a graph G. Brandt conjectured in 1997 that for regular trianglefree graphs $q_n(G)$ <= $(4/25)n$. We prove Brandt's conjecture in a strong form by confirming it
for all trianglefree graphs.
This is joint work with József Balogh, Bernard Lidický, Sergey Norin and Jan Volec.
Complexity of Finding Maximum Locally Irregular Induced Subgraphs
Nikos Melissinos, Paris Dauphine
Abstract:
If a graph $G$ is such that no two adjacent vertices of $G$ have the same
degree, we say that $G$ is \emph{locally irregular}. In this work we introduce
and study the problem of identifying a largest induced subgraph of a given
graph $G$ that is locally irregular. Equivalently, given a graph $G$, find a subset
$S$ of $V(G)$ with minimum order, such that by deleting the vertices of $S$
from $G$ results in a locally irregular graph; we denote with $I(G)$ the order of
such a set $S$. We first examine some easy graph families, namely paths,
cycles, trees, complete bipartite and complete graphs. However, we show that
the decision version of the introduced problem is NPComplete, even for
restricted families of graphs, such as subcubic planar bipartite, or cubic bipartite
graphs. We then show that we can not even approximate an optimal solution
within a ratio of $\mathcal{O}(n^{1\frac{1}{k}})$, where $k\geq 1$ and $n$ is the
order the graph, unless $P=NP$, even when the input graph is bipartite.
Then, looking for more positive results, we turn our attention towards computing
$I(G)$ through the lens of parameterised complexity. In particular, we provide
two algorithms that compute $I(G)$, each one considering different parameters.
The first one considers the size of the solution $k$ and the maximum degree
$\Delta$ of $G$ with running time $(2\Delta)^kn^{\mathcal{O}(1)}$, while the
second one considers the treewidth $tw$ and $\Delta$ of $G$, and has running
time $\Delta^{2tw}n^{\mathcal{O}(1)}$. Therefore, we show that the problem is
FPT by both $k$ and $tw$ if the graph has bounded maximum degree $\Delta$.
Since these algorithms are not FPT for graphs with unbounded maximum
degree (unless we consider $\Delta + k$ or $\Delta + tw$ as the parameter), it is
natural to wonder if there exists an algorithm that does not include additional
parameters (other than $k$ or $tw$) in its dependency.
We answer negatively, to this question, by showing that our algorithms are
essentially optimal. In particular, we prove that there is no algorithm that
computes $I(G)$ with dependence $f(k)n^{o(k)}$ or $f(tw)n^{o(tw)}$, unless the
ETH fails.

13:45  15:00 
Lunch break 
15:00  16:00 
Data Driven Algorithm Design: Learning to Search
Christos Tzamos, UWMadison and NKUA
Abstract:

16:00  16:30 
Coffee break 
16:30  17:45 
Constant Inapproximability for PPA
Themistoklis Melissourgos, University of Essex
Abstract:
We show that $\varepsilon$Consensus Halving is PPAcomplete even when the parameter $\varepsilon$ is a constant. Consensus Halving is a fundamental fair division problem which was the first natural problem shown to be complete for
the class PPA, and all subsequent PPAcompleteness results for other natural problems have been obtained by reducing from it. In fact, we prove that PPAcompleteness holds for any constant $\varepsilon < 1/5$. This immediately implies
constant inapproximability results for all known natural PPAcomplete problems, including "Necklace Splitting" , "Discrete Ham Sandwich" , two variants of the "Pizza Sharing" problem, and finding fair independent sets in cycles and
paths.
Joint work with Argyrios Deligkas, John Fearnley, and Alexandros Hollender.
FirstOrder Algorithms for MinMax Optimization in Geodesic Metric Spaces
Emmanouil Vasileios Vlatakis Gkaragkounis, UC Berkeley
Abstract:
From optimal transport to robust dimensionality reduction, a plethora of machine learning applications can be cast into the minmax optimization problems over Riemannian manifolds. Though many minmax algorithms have been analyzed in
the Euclidean setting, it has proved elusive to translate these results to the Riemannian case. Zhang et al. [2022] have recently shown that geodesic convex concave Riemannian problems always admit saddlepoint solutions. Inspired by
this result, we study whether a performance gap between Riemannian and optimal Euclidean space convexconcave algorithms is necessary. We answer this question in the negativewe prove that the Riemannian corrected extragradient (RCEG)
method achieves lastiterate convergence at a linear rate in the geodesically stronglyconvexconcave case, matching the Euclidean result. Our results also extend to the stochastic or nonsmooth case where RCEG and Riemanian gradient
ascent descent (RGDA) achieve nearoptimal convergence rates up to factors depending on curvature of the manifold.
Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Fivos Kalogiannis, UC Irvine
Abstract:
Computing Nash equilibrium policies is a central problem in multiagent reinforcement learning that has received extensive attention both in theory and in practice. However, in light of computational intractability barriers in
generalsum games, provable guarantees have been thus far either limited to fully competitive or cooperative scenarios or impose strong assumptions that are difficult to meet in most applications.
In this work, we depart from those prior results by investigating infinitehorizon adversarial team Markov games, a natural and wellmotivated class of games in which a team of identicallyinterested playerswithout any explicit
coordination or communicationis competing against an adversarial player. This setting allows for a unifying treatment of zerosum Markov games and Markov potential games, and serves as a step to model more realistic strategic
interactions that feature both competing and cooperative interests. Our main contribution is the first algorithm for computing stationary $\epsilon$approximate Nash equilibria in adversarial team Markov games with complexity that is
polynomial in all the natural parameters of the problem and $1/\epsilon$.
The proposed algorithm is particularly natural and practical, and it is based on performing independent policy gradient steps for each player in the team, in tandem with bestresponses from the side of the adversary; in turn, the
policy for the adversary is then obtained by solving the dual of a carefully constructed linear program. Our analysis leverages nonstandard techniques to establish the KKT optimality conditions for a nonlinear program with nonconvex
constraints, thereby leading to a natural interpretation of the induced Lagrange multipliers. Along the way, we significantly extend an important characterization of optimal policies due to Von Stengel and Koller (GEB `97) in the
context of adversarial (normalform) team games.

17:45  18:00 
Short Break 
18:00  19:15 
Strong Approximations and Irrationality in Financial Networks with Derivatives
Stavros Ioannidis, King's College London
Abstract:
Financial networks model a set of financial institutions interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main
computational
challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery
rates form the
set of fixed points of a simple function, and that these fixed points can be irrational. We study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate
solutions may
contain misleading information regarding the actual financial state of an institution. On this basis, we study the complexity of finding a strongly approximate solution, and show FIXPcompleteness. We then study the structural
properties required
for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of nonlinear polynomials. In
the absence
of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of, PPAD.
Metric Distortion Bounds under Limited Information
Panagiotis Patsilinakos, NTUA
Abstract:
In this work we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechanisms which perform a sequence of pairwise comparisons
between
candidates. We show that a widelypopular deterministic mechanism employed in most knockout phases yields distortion $O(\log m)$ while eliciting only $m1$ out of $\Theta(m^2)$ possible pairwise comparisons, where m represents the
number of
candidates. Our analysis for this mechanism leverages a powerful technical lemma recently developed by (Kempe, ΑΑΑΙ 2020a). We also provide a matching lower bound on its distortion. In contrast, we prove that any mechanism which
performs fewer
than $m1$ pairwise comparisons is destined to have unbounded distortion. Moreover, we study the power of deterministic mechanisms under incomplete rankings. Most notably, when every agent provides her $k$top preferences we show an
upper bound
of $6m/k+1$ on the distortion, for any $k \in \{1, 2, …, m\}$. Thus, we substantially improve over the previous bound of $12m/k$ recently established by (Kempe, AAAI 2020a, Kempe AAAI 2020b), and we come closer to matching the
bestknown lower
bound. Finally, we are concerned with the sample complexity required to ensure nearoptimal distortion with high probability. Our main contribution is to show that a random sample of $\Theta(m/\epsilon^2)$ voters suffices to guarantee
distortion
$3+\epsilon$ with high probability, for any sufficiently small $\epsilon>0$.. This result is based on analyzing the sensitivity of the deterministic mechanism introduced by (Gkatzelis, Halpern, and Shah, FOCS 2020). Importantly, all
of our
samplecomplexity bounds are distributionindependent.
From an experimental standpoint we present several empirical findings on reallife voting applications, comparing the scoring systems employed in practice with a mechanism explicitly minimizing (metric) distortion. Interestingly, for
our case
studies we find that the winner in the actual competition is typically the candidate who minimizes the distortion.
Joint work with Ioannis Anagnostides and Dimitris Fotakis
FaultTolerant Total Domination
Ioannis Vaxevanakis, Department of Informatics and Telecommunications, NKUA
Abstract:
In \textit{total domination}, given a graph $G=(V,E)$, we seek a minimumsize set of nodes $S\subseteq V$, such that every node in $V \setminus S$ has at least one neighbor in $S$ and every node in $S$ also has at least one neighbor
in $S$. We
define the \textit{faulttolerant} version of total domination, where we extend the requirement for nodes in $V \setminus S$. Any node in $V \setminus S$ must have at least $m$ neighbors in $S$. Let $\Delta$ denote the maximum degree
in $G$. We
prove a first $1 + \ln(\Delta + m  1)$ approximation for faulttolerant total domination.


