# ACAC 15

## 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 18/8, starting on Monday, 15/6.

#### Contributions

Participants interested in giving a presentation should register, providing a tentative title and a short abstract, either in the registration form (click the "Would you like to give a talk?" checkbox), or by sending an e-mail to acac15@corelab.ntua.gr, no later than 20/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

• Preliminary Program is announced here.

• Important Dates

#### Organizing Committee

• Dimitris Fotakis
• Elias Koutsoupias
• Evangelos Markakis
• Ioannis Milis
• Aris Pagourtzis
• Stathis Zachos
• Vassilis Zissimopoulos
• Martha Sideri
• Evripidis Markou

#### Local Arrangements

• Antonis Antonopoulos
• Eleni Bakali
• Dimitris Fotakis
• Aris Pagourtzis
• Dimitris Tsipras
• Stathis Zachos

## Register

Would you like to give a talk?
Registration is closed

Hello

## Program

(*Click on the arrow icon to view talk details.)

#### Thursday, August 20th

 8:45 Registration - Coffee 9:15 Opening 9:30 - 10:30 Plenary Session    (Chair: Stathis Zachos) On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring     Lefteris Kirousis, University of Athens & Computer Technology Institute and Press “Diophantus” Abstract: The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree $\Delta$ has an acyclic proper edge coloring with at most $\lceil 3.74(\Delta-1)\rceil+1$ colors, whereas the previously known best bound was $4(\Delta-1)$. The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of the latter application is that the probability of the undesirable” events do not have a uniform upper bound, i.e., it constitutes a case of the asymmetric Lovász Local Lemma. Joint work by Ioannis Giotis, Kostas I. Psaromiligkos and Dimitrios M. Thilikos. 10:30 - 11:00 Coffee Break 11:00 - 12:30 Session 1    (Chair: Stathis Zachos) Designing Networks with Good Equilibria under Uncertainty     Giorgos Christodoulou, University of Liverpool Abstract: We consider the problem of designing network cost-sharing protocols with good equilibria under uncertainty. The underlying game is a multicast game in a rooted undirected graph with nonnegative edge costs. A set of k terminal vertices or players need to establish connectivity with the root. The social optimum is the Minimum Steiner Tree. We are interested in situations where the designer has incomplete information about the input. We propose two different models, the adversarial and the stochastic. In both models, the designer has prior knowledge of the underlying metric but the requested subset of the players is not known and is activated either in an adversarial manner (adversarial model) or is drawn from a known probability distribution (stochastic model). Stable marriages with evolving preferences     Nikos Leonardos, LIAFA, Univ Paris Diderot, France Abstract: We consider the classical Stable Marriages problem in a model introduced by Anagnostopoulos, Kumar, Mahdian, and Upfal, in 2011. The essential property of the model is that the input is not static but is dynamically changing. The changes are probabilistic and occur in discrete time-steps and the algorithm tries to detect them by querying the input in some predefined manner. The goal of the algorithm is to maintain an output which is dynamically changing and is sufficently "good" in expectation and with high probability. For the Stable Marriages problem we focus on the number of "unstable" pairs as a measure of the quality of the output. Joint work with Varun Kanade and Frederic Magniez. Enumeration of 2-level polytopes     Vissarion Fisikopoulos, Université libre de Bruxelles Abstract: We propose the first algorithm for enumerating all combinatorial types of 2-level (a.k.a. compressed) polytopes of a given dimension d, and provide complete experimental results for d≤6. Our approach is based on new findings on 2-level polytopes, also presented here. In particular, we introduce the notion of a simplicial core, which allows us to reduce the problem to the enumeration of the closed sets of a discrete closure operator, along with some convex hull computations and isomorphism tests. (to appear in ESA'15) Joint work with: Adam Bohn, Yuri Faenza, Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich 12:30 - 12:45 Coffee Break 12:45 - 13:45 Session 2    (Chair: Aris Pagourtzis) On mobile agent verifiable problems     Evangelos Bampas, LaBRI, University of Bordeaux Abstract: We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [LATIN 2012, LNCS 7256, pp. 362–374], we introduce several natural new computability classes allowing for a finer classification of problems below co-MAV or MAV, the latter being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which may be of independent interest, is a new meta-protocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory. Joint work with David Ilcinkas. Collaborative Exploration by Energy-Constrained Mobile Robots     Christina Karousatou, Aix-Marseille University and CNRS, France Abstract: We study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. Thus we need a team of agents to completely explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is bounded by the energy bound B. We provide an exploration algorithm without any knowledge about the tree and we compare our algorithm with the optimal offline algorithm that has complete knowledge of the tree. Our algorithm has a competitive ratio of O(logB), independent of the number of nodes in the tree. We also show that this is the best possible competitive ratio for exploration of unknown trees. 13:45 - 15:00 Lunch Break 15:00 - 16:00 Session 3    (Chair: Vangelis Markakis) Improving Selfish Routing for Risk-Averse Players     Thanasis Lianeas, University of Texas at Austin Abstract: We investigate how and to which extent one can exploit risk-aversion and modify the perceived cost of the players in selfish routing so that the Price of Anarchy (PoA) wrt. the total latency is improved. The starting point is to introduce some small random perturbations to the edge latencies so that the expected latency does not change, but the perceived cost of the players increases, due to risk-aversion. We adopt the simple model of γ-modifiable routing games, a variant of selfish routing games with restricted tolls. We prove that computing the best γ-enforceable flow is NP-hard for parallel-link networks with affine latencies and two classes of heterogeneous risk-averse players. On the positive side, we show that for parallel-link networks with heterogeneous players and for series-parallel networks with homogeneous players, there exists a nicely structured γ-enforceable flow whose PoA improves fast as γ increases. We show that the complexity of computing such a γ-enforceable flow is determined by the complexity of computing a Nash flow for the original game. Moreover, we prove that the PoA of this flow is best possible in the worst-case, in the sense that there are instances where (i) the best γ-enforceable flow has the same PoA, and (ii) considering more flexible modifications does not lead to any improvement on the PoA. Pushing the Envelope in Graph Compression    Katia Papakonstantinopoulou, University of Athens Abstract: We improve the state-of-the-art method for the compression of web and other similar graphs by introducing an elegant technique which further exploits the clustering properties observed in these graphs. The analysis and experimental evaluation of our method shows that it outperforms the currently best method of Boldi et al. by achieving a better compression ratio and retrieval time. Our method exhibits vast improvements on certain families of graphs, such as social networks, by taking advantage of their compressibility characteristics, and ensures that the compression ratio will not worsen for any graph, since it easily falls back to the state-of-the-art method. 16:00 - 16:15 Coffee Break 16:15 - 17:45 Session 4    (Chair: Dimitris Fotakis) Who to Trust for Truthfully Maximizing Welfare?     Emmanouil Zampetakis, Massachusetts Institute of Technology Abstract: We introduce a general approach based on selective verification and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of utilitarian voting. Having a good allocation in mind, a mechanism with verification selects few critical agents and detects, using a verification oracle, whether they have reported truthfully. If yes, the mechanism produces the desired allocation. Otherwise, the mechanism ignores any misreports and proceeds with the remaining agents. We obtain randomized truthful (or almost truthful) mechanisms without money that verify only O(lnm/ϵ) agents, where m is the number of outcomes, independently of the total number of agents, and are (1−ϵ)-approximate for the social welfare. We also show that any truthful mechanism with a constant approximation ratio needs to verify Ω(logm) agents. A remarkable property of our mechanisms is emph{robustness}, namely that their outcome depends only on the reports of the truthful agents. On the Efficiency of All-Pay Mechanisms     Alkmini Sgouritsa, University of Liverpool Abstract: We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 to 1,82 by proving some structural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi-unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, 75% efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy of social welfare, revenue and maximum bid. Manipulation of h-index, g-index, i10-index by merging articles     Chrystalla Pavlou, University of Oxford Abstract: In the academic word different measures are used to quantify the productivity and the impact of a researcher. The h-index, g-index and i10-index are examples of popular scientific impact indices that are computed in many article databases. Although these indices are widely used, there have been some observations about how someone can manipulate them. Extending the model proposed by Bevern et al. (2014), we investigate whether it is easy for a researcher to improve his g-index and i10-index by means of the merge operation. We also study the manipulation of h-index, g-index and the i10-index under a model that takes the social network of the researcher into account. Specifically, we study the case where a researcher wants to improve his target index without affecting a second researcher's index and two adversarial scenarios. In the first case a researcher wants to improve his target index in a way that does not improve his opponent's index and in the second case a researcher wants to harm his opponent's index in a way that does not harm his own index. 17:45 - 18:00 Short Break 18:00 - 19:00 Session 5    (Chair: Vassilis Zissimopoulos) Cost-sharing models in Participatory Sensing     Giorgos Birmpas, Athens University of Economics and Business Abstract: In Smart City and Participatory Sensing initiatives the key concept is for user communities to contribute sensor information and form a body of knowledge that can be exploited by innovative applications and data analytics services. A key aspect in all such platforms is that sensor information is not free but comes at a cost. As a result, these platforms may suffer due to insufficient sensor information made publicly available if applications do not share efficiently the cost of the sensor information they consume. We explore the design of specialized market mechanisms that match demand to supply while taking into account important positive demand externalities: sensors are digital goods and their cost can be shared by applications. We focus on the buyer side and define different demand models according to the flexibility in choosing sensor data for satisfying application needs. We then investigate the properties of various cost-sharing mechanisms with respect to efficiency and budget balance. In doing so, we also propose and study a new mechanism, which although lacks strategyproofness, it exhibits important efficiency improvement along with certain fairness properties. Aggregating partial rankings with applications to peer grading in MOOCs     Alexandros Voudouris, University of Patras Abstract: We investigate the potential of using ordinal peer grading for the evaluation of students in massive online open courses (MOOCs). According to such grading schemes, each student receives a few assignments (by other students) which she has to rank. Then, a global ranking is produced by combining the individual ones. This is a novel application area for social choice concepts and methods where the important problem to be solved is as follows: how should the assignments be distributed so that the collected individual rankings can be easily merged into a global one that is as close as possible to the ranking that represents the relative performance of the students in the assignment? Our main theoretical result suggests that using very simple ways to distribute the assignments so that each student has to rank only k of them, a Borda-like aggregation method can recover a 1-O(1/k) fraction of the true ranking when each student correctly ranks the assignments she receives. Experimental results indicate that this method works even better in practice and is extremely robust even when students have imperfect capabilities as graders. Our results provide strong evidence that ordinal peer grading can be a highly effective and scalable solution for evaluation in MOOCs.

## Participants

First Name Last Name Affiliation
GeorgiosAmanatidisAthens University of Economics and Business
AntoniosAngelakisECE NTUA
KonstantinosAngelopoulosUniversity of Trento
AntonisAntonisNTUA
AntonisAntonopoulosNTUA
SpirosArgiroiliopoulosMathematician
MakisArsenisNTUA
ChristosAslanoglouDI, UoA
ZetaAvarikiotiNTUA
EleniBakaliNTUA
EvangelosBampasLaBRI, University of Bordeaux
EleniBatziouNational Technical University of Athens
LeonidasBeisAUEB
IoannisBelimezakisAUEB
VictorBenetatosUOA
GiorgosBirmpasAUEB
IoannisCaragiannisUniversity of Patras
NikolaosChasanisObserver
EvangelosChatziafratisHMMY
XenophonChatzigeorgiouECE, UoPatra
GiorgosChristodoulouUniversity of Liverpool
IoannisDiamantisNational Technical University of Athens
ArisFilos-RatsikasUniversity of Oxford
VissarionFisikopoulosUniversité libre de Bruxelles
GeorgeFotopoulosIEK KSINI / Open University of Patra
PanagiotisFotopoulosUniversity of Athens
EnriGaci
MyrtoGalenianouUniversity of Athens
ChristinaGiannoulaStudent at School of Electrical and Computer Engineering - N.T.U.A.
AggelosGiantsiosNTUA
VasilisGkatzelisStanford University
GeorgiaGkiokaECE student
SofiaGkogkoustudent
VasilisGoumasECE, NTUA
Panagiotis GrontasNtua
FotiosGryllakisUoPatra
PolyxeniIoannidouStudent
Anthimos-VardisKandirosNational Technical University of Athens
ChrysostomosKaniourasECCE, NTUA
PavlosKapoutsisECCE, NTUA
AthanasiosKapoutsisDUTH
Aggelos-DionysiosKapposNational and Kapodistrian University of Athens
NikosKapsoulisHMMY
GrigorisKaragiorgosTEI of Peloponnese
AnnaKarasoulouUniversity of Athens
MikeliKarotsieri
ChristinaKarousatouAix-Marseille University and CNRS, France
VasilikiKontouraNational Technical University of Athens
NataliaKotsaniNTUA
EugeniaKotzapanagiotouUniversity of Patras
KonstantinosKoukasDI, UoA
IoannisKoulierakisECE
AthanasiosKoumpoulisECE
GeorgeKrimpasUniversity of Patras
NickKrimpasUniversity of Patras
KonstantinosLentzosUniversität Konstanz
NikosLeonardosLIAFA, Univ Paris Diderot, France
ThanasisLianeasUniversity of Texas at Austin
VasilisLivanosNTUA
VasilisMargonisUniversity of Patras
VangelisMarkakisAthens University of Economics and Business
EuripidesMarkouUniversity of Thessaly
NikolaosMelissinosNTUA
Orestis MelkonianNational and Kapodistrian University of Athens
StavrosMessarisUniversity of Athens (Undergrad Mathematics Student)
AlexandrosMetaxasECE, NTUA
Faidra GeorgiaMonachouNTUA
VassilikiNikolaouECE, NTUA
KaterinaNikolidakiNTUA
DimitriosPanagopoulosEurekaModule
HarisPantazisStudent
IoannisPapaioannouMPLA
KatiaPapakonstantinopoulouUniversity of Athens
DespoinaPapatheodorouNTUA
IoannisPapatsorisUniversity of Athens
ChrystallaPavlouUniversity of Oxford
MatoulaPetroliaUniversity of Nantes
AnastasiosPikridasntua
ManolisPitsikalisdi uoa
CharaPodimataNTUA
DimitriosPolitisAristotle university of Thessaloniki
GeorgePolykratisPhysics Department, University of Athens
IoannisPsarrosUniversity of Athens
AgapiRissakiECE NTUA
GeorgiosRoutisNTUA
MarioSaldingerNational and Kapodistrian University of Athens
EleniSapountziUniversity of Thessaly
DimitrisSeintaridisStudent
KyriakosSergisNTUA
AlkminiSgouritsaUniversity of Liverpool
JohnSigalasUoA
LamprosSmyrnaiosComputer Science
EvaggelosSouldatosNTUA
DimitrisSpyropoulosStudent
KonstantinosStratisShmmy
OrestisTelelisUniversity of Piraeus
Orfeas StefanosThyfronitis LitosECE NTUA
EfthymiosTsakalerisBank of Greece
EliasTsigaridasINRIA Paris
DimitrisTsiprasNTUA
Mustafa KemalTuralIndustrial Engineering Department, Middle East Technical University
IoannaTziallaECE NTUA
GrigoriosVelegkasECE, NTUA
IoannisVetsikasNCSR Demokritos, Greece
AngelinaVidaliPierre and Marie Curie University
EleftheriaVolianakiUniversity of Patras
Alexandros VoudourisUniversity of Patras
ChristosVrachasUniversity of Athens
StathisZachosNTUA
LydiaZakynthinouNTUA
EmmanouilZampetakisMIT
GiorgosZirdelisNTUA
VassilisZissimopoulosUniversity of Athens
GeorgiosZoisAthens University of Economics and Business
ilias kotsireasWilfrid Laurier University, Waterloo, Ontario, Canada
stavrospetsalakisDIT, UoA
ΒασιλικήΒελώνα-
ΑστρινόςΔαμιανάκηςΦοιτητής
ΔημήτρηςΔημητρίουΤμήμα Πληροφορικής ΕΚΠΑ
ΑπόστολοςΚυτέαςΦοιτητής ΣΗΜΜΥ
ΠαναγιώτηςΠουραΐμηςΣπουδαστής ΣΗΜΜΥ ΕΜΠ

## Venue

ACAC15 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.