ACAC '21

16th Athens Colloquium on Algorithms and Complexity

August 26-27, 2021, Online

Organized by National Technical University of Athens


Scope

ACAC is an annual meeting in Athens aiming to bring together researchers working in all areas of the theory of algorithms and computational complexity. It serves as a lively forum for presenting research results that are in a preliminary stage or have been recently accepted / presented in some major conference. Contributions may appear, fully or partially, in informal electronic proceedings available only to the participants (subject to authors' approval). The language of the workshop is English.


Registration

There are no registration fees. However, participants should register for administrative purposes, by filling the registration form no later than 25/8.


Contributions

Participants interested in giving a presentation should register, providing a tentative title and a short abstract,in text or latex format, either in the registration form (click the "Would you like to give a talk?" checkbox), or by sending an e-mail to acac21@corelab.ntua.gr, no later than 10/8. The organizers will make every possible effort so that all interested participants present their work (subject to scheduling constraints).


Topics of interest

Include, but are not limited to:

  • Analysis of Algorithms, Randomized and Approximation Algorithms
  • Computational Complexity
  • Data Structures
  • Cryptography
  • Graph Theory
  • Algorithmic Game Theory
  • Computational Geometry
  • Combinatorial Optimization
  • Algorithmic Algebra and Coding Theory
  • Theoretical Aspects of Databases
  • Computational Biology
  • Quantum Computing
  • Parallel and Distributed Computing
  • Machine Learning
  • Applications of Logic


Organization of ACAC 2021 is partially supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the ``First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant'', project BALSAM, HFRI-FM17-1424.


News

  • Important Dates

    Registration Deadline: 25/8
    Submission Deadline:    10/8

Organizing Committee

  • Dimitris Fotakis
  • Elias Koutsoupias
  • Evangelos Markakis
  • Aris Pagourtzis
  • Stathis Zachos
  • Vassilis Zissimopoulos


Local Arrangements

  • Antonis Antonopoulos
  • Pourandokht Behrouz
  • Angeliki Chalki
  • Sotiris Dimos
  • Aggeliki Mathioudaki
  • Giannis Papaioannou
  • Petros Potikas


Links

Previous ACACs


Share this event

Contact


For submission and further details please contact the organizers by email to acac21@corelab.ntua.gr.

Register


Would you like to give a talk?  
    

Hello

PROGRAM


Thursday, August 26

(*Click on Go to Abstract to view the details of each talk.)
11:00 - 12:00
Plenary Session

2-Connectivity in Directed Graphs    Go to Abstract
Giuseppe Italiano, LUISS Guido Carli University
Abstract:
We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only very recently.

Short bio:
After getting a Ph.D. in Computer Science at Columbia University, he worked as a Research Staff Member at the IBM T.J. Watson Research Center in Yorktown Heights (New York). When he was 33 years old, he won a National competition for Full Professor and went back to Italy. Before joining LUISS University, he was professor of computer science at University of Salerno, University "Ca' Foscari" of Venice, and University of Rome "Tor Vergata". Giuseppe F. Italiano has worked on a wide variety of problems, producing highly-cited results on a number of different areas. Most of his research is centered around the design, analysis and engineering of algorithms for big data sets, with applications to several areas, including graph theory, social network analysis, computer and network security, and computational biology. His background, which includes also a five-year experience in industrial research, puts him in a unique position to carry out work that combines basic research with strong focus on applications. In 2016 Giuseppe was nominated EATCS Fellow for "fundamental contributions to the design and analysis of algorithms for solving theoretical and applied problems in graphs and massive data sets, and for his role in establishing the field of algorithm engineering".
12:00 - 12:20 Break
12:20 - 14:00
Session 1

Resource-Aware Cost-Sharing Mechanisms with Priors    Go to Abstract
Vasilis Gkatzelis, Drexel University
Abstract: In a decentralized system with m machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games.
Recent work introduced the class of "resource-aware" cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families. In this paper we show that if we enhance the class of resource-aware mechanisms with some prior information regarding the users, then they can achieve low PoA for a much more general family of cost functions. We first show that, as long as the mechanism knows just two of the participating users, then it can assign special roles to them and ensure a constant PoA. We then extend this idea to settings where the mechanism has access to the probability with which each user is present in the system. For all these instances, we provide a mechanism that achieves an expected PoA that is logarithmic in the expected number of users.

Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness    Go to Abstract
Philip Lazos, IOHK
Abstract: We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers and, therefore, a mechanism in our setting is an algorithm that takes as input the reported---rather than the true---values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely envy-freeness up to one good} (EF1), and envy-freeness up to any good (EFX), and we positively answer the above question. In particular, we study two algorithms that are known to produce such allocations in the non-strategic setting: Round-Robin (EF1 allocations for any number of agents) and a cut and choose algorithm of Plaut and Roughgarden (EFX allocations for two agents). For Round-Robin we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, while for the algorithm of Plaut and Roughgarden we show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria which all induce EFX allocations.

Strategyproof Facility Location in Perturbation Stable Instances    Go to Abstract
Panagiotis Patsilinakos, National Technical University of Athens
Abstract: We consider $k$-Facility Location games, where $n$ strategic agents report their locations on the real line, and a mechanism maps them to $k \ge 2$ facilities. Each agent seeks to minimize her distance to the nearest facility. We are interested in (deterministic or randomized) strategyproof mechanisms without payments that achieve a reasonable approximation ratio to the optimal social cost of the agents. To circumvent the inapproximability of $k$-Facility Location by deterministic strategyproof mechanisms, we restrict our attention to perturbation stable instances. An instance of $k$-Facility Location on the line is $\gamma$-perturbation stable (or simply, $\gamma$-stable), for some $\gamma \ge 1$, if the optimal agent clustering is not affected by moving any subset of consecutive agent locations closer to each other by a factor at most $\gamma$. We show that the optimal solution is strategyproof in $(2+\sqrt{3})$-stable instances whose optimal solution does not include any singleton clusters, and that allocating the facility to the agent next to the rightmost one in each optimal cluster (or to the unique agent, for singleton clusters) is strategyproof and $(n-2)/2$-approximate for $5$-stable instances (even if their optimal solution includes singleton clusters). On the negative side, we show that for any $k \ge 3$ and any $\delta > 0$, there is no deterministic anonymous mechanism that achieves a bounded approximation ratio and is strategyproof in $(\sqrt{2}-\delta)$-stable instances. We also prove that allocating the facility to a random agent of each optimal cluster is strategyproof and $2$-approximate in $5$-stable instances. To the best of our knowledge, this is the first time that the existence of deterministic (resp. randomized) strategyproof mechanisms with a bounded (resp. constant) approximation ratio is shown for a large and natural class of $k$-Facility Location instances.

On Blame Attribution for Accountable Multi-Agent Sequential Decision Making    Go to Abstract
Stelios Triantafyllou, Max Planck Institute for Software Systems
Abstract: Blame attribution is one of the key aspects of accountable decision making, as it provides means to quantify the responsibility of an agent for a decision making outcome. In this paper, we study blame attribution in the context of cooperative multi-agent sequential decision making. As a particular setting of interest, we focus on cooperative decision making formalized by Multi-Agent Markov Decision Processes (MMDP), and we analyze different blame attribution methods derived from or inspired by existing concepts in cooperative game theory. We formalize desirable properties of blame attribution in the setting of interest, and we analyze the relationship between these properties and the studied blame attribution methods. Interestingly, we show that some of the well known blame attribution methods, such as Shapley value, are not performance-incentivizing, while others, such as Banzhaf index, may over-blame agents. To mitigate these value misalignment and fairness issues, we introduce a novel blame attribution method, unique in the set of properties it satisfies, which trade-offs explanatory power (by under-blaming agents) for the aforementioned properties. We further show how to account for uncertainty about agents' decision making policies, and we experimentally: a) validate the qualitative properties of the studied blame attribution methods, and b) analyze their robustness to uncertainty.
14:00 - 15:00 Break
15:00 - 16:15
Session 2

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games    Go to Abstract
Ioannis Panageas, UC Irvine
Abstract: Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent utilities are perfectly aligned with each other via a common potential function. Can this intuitive framework be transplanted in the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove polynomial convergence of independent policy gradient (and its stochastic variant) to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings.

Min-max optimization in team zero-sum games    Go to Abstract
Fivos Kalogiannis, National Technical University of Athens
Abstract: We focus on min-max optimization in team zero-sum games. These are games that do not satisfy the minimax theorem and have a duality gap. We show that convergence to a Nash Equilibrium is impossible using Gradient Descent Ascent (GDA), its optimistic variant, extra gradient etc. The key observation is that the Nash Equilibrium might be a saddle point of the underlying optimization landscape. Using techniques from control theory, we complement our negative results by designing a modified GDA that converges locally to Nash equilibria.

Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits    Go to Abstract
Orestis Papadigenopoulos, The University of Texas at Austin
Abstract: A recent line of research focuses on the study of stochastic multi-armed bandits (MAB), in the case where temporal correlations of specific structure are imposed between the player's actions and the reward distributions of the arms (see, e.g., [Kleinberg and Immorlica, 2018]). These correlations lead to (sub-)optimal solutions that exhibit interesting dynamical patterns -- a phenomenon that yields new challenges both from an algorithmic as well as a learning perspective. In this work, we extend the above direction to a combinatorial semi-bandit setting and study a variant of stochastic MAB, where arms are subject to matroid constraints and each arm becomes unavailable (blocked) for a fixed number of rounds after each play. A natural common generalization of the state-of-the-art for blocking bandits, and that for matroid bandits, only guarantees a $1/2$-approximation for general matroids. In this paper we develop the novel technique of correlated (interleaved) scheduling, which allows us to obtain a polynomial-time $(1 - 1/e)$-approximation algorithm (asymptotically and in expectation) for any matroid. Along the way, we discover an interesting connection to a variant of Submodular Welfare Maximization, for which we provide (asymptotically) matching upper and lower approximability bounds. In the case where the mean arm rewards are unknown, our technique naturally decouples the scheduling from the learning problem, and thus allows to control the $(1-1/e)$-approximate regret of a UCB-based adaptation of our online algorithm.

16:15 - 16:30 Break
16:30 - 17:45
Session 3

On the Complexity of Equilibrium Computation in First-Price Auctions    Go to Abstract
Aris Filos-Ratsikas, University of Liverpool
Abstract: We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an epsilon-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

Pizza Sharing is PPA-hard    Go to Abstract
Themistoklis Melissourgos, TU Munich
Abstract: We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also show that decision variants of the square-cut problem are hard: we show that the approximate problem is NP-complete, and the exact problem is ETR-complete.

A spectral independence view on hardspheres via block dynamics    Go to Abstract
Andreas Göbel, Hasso Plattner Institute
Abstract: The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions.

17:45 - 18:00 Break
18:00 - 19:00
Plenary Session

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets    Go to Abstract
Mihalis Yannakakis, Columbia University
Abstract:
In 1979, Hylland and Zeckhauser gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following results.
  • - A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., when the agent's utilities come from a bi-valued set.
  • - In general, there are instances that have only irrational equilibria.
  • - Computing an exact equilibrium solution is in FIXP.
  • - Computing an approximate equilibrium is PPAD-complete, and this holds even for 4-valued utilities.
  • - Computing an equilibrium that maximizes approximately the social welfare (the weight of the matching) within a certain contant factor is NP-hard.
The talk is based on joint works with Vijay Vazirani, and Thomas Chen, Xi Chen and Binghui Peng.

Bio:
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University. Prior to joining Columbia, he was Head of the Computing Principles Research Department at Bell Labs, and Professor of Computer Science at Stanford University. Dr. Yannakakis received his PhD from Princeton University. He has served on the editorial boards of several journals, including as the editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. Dr. Yannakakis is a recipient of the Knuth Prize, a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, of Academia Europaea, and he is a Fellow of the ACM, and a Bell Labs Fellow.

Friday, August 27

(*Click on Go to Abstract to view the details of each talk.)
11:00 - 12:00
Plenary Session

Single cell dissection of human disease circuitry    Go to Abstract
Manolis Kellis, MIT
Abstract:
Disease-associated nucleotides lie primarily in non-coding regions, increasing the urgency of understanding how gene-regulatory circuitry impacts human disease. To address this challenge, we generate tran-scriptional and epigenomic maps of 823 human tissues, 1500 individuals, and 7.5 million single cells. We link variants to target genes, upstream regulators, cell types of action, and perturbed pathways, and predict causal genes and regions to provide unbiased views of disease mechanisms, sometimes re-shaping our understanding. We find that Alzheimer’s variants act primarily through immune processes, rather than neuronal processes, and the strongest genetic association with obesity acts via energy storage/dissipation rather than appetite/exercise decisions. We combine single-cell profiles, tissue-level variation, and genetic variation across healthy and diseased individuals to deconvolve bulk profiles into single-cell profiles, to recognize changes in cell type proportion associated with disease and aging, to partition genetic effects in-to the individual cell typeswhere they act, and to recognize cell-type-specific and disease-associated somatic mutations in exonic regions indicative of mosaicism. We expand these methods to electronic health records to recognize meta-phenotypes associated with combinations of clinical notes, prescriptions, lab tests, and billing codes, to impute missing phenotypes in sparse medical records, and to recognize the mo-lecular pathways underlying complex meta-phenotypes in genotyped individualsby integration of molecular phenotypes imputed in disease-relevant cell types. Lastly, we develop programmable and modular technologies for manipulating these pathways by high-throughput reporter assays, genome editing,and gene targeting in human cells and mice, demonstrating tissue-autonomous therapeutic avenues in Alzheimer’s, obesity, and cancer. These results provide a roadmap for translating genetic findings into mechanistic insights and ultimately new therapeutic avenues for complex disease and cancer.
Bio:
Manolis Kellis is a professor of computer science at MIT, a member of the Broad Institute of MIT and Harvard, a principal investigator of the Computer Science and Artificial Intelligence Lab at MIT, and head of the MIT Computational Biology Group (compbio.mit.edu). His research includes disease circuitry, genetics, genomics, epigenomics,coding genes, non-coding RNAs, regulatory genomics, and comparative genomics, applied to Alzheimer's Disease, Obesity, Schizophrenia, Cardiac Disorders, Cancer, and Immune Disorders, and multiple other disorders. He has led several large-scale genomics projects, including the Roadmap Epigenomics project, the ENCODE project, the Genotype Tissue-Expression (GTEx) project, and comparative genomics projects in mammals, flies, and yeasts. He received the US Presidential Early Career Award in Science and Engineering (PECASE) by US President Barack Obama, the Mendel Medal for Outstanding Achievements in Science, the NSF CAREER award, the Alfred P.Sloan Fellowship, the Technology Review TR35 recognition, the AIT Niki Award,and the Sprowls award for the best Ph.D. thesis in computer science at MIT. He has authored over 240 journal publications cited more than 115,000 times. He has obtained more than 20 multi-year grants from the NIH, and his trainees hold faculty positions at Stanford, Harvard, CMU, McGill, Johns Hopkins, UCLA, and other top universities. He lived in Greece and France before moving to the US, and he studied and conducted research at MIT, the Xerox Palo Alto Research Center, and the Cold Spring Harbor Lab. For more info, see: compbio.mit.edu and kellislab.com.
12:00 - 12:15 Break
12:15 - 13:30
Session 4

Faster Approximate Pattern Matching: A Unified Approach    Go to Abstract
Panagiotis Charalampopoulos, The Interdisciplinary Center Herzliya
Abstract: Approximate pattern matching is a natural and well-studied problem on strings: Given a text T, a pattern P, and a threshold k, find (the starting positions of) all substrings of T that are at distance at most k from P. We consider the two most fundamental string metrics: the Hamming distance and the edit distance. Under the Hamming distance, we search for substrings of T that have at most k mismatches with P, while under the edit distance, we search for substrings of T that can be transformed to P with at most k edits. Exact occurrences of P in T have a very simple structure: If we assume for simplicity that $|T| \le 3|P|/2$ and trim T so that P occurs both as a prefix and as a suffix of T, then both P and T are periodic with a common period. However, an analogous characterization for the structure of occurrences with up to k mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are $O(k^2)$ k-mismatch occurrences of P in T, or both P and T are at Hamming distance $O(k)$ from strings with a common period $O(m/k)$. We tighten this characterization by showing that there are $O(k)$ k-mismatch occurrences in the case when the pattern is not (approximately) periodic, and we lift it to the edit distance setting, where we tightly bound the number of k-edit occurrences by $O(k^2)$ in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. We showcase the generality of our framework with results for the fully-compressed setting (where T and P are given as a straight-line programs) and for the dynamic setting (where we extend a data structure of Gawrychowski et al. [SODA'18]).
A longer abstract can be found here: https://arxiv.org/pdf/2004.08350.pdf.
This paper was presented in FOCS 2020.

On the Approximability of Multistage Min-Sum Set Cover    Go to Abstract
Stratis Skoulakis, Singapore University of Technology and Design
Abstract: TBA

Faster Algorithms for k-Subset Sum and Variations    Go to Abstract
Manolis Vasilakis, National Technical University of Athens
Abstract: We present new, faster pseudopolynomial time algorithms for the $k$-Subset Sum problem, defined as follows: given a set $Z$ of $n$ positive integers and $k$ targets $t_1, \ldots, t_k$, determine whether there exist $k$ disjoint subsets $Z_1,\dots,Z_k \subseteq Z$, such that $\Sigma(Z_i) = t_i$, for $i = 1, \ldots, k$. Assuming $t = \max \{ t_1, \ldots, t_k \}$ is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm can solve the problem in $O(n t^k)$ time. We build upon recent advances on extsc{Subset Sum} due to Koiliaris and Xu [Koil19] and Bringmann [Brin17] in order to provide faster algorithms for $k$-Subset Sum. We devise two algorithms: a deterministic one of time complexity $ \tilde{O}(n^{k / (k+1)} t^k)$ and a randomised one of $ \tilde{O}(n + t^k)$ complexity. We further demonstrate how these algorithms can be used in order to cope with variations of $k$-Subset Sum, namely Subset Sum Ratio, $k$-Subset Sum Ratio and Multiple Subset Sum.

13:30 - 14:30 Break
14:30 - 15:30
Plenary Talk

Quantum Machine Learning: Prospects And Challenges    Go to Abstract
Iordanis Kerenidis, CNRS-University of Paris and QC Ware
Abstract: We will review recent work on Quantum Machine Learning and discuss the prospects and challenges of applying this new exciting computing paradigm to machine learning applications.

Bio:
Iordanis Kerenidis (CNRS and QC Ware) received his Ph.D. from the Computer Science Department at the University of California, Berkeley, in 2004. After a two-year postdoctoral position at the Massachusetts Institute of Technology, he joined the Centre National de Recherche Scientifique in Paris as a permanent researcher. He has been the coordinator of a number of EU-funded projects including an ERC Grant, and he is the founder and director of the Paris Centre for Quantum Computing. His research is focused on quantum algorithms for machine learning and optimization, including work on recommendation systems, classification and clustering. He is currently working as the Head of Quantum Algorithms Int. at QC Ware Corp.
15:30 - 15:45 Break
15:45 - 17:00
Session 5

The Largest Connected Subgraph Game    Go to Abstract
Foivos Fioravantes, Université Côte d’Azur, CNRS, Inria, I3S, France
Abstract: In this talk, we introduce the largest connected subgraph game, played on a graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph of G whose order is greater than the order of any blue (red, resp.) connected subgraph of G. We first prove that Bob can never win this game, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that the problem of recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give a linear time algorithm that determines the outcome of the game in cographs.
This is a joint work with Julien Bensmail, Fionn Mc Inerney, and Nicolas Nisse.

Byzantine Fault Tolerant Symmetric-Persistent Circle Evacuation    Go to Abstract
Giannis Papaioannou, National Technical University of Athens
Abstract: We consider $(n,f)$-evacuation on a circle, an evacuation problem of a hidden exit on the perimeter of a unit radius circle for $n>1$ robots, $f$ of which are faulty. All the robots start at the center of the circle and move with maximum speed~1. Robots must first find the exit and then move there to evacuate in minimum time. The problem is considered complete when all the honest robots know the correct position of the exit and the last honest robot has evacuated through the exit. During the search, robots can communicate wirelessly. We focus on symmetric-persistent algorithms, that is, algorithms in which all robots move directly to the circumference, start searching the circle moving in the same direction (cw or ccw), and do not stop moving around the circle before receiving information about the exit. We study the case of $(n,1)$ and $(n,2)$ evacuation. We first prove a lower bound of $1+\frac{4\pi}{n}+2\sin(\frac{\pi}{2}-\frac{\pi}{n})$ for one faulty robot even a crash-faulty one. We also observe an almost matching upper bound obtained by means of an earlier search algorithm. We finally study the case with two Byzantine robots and we provide an algorithm that achieves evacuation in time at most $3+\frac{6\pi}{n}$ , for $n \geq 9$, or at most $3+\frac{6\pi}{n}+\delta(n)$.

Efficient Online Scheduling of Electric Vehicle Charging Using a Service-Price Menu    Go to Abstract
Angeliki Mathioudaki, National Technical University of Athens
Abstract: Along with high penetration of Electric Vehicles (EVs), charging stations are required to service a large amount of charging requests while accounting for constraints on the station's peak electricity consumption. To this end, a charging station needs to make online charging scheduling decisions often under limited future information. An important challenge relates to the prioritization of EVs that have unknown valuations for different levels of charging services. In this paper, we take into consideration the inability of EV users to express these valuations explicitly. We consider a paradigm where a menu of possible charging schedules and corresponding prices is generated online. By letting the EV users pick their most preferable menu option, the proposed algorithm commits on each EV's charging completion time upon its arrival, achieves a near optimal total weighted charging completion time, and prevents the users from strategically misreporting their preferences, while offering a practical and implementable solution to the problem of EVs - charging station interaction.

17:00 - 17:20 Break
17:20 - 19:00
Session 6

Adversarially Robust Principal Component Analysis    Go to Abstract
Vaggos Chatziafratis, Northwestern University and UC Santa Cruz
Abstract: Many machine learning systems are vulnerable to small perturbations made to inputs either at test time or at training time. This has received much recent interest on the empirical front due to applications where reliability and security are critical. However, theoretical understanding of algorithms that are robust to adversarial perturbations is limited. In this work we focus on Principal Component Analysis (PCA), a ubiquitous algorithmic primitive in machine learning. We formulate a natural robust variant of PCA where the goal is to find a low dimensional subspace to represent the given data with minimum projection error, that is in addition robust to small perturbations. Unlike PCA which is solvable in polynomial time, our formulation is computationally intractable to optimize as it captures a variant of the well-studied sparse PCA objective as a special case. In the talk, I will mainly focus on worst-case approximation algorithms that find constant factor approximations with respect to the bst subspace, in terms of the projection error and the robustness criterion. If time allows, we will also discuss several applications of our PCA formulation.

Efficient Algorithms for Learning from Coarse Labels    Go to Abstract
Alkis Kalavasis, National Technical University of Athens
Abstract: For many learning problems one may not have access to fine grained label information; e.g., an image can be labeled as husky, dog, or even animal depending on the expertise of the annotator. In this work, we formalize these settings and study the problem of learning from such coarse data. Instead of observing the actual labels from a set $\mathcal{Z}$, we observe coarse labels corresponding to a partition of $\mathcal{Z}$ (or a mixture of partitions). Our main algorithmic result is that essentially any problem learnable from fine grained labels can also be learned efficiently when the coarse data are sufficiently informative. We obtain our result through a generic reduction for answering Statistical Queries (SQ) over fine grained labels given only coarse labels. The number of coarse labels required depends polynomially on the information distortion due to coarsening and the number of fine labels $|\mathcal{Z}|$. We also investigate the case of (infinitely many) real valued labels focusing on a central problem in censored and truncated statistics: Gaussian mean estimation from coarse data. We provide an efficient algorithm when the sets in the partition are convex and establish that the problem is NP-hard even for very simple non-convex sets.

Learning Ising models from one or multiple samples    Go to Abstract
Anthimos Vardis Kandiros, MIT
Abstract: There have been two separate lines of work on estimating Ising models: (1) estimating them from multiple independent samples under minimal assumptions about the model's interaction matrix; and (2) estimating them from one sample in restrictive settings. We propose a unified framework that smoothly interpolates between these two settings, enabling significantly richer estimation guarantees from one, a few, or many samples. Our main theorem provides guarantees for one-sample estimation, quantifying the estimation error in terms of the metric entropy of a family of interaction matrices. As corollaries of our main theorem, we derive bounds when the model's interaction matrix is a (sparse) linear combination of known matrices, or it belongs to a finite set, or to a high-dimensional manifold. In fact, our main result handles multiple independent samples by viewing them as one sample from a larger model, and can be used to derive estimation bounds that are qualitatively similar to those obtained in the afore-described multiple-sample literature. Our technical approach benefits from sparsifying a model's interaction network, conditioning on subsets of variables that make the dependencies in the resulting conditional distribution sufficiently weak. We use this sparsification technique to prove strong concentration and anti-concentration results for the Ising model, which we believe have applications beyond the scope of this paper.

Learning and Covering Sums of Independent Random Variables with Unbounded Support    Go to Abstract
Kostas Stavropoulos, National Technical University of Athens
Abstract: We study the problem of covering and learning sums $S = X_1 +\cdots+X_n$ of independent random variables $X_i$ with unbounded, or even infinite, support. De et al. (2018) at FOCS 2018, showed that the maximum value of the collective support of $X_i$’s necessarily appears in the sample complexity of learning $S$. We bypass this lower bound in the general setting where each variable $X_i$ has decreasing probability mass function and is a different member of some, possibly multi-parameter, exponential family E that satisfies some structural properties. These properties allow E to contain heavy tailed distributions and distributions that are not log-concave.
Our main results in this setting are the following.
(Covering). For every ε > 0, and E that satisfies some structural assumptions, there exists a set L(E, ε) that covers S within ε in total variation distance, such that the size of L(E, ε) depends on some parameters of Ε but it is independent on the size of the support of $X_i$. In particular, the support can be infinite.
(Learning). For every ε > 0, and every k-parameter family Ε that satisfies some structural assumptions, there exists an algorithm with $\tilde{Ο}(k)·poly(1/ε)$ samples that learns a sum of n arbitrary members of E within ε in TV distance. Our results are the first to address the problem of learning sums of independent random variables with unbounded support in a very general setting.

All times are in Athens time zone: UTC/GMT +3.

Talks


Plenary Talks

Giuseppe Italiano, LUISS Guido Carli University
Details

Manolis Kellis, MIT
Details

Iordanis Kerenidis, University Paris Diderot
Details

Mihalis Yannakakis, Columbia University
Details

Contributed Talks

Panagiotis Charalampopoulos. Faster Approximate Pattern Matching: A Unified Approach

Vaggos Chatziafratis. Adversarially Robust Principal Component Analysis

Aris Filos-Ratsikas. On the Complexity of Equilibrium Computation in First-Price Auctions

Foivos Fioravantes. The Largest Connected Subgraph Game

Vasilis Gkatzelis. Resource-Aware Cost-Sharing Mechanisms with Priors

Andreas Göbel. A spectral independence view on hardspheres via block dynamics

Alkis Kalavasis. Efficient Algorithms for Learning from Coarse Labels

Fivos Kalogiannis. Min-max optimization in team zero-sum games

Vardis Kandiros. Learning Ising models from one or multiple samples

Philip Lazos. Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Angeliki Mathioudaki. Efficient Online Scheduling of Electric Vehicle Charging Using a Service-Price Menu

Themistoklis Melissourgos. Pizza Sharing is PPA-hard

Ioannis Panageas. Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Orestis Papadigenopoulos. Recurrent Submodular Welfare and Matroid Blocking Semi-Bandits

Giannis Papaioannou. Byzantine Fault Tolerant Symmetric-Persistent Circle Evacuation

Panagiotis Patsilinakos. Strategyproof Facility Location in Perturbation Stable Instances

Stratis Skoulakis. On the Approximability of Multistage Min-Sum Set Cover

Kostas Stavropoulos. Learning and Covering Sums of Independent Random Variables with Unbounded Support

Stelios Triantafyllou. On Blame Attribution for Accountable Multi-Agent Sequential Decision Making

Manolis Vasilakis. Faster Algorithms for k-Subset Sum and Variations

Abstracts

Plenary Talks

2-Connectivity in Directed Graphs

Giuseppe F. Italiano
Luiss University

Abstract:
We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only very recently.

Short bio:
After getting a Ph.D. in Computer Science at Columbia University, he worked as a Research Staff Member at the IBM T.J. Watson Research Center in Yorktown Heights (New York). When he was 33 years old, he won a National competition for Full Professor and went back to Italy. Before joining LUISS University, he was professor of computer science at University of Salerno, University "Ca' Foscari" of Venice, and University of Rome "Tor Vergata". Giuseppe F. Italiano has worked on a wide variety of problems, producing highly-cited results on a number of different areas. Most of his research is centered around the design, analysis and engineering of algorithms for big data sets, with applications to several areas, including graph theory, social network analysis, computer and network security, and computational biology. His background, which includes also a five-year experience in industrial research, puts him in a unique position to carry out work that combines basic research with strong focus on applications. In 2016 Giuseppe was nominated EATCS Fellow for "fundamental contributions to the design and analysis of algorithms for solving theoretical and applied problems in graphs and massive data sets, and for his role in establishing the field of algorithm engineering".

Single-cell dissection and manipulation of disease circuitry

Manolis Kellis
Affiliation: MIT

Abstract:
Disease-associated nucleotides lie primarily in non-coding regions, increasing the urgency of understanding how gene-regulatory circuitry impacts human disease. To address this challenge, we generate tran-scriptional and epigenomic maps of 823 human tissues, 1500 individuals, and 7.5 million single cells. We link variants to target genes, upstream regulators, cell types of action, and perturbed pathways, and predict causal genes and regions to provide unbiased views of disease mechanisms, sometimes re-shaping our understanding. We find that Alzheimer’s variants act primarily through immune processes, rather than neuronal processes, and the strongest genetic association with obesity acts via energy storage/dissipation rather than appetite/exercise decisions. We combine single-cell profiles, tissue-level variation, and genetic variation across healthy and diseased individuals to deconvolve bulk profiles into single-cell profiles, to recognize changes in cell type proportion associated with disease and aging, to partition genetic effects in-to the individual cell typeswhere they act, and to recognize cell-type-specific and disease-associated somatic mutations in exonic regions indicative of mosaicism. We expand these methods to electronic health records to recognize meta-phenotypes associated with combinations of clinical notes, prescriptions, lab tests, and billing codes, to impute missing phenotypes in sparse medical records, and to recognize the mo-lecular pathways underlying complex meta-phenotypes in genotyped individualsby integration of molecular phenotypes imputed in disease-relevant cell types. Lastly, we develop programmable and modular technologies for manipulating these pathways by high-throughput reporter assays, genome editing,and gene targeting in human cells and mice, demonstrating tissue-autonomous therapeutic avenues in Alzheimer’s, obesity, and cancer. These results provide a roadmap for translating genetic findings into mechanistic insights and ultimately new therapeutic avenues for complex disease and cancer.
Bio:
Manolis Kellis is a professor of computer science at MIT, a member of the Broad Institute of MIT and Harvard, a principal investigator of the Computer Science and Artificial Intelligence Lab at MIT, and head of the MIT Computational Biology Group (compbio.mit.edu). His research includes disease circuitry, genetics, genomics, epigenomics,coding genes, non-coding RNAs, regulatory genomics, and comparative genomics, applied to Alzheimer's Disease, Obesity, Schizophrenia, Cardiac Disorders, Cancer, and Immune Disorders, and multiple other disorders. He has led several large-scale genomics projects, including the Roadmap Epigenomics project, the ENCODE project, the Genotype Tissue-Expression (GTEx) project, and comparative genomics projects in mammals, flies, and yeasts. He received the US Presidential Early Career Award in Science and Engineering (PECASE) by US President Barack Obama, the Mendel Medal for Outstanding Achievements in Science, the NSF CAREER award, the Alfred P.Sloan Fellowship, the Technology Review TR35 recognition, the AIT Niki Award,and the Sprowls award for the best Ph.D. thesis in computer science at MIT. He has authored over 240 journal publications cited more than 115,000 times. He has obtained more than 20 multi-year grants from the NIH, and his trainees hold faculty positions at Stanford, Harvard, CMU, McGill, Johns Hopkins, UCLA, and other top universities. He lived in Greece and France before moving to the US, and he studied and conducted research at MIT, the Xerox Palo Alto Research Center, and the Cold Spring Harbor Lab. For more info, see: compbio.mit.edu and kellislab.com.

Quantum Machine Learning : prospects and challenges

Iordanis Kerenidis
Affiliation: CNRS-University of Paris and QC Ware

Abstract:
We will review recent work on Quantum Machine Learning and discuss the prospects and challenges of applying this new exciting computing paradigm to machine learning applications.
Bio:
Iordanis Kerenidis (CNRS and QC Ware) received his Ph.D. from the Computer Science Department at the University of California, Berkeley, in 2004. After a two-year postdoctoral position at the Massachusetts Institute of Technology, he joined the Centre National de Recherche Scientifique in Paris as a permanent researcher. He has been the coordinator of a number of EU-funded projects including an ERC Grant, and he is the founder and director of the Paris Centre for Quantum Computing. His research is focused on quantum algorithms for machine learning and optimization, including work on recommendation systems, classification and clustering. He is currently working as the Head of Quantum Algorithms Int. at QC Ware Corp.

Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets

Mihalis Yannakakis
Columbia University

Abstract:
In 1979, Hylland and Zeckhauser gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method has nice properties -- it is incentive compatible in the large and produces an allocation that is Pareto optimal -- and hence it provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to finally settle the computational complexity of this scheme. We present the following results.
  • - A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., when the agent's utilities come from a bi-valued set.
  • - In general, there are instances that have only irrational equilibria.
  • - Computing an exact equilibrium solution is in FIXP.
  • - Computing an approximate equilibrium is PPAD-complete, and this holds even for 4-valued utilities.
  • - Computing an equilibrium that maximizes approximately the social welfare (the weight of the matching) within a certain contant factor is NP-hard.
The talk is based on joint works with Vijay Vazirani, and Thomas Chen, Xi Chen and Binghui Peng.
Bio:
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University. Prior to joining Columbia, he was Head of the Computing Principles Research Department at Bell Labs, and Professor of Computer Science at Stanford University. Dr. Yannakakis received his PhD from Princeton University. He has served on the editorial boards of several journals, including as the editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. Dr. Yannakakis is a recipient of the Knuth Prize, a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, of Academia Europaea, and he is a Fellow of the ACM, and a Bell Labs Fellow.

Venue


ACAC will take place virtually, via the Zoom platform, due to the Covid 19 pandemic. The Zoom link will be sent in your e-mail, after registering (free). If you face any difficulties please contact the organizers.