# ACAC '18

## 13th Athens Colloquium on Algorithms and Complexity

#### 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 15/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 acac18@corelab.ntua.gr, no later than 31/7. 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

#### News

• Important Dates

#### Organizing Committee

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

#### Local Arrangements

• Antonis Antonopoulos
• Angeliki Chalki
• Aris Pagourtzis
• Giannis Papaioannou
• Petros Potikas
• Stathis Zachos

## Register

Would you like to give a talk?

Hello

## Program

#### Thursday, August 23rd

 9:00 Registration - Opening 9:30 - 10:30 Plenary Session Taking into account a society’s opinions on a multiplicity of issues in a way that avoids proclaiming dictators.     Lefteris Kirousis, National and Kapodistrian University of Athens Abstract: Assume that the members of a society of individuals are given the chance to express an opinion on a multiplicity of issues. The opinion of an individual on an issue can take one of several values, however only certain combinations of an individual’s opinions on the issues are considered to be rational. Given the set of rational combinations, can we efficiently decide whether any collection of such combinations by the individuals can be aggregated into a single rational combination in a way that avoids proclaiming one particular individual as a dictator and always following their opinion? Joint work with Phokion Kolaitis and John Livieratos 10:30 - 11:00 Coffee Break 11:00 - 12:00 Session 1 Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators     Thanasis Lianeas, National Technical University of Athens Abstract: Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: owners (operators) of the network and users of the network. Owners of the network post a price for usage of the link they own so as to attract users and maximize profit; users of the network select routes based on price and level of use by other users. We point out that an equilibrium in these games may not exist, may not be unique and may induce an arbitrarily inefficient network performance. Our main result is to observe that a simple regulation on the network owners market solves all three issues above. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then: the game among the link operators has a unique and strong Nash equilibrium and the users' game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. As a secondary objective, we want to compute great tolls that minimize total users' payments and we provide a linear program that does this. We obtain multiplicative approximation results compared to the optimal total users' payments for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a bound that only depends on the topology of the network. Lastly, we show how the same mechanism of setting appropriate caps on the allowable prices extends to the model of elastic demands. Algorithms for Stable and Perturbation-Resilient Problems     Haris Angelidakis, Toyota Technological Institute at Chicago Abstract: We study a beyond worst-case analysis framework known as stability and perturbation resilience, introduced by Bilu and Linial (2010) and Awasthi, Blum, and Sheffet (2012). A combinatorial optimization problem is $\gamma$-stable or $\gamma$-perturbation-resilient if the optimal solution does not change when we perturb all parameters of the problem by a factor of at most $\gamma$. In this talk, we start with a brief survey of known results in the area, and then present exact polynomial-time algorithms for stable instances of Edge/Node Multiway Cut and Independent Set. We then proceed to explore the power of convex relaxations for solving stable instances of combinatorial optimization problems. We conclude with several hardness results for stable instances of covering problems. Based on joint works with Konstantin Makarychev and Yury Makarychev, and Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis and Chen Dan. 12:00 - 12:15 Coffee Break 12:15 - 13:15 Session 2 Maximum Rooted Connected Expansion     Ioannis Lamprou, University of Liverpool Abstract: Prefetching constitutes a valuable tool toward efficient Web surfing. As a result, estimating the amount of resources that need to be preloaded during a surfer's browsing becomes an important task. In this regard, prefetching can be modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer Science 2014], where a surfer and a marker alternately play on a given graph (representing the Web graph). During its turn, the marker chooses a set of $k$ nodes to mark (prefetch), whereas the surfer, represented as a token resting on graph nodes, moves to a neighboring node (Web resource). The surfer's objective is to reach an unmarked node before all nodes become marked and the marker wins. Intuitively, since the surfer is step-by-step traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache all resources lying in the neighborhood of this growing subset. Motivated by the above, we consider the following problem to which we refer to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$ and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$ is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where $N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all nodes in $S$ and all nodes with at least one neighbor in $S$. We prove that the problem is NP-hard even when the input graph $G$ is restricted to be a split graph. On the positive side, we demonstrate a polynomial time approximation scheme for split graphs. Furthermore, we present a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomial-time algorithm for the special case of interval graphs. Joint work with R. Martin, S. Schewe, I. Sigalas, V. Zissimopoulos Improved Approximation for Tree Augmentation: Saving by Rewiring     Christos Kalaitzis, ETH Zürich Abstract:The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose addition to the tree leads to a 2-edge-connected graph. A long line of results on TAP culminated in the previously best known approximation guarantee of 1.5. We show that an approximation factor below 1.5 can be achieved, by presenting a 1.458-approximation that is based on several new techniques. 13:15 - 14:45 Lunch Break 14:45 - 15:45 Session 3 Truthful mechanisms for ownership transfer with expert advice     Ioannis Caragiannis, University of Patras Abstract:When a company undergoes a merger or transfer of its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, e.g., the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the internal experts' opinions. Motivated by such questions, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in these settings. We consider the problem with one expert and two bidders and provide tight approximation guarantees of the optimal social welfare. Since this problem is a combination of mechanism design with and without monetary transfers (payments can be imposed to the bidders but not to the expert), classical solutions like VCG cannot be applied, making this a novel mechanism design problem. We distinguish between mechanisms that use ordinal and cardinal information, as well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several non-trivial randomized truthful mechanisms, and also allows for closer-to-optimal-welfare guarantees. 15:45 - 16:00 Coffee Break 16:00 - 17:00 Session 4 A combinatorial approach to the recovery of Gaussian Graphical Models     Vasiliki Velona, Universitat Pompeu Fabra, Universitat Politècnica de Catalunya Abstract: Suppose that $X=(X_1,...,X_n)$ follows a multivariate normal distribution with precision matrix Q and G(V,E) is the underlying graph of Q, i.e., an edge ij belongs in E if and only if $q_{ij}$ is not zero. We give randomised algorithms that recover efficiently the graph G, under some graph theoretic assumptions. Moreover, we give lower bounds on the number of pairwise correlations needed to recover G. We pursue to extend our results to more general classes of graphs. This is joint (and ongoing) work with Gábor Lugosi, Jakub Truszkowski, and Piotr Zwiernik. Local Differential Privacy     Angelina Vidali, National and Kapodistrian University of Athens Abstract:Local Differential Privacy has recently attracted much attention as a privacy metric in the local model, in which each user adds noise to his own personal data by himself and the data aggregator estimates the statistics of the personal data such as a distribution underlying the data. Local Differential Privacy provides a privacy guarantee against adversaries with arbitrary background knowledge, and does not suffer from a possibility of data leakage. It is very useful in practice because users don't need to trust the data aggregator to be willing to give their data.

#### Friday, August 24th

 9:30 - 10:30 Session 5 Learning Combinations of Linear Classifiers     Stratis Ioannidis, Northeastern University Abstract: We consider a discriminative learning problem in which the regression function is a convex combination of k linear classifiers of dimension d. This is motivated both by a classifier mixture setting as well as by the identifiability of a 2-layer neural network. We study two problems related by this setting: (a) learning the subspace spanned by the k classifiers, which can be used for dimensionality reduction, and (b) learning the classifier parameters themselves, i.e., solving the full regression problem. For the first problem, we develop a simple algorithm based on the principal Hessian directions method and a "mirroring" trick; under a probabilistic assumption on the feature vector distribution, we prove that this approach has nearly optimal $(O(d))$ statistical efficiency. For the second problem, we provide an algorithm that retrieves the classifier parameter vectors by clustering estimates of the regression function's gradient. Combining the two algorithms yields an algorithm learning classifier parameters with $O(d)+e^{\Theta(poly(k))}$ sample complexity. This is joint work with Yuekai Sun and Andrea Montanari. 10:30 - 11:00 Coffee Break 11:00 - 12:00 Session 6 Generalized malleable scheduling on uniform and unrelated machines.     Orestis Papadigenopoulos, The University of Texas at Austin Abstract: We consider the problem of scheduling a set of malleable jobs on uniform/unrelated machines, minimizing the makespan of the produced schedule. Unlike the classical parallel scheduling where every job is assigned to a specific machine, in the malleable setting, every job is assigned to a subset of machines where it is executed non-preemptively and in unison, i.e., the starting and ending time of a job is the same on every machine it is executed on. We propose LP-based O(1)-approximation algorithms for: (a) the case of uniform machines, where every machine is associated with some speed, and (b) the case of unrelated machines, where the speed of each machine is job-dependent. Joint work with Evdokia Nikolova, Dimitris Fotakis and Jannik Matuschke. Drawing a Rooted Tree as a Rooted y−Monotone Minimum Spanning Tree     Konstantinos Mastakas, National Technical University of Athens Abstract:Given a rooted point set P , the rooted y−Monotone Minimum Spanning Tree (rooted y−MMST) of P is the spanning geometric graph of P in which all the vertices are connected to the root by some y−monotone path and the sum of the Euclidean lengths of its edges is the minimum. We show that the maximum degree of a rooted y−MMST is not bounded by a constant number. We give a linear time algorithm that draws any rooted tree as a rooted y−MMST and also show that there exist rooted trees that can be drawn as rooted y−MMSTs only in a grid of exponential area. 12:00 - 12:15 Coffee Break 12:15 - 13:15 Session 7 An Improved Envy-Free Cake Cutting Protocol for Four Agents     Georgios Amanatidis, Centrum Wiskunde & Informatica (CWI) Abstract:We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent's piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie (STOC 2016, FOCS 2016). The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of Aziz and Mackenzie (STOC 2016) by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity. The Stochastic Score Classification Problem     Dimitrios Gkenosis, National and Kapodistrian University of Athens Abstract:Consider the following Stochastic Score Classification Problem. A doctor is assessing a patient's risk of developing a certain disease, and can perform $n$ tests on the patient. Each test has a binary outcome, positive or negative. A positive test result is an indication of risk, and a patient's score is the total number of positive test results. The doctor needs to classify the patient into one of $B$ risk classes, depending on the score (e.g., LOW, MEDIUM, and HIGH risk). Each of these classes corresponds to a contiguous range of scores. Test $i$ has probability $p_i$ of being positive, and it costs $c_i$ to perform the test. To reduce costs, instead of performing all tests, the doctor will perform them sequentially and stop testing when it is possible to determine the risk category for the patient. The problem is to determine the order in which the doctor should perform the tests, so as to minimize the expected testing cost. We provide approximation algorithms for adaptive and non-adaptive versions of this problem, and pose a number of open questions. 13:15 - 14:45 Lunch Break 14:45 - 15:45 Session 8 Hard Combinatorial Problems via SAT     Ilias Kotsireas, Wilfrid Laurier University, Waterloo Abstract:The area of boolean satisfiability and SAT solvers has seen dramatic advances in the past two decades. A recent trend in SAT solving is an attempt to combine the stengths of symbolic computation tools with the power of SAT solvers, in order to improve their effectiveness and to build custom-tailored SAT solvers for hard combinatorial problems. We will describe our work in this context, with a focus on some particularly hard combinatorial problems, described via autocorrelation of finite sequences. Based on joint work with Vijay Ganesh (University of Waterloo) and Curtis Bright (University of Waterloo) in the context of the Horizon 2020 EU project "Satisfiability Checking and Symbolic Computation" (SC^2). 15:45 - 16:00 Coffee Break 16:00 - 16:45 Short Presentations Session 16:45 - 17:00 Coffee Break 17:00 - 17:45 Session 9 A Converse to Banach’s Fixed Point Theorem and its CLS Completeness     Manolis Zampetakis, MIT Abstract:Banach’s fixed point theorem has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach’s theorem limited. Our first result is a strong converse of Banach’s theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to. We next consider the computational complexity of Banach’s fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach’s fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11]. 20:00 Dinner: "Vyrinis" Restaurant (Archimidous 11, Pangrati)* *[please book your seat at the registration desk]

## Venue

ACAC18 will take place in the Multimedia Amphitheater of the National Technical University of Athens, located in the basement of the building of NTUA's Central Library. See the map below:

You can arrive at the Central Library by various ways:

#### By public transport:

The easiest way is by taking the Blue Metro line and getting off at the "ΚΑΤΕΧΑΚΗ" station. Then take the bus 242, get off at stop "ΘΥΡΩΡΕΙΟ" and walk 5 minutes towards the Central Library.
Another option is to take the bus 140 from the "ΚΑΤΕΧΑΚΗ" metro station and get off at stop "ΠΟΛΥΤΕΧΝΕΙΟΥΠΟΛΗ". Then get into the campus and walk 10 minutes towards the Central Library.

#### By car:

You can use this google map to get directions from Alimou-Katechaki Avenue.