## National Technical University of Athens

### Athens, Greece

### August **21-22**, 2014

### Scope

### Registration

**15/8**, starting on Monday, 14/7.

### Contributions

**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

### Contact

### Register

Hello

### Program

#### Thursday, August 21^{th}

#### Friday, August 22^{th}

9:30-10:30 | Sparsification and subexponential approximation |

Vangelis Paschos, University Paris-Dauphine | |

10:30-11:00 | Coffee Break |

11:00-12:30 | Session 5 (Chair: V. Zissimopoulos) |

Item Bidding from Combinatorial Public Projects | |

Orestis Telelis, Athens University of Economics and Business | |

Nash equilibria in bimatrix 5x4 games | |

Raimundas Vidunas, University of Athens | |

Reliable Broadcast with Respect to Topology Knowledge | |

Giorgos Panagiotakos, National Technical University of Athens | |

12:30-12:45 | Short Break |

12:45-13:45 | Session 6 (Chair: I. Milis) |

Game Semantics for Logic Programming | |

Chrysida Galanaki, University of Athens | |

Multiprocessor Speed Scaling with Precedence Constraints | |

Dimitris Letsios, Technical University of Munich | |

13:45-15:00 | Lunch Break |

15:00-16:00 | Reductions from Mechanism to Algorithm Design |

Costantinos Daskalakis, MIT | |

16:00-16:15 | Short Break |

16:15-17:45 | Session 7 (Chair: A. Pagourtzis) |

Exclusive Graph Searching in Various Graph Classes | |

Euripides Markou, University of Thessaly | |

Short Sessions | |

20:15 | Dinner: "O Tsopanakos", Anakreontos 2, Kaisariani (Google Maps) |

x

Paul Spirakis, University of Liverpool & CTI

Joint work with O. Michail, I. Chatzigiannakis and G. Mertzios, results appeared in ICALP 2013 and results that will appear in MFCS 2014.

We discuss here the notion of temporal graphs. These are abstract models of networks that change with time. Here, edges have labels (positive integers indicating discrete times of availability). A basic notion is that of a journey (that is a path in which subsequent edges appear with increasing labels). We examine foremost journeys, Menger's theorem, design issues of temporal nets and also some questions on traversals and the Temporal Travelling salesman Problem.

**Temporal graphs and temporal networks**Paul Spirakis, University of Liverpool & CTI

Joint work with O. Michail, I. Chatzigiannakis and G. Mertzios, results appeared in ICALP 2013 and results that will appear in MFCS 2014.

We discuss here the notion of temporal graphs. These are abstract models of networks that change with time. Here, edges have labels (positive integers indicating discrete times of availability). A basic notion is that of a journey (that is a path in which subsequent edges appear with increasing labels). We examine foremost journeys, Menger's theorem, design issues of temporal nets and also some questions on traversals and the Temporal Travelling salesman Problem.

x

Panagiotis Cheilaris, Università della Svizzera italiana

Joint work with Sandeep Kumar Dey, Maria Gabrani, Evanthia Papadopoulou

We present a CGAL (Computational Geometry Algorithm Library) implementation of the line segment Voronoi diagram under the L∞ metric, building on top of the existing line segment Voronoi diagram under the Euclidean (L2) metric in CGAL. CGAL is an open- source collection of geometric algorithms implemented in C++, used in both academia and industry. We also discuss an application of the L∞ segment Voronoi diagram in the area of VLSI pattern analysis. In particular, we identify potentially critical locations in VLSI design patterns, where a pattern (when printed) may differ substantially from the original intended VLSI design.

**Implementing the L∞ segment Voronoi diagram in CGAL and an application in VLSI pattern analysis**Panagiotis Cheilaris, Università della Svizzera italiana

Joint work with Sandeep Kumar Dey, Maria Gabrani, Evanthia Papadopoulou

We present a CGAL (Computational Geometry Algorithm Library) implementation of the line segment Voronoi diagram under the L∞ metric, building on top of the existing line segment Voronoi diagram under the Euclidean (L2) metric in CGAL. CGAL is an open- source collection of geometric algorithms implemented in C++, used in both academia and industry. We also discuss an application of the L∞ segment Voronoi diagram in the area of VLSI pattern analysis. In particular, we identify potentially critical locations in VLSI design patterns, where a pattern (when printed) may differ substantially from the original intended VLSI design.

x

Elias Tsigaridas, Inria Paris-Rocquencourt

Joint work with Victor Y. Pan (CUNY, USA)

What is the bit complexity for approximating up to L bits the complex root of a univariate polynomial with integer coefficients? We present an optimal, up to poly-logarithmic factors, algorithm for this problem.

**Nearly optimal algorithm for complex root refinement**Elias Tsigaridas, Inria Paris-Rocquencourt

Joint work with Victor Y. Pan (CUNY, USA)

What is the bit complexity for approximating up to L bits the complex root of a univariate polynomial with integer coefficients? We present an optimal, up to poly-logarithmic factors, algorithm for this problem.

x

Zafeirakis Zafeirakopoulos, RISC-Linz

Joint work with Felix Breuer

Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omega is significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date.

**Polyhedral Omega: A linear Diophantine system solver**Zafeirakis Zafeirakopoulos, RISC-Linz

Joint work with Felix Breuer

Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omega is significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date.

x

Alkmini Sgouritsa, University of Liverpool

We study the Price of Anarchy (PoA) of simple mechanisms where divisible goods are to be allocated among selfish individuals. In such mechanisms, each bidder submits a single bid for each divisible good to represent her preference and the mechanism determines the fractional allocation and payments for bidders based on their bids. We are interested in simultaneous (i.e. running in parallel) allocation mechanisms when the valuations of the bidders are subadditive and we mainly focus on the well-known proportional-share allocation mechanism.

**On the Efficiency of Simple Allocation Mechanisms for Divisible Goods**Alkmini Sgouritsa, University of Liverpool

We study the Price of Anarchy (PoA) of simple mechanisms where divisible goods are to be allocated among selfish individuals. In such mechanisms, each bidder submits a single bid for each divisible good to represent her preference and the mechanism determines the fractional allocation and payments for bidders based on their bids. We are interested in simultaneous (i.e. running in parallel) allocation mechanisms when the valuations of the bidders are subadditive and we mainly focus on the well-known proportional-share allocation mechanism.

x

Yiannis Giannakopoulos, University of Oxford

We derive exact optimal solutions for the problem of optimizing revenue in single-bidder multi-item auctions for uniform i.i.d. valuations. We give optimal auctions of up to 6 items; previous results were only known for up to three items. To do so, we develop a general duality framework for the general problem of maximizing revenue in many-bidders multi-item additive Bayesian auctions with continuous probability valuation distributions. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal auction; as a result, the optimal auction is defined by natural geometric constraints.

**Duality and Optimality of Auctions for Uniform Distributions**Yiannis Giannakopoulos, University of Oxford

We derive exact optimal solutions for the problem of optimizing revenue in single-bidder multi-item auctions for uniform i.i.d. valuations. We give optimal auctions of up to 6 items; previous results were only known for up to three items. To do so, we develop a general duality framework for the general problem of maximizing revenue in many-bidders multi-item additive Bayesian auctions with continuous probability valuation distributions. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal auction; as a result, the optimal auction is defined by natural geometric constraints.

x

Vasilis Gkatzelis, Stanford University

Joint work with Paul Duetting and Tim Roughgarden

Deferred-acceptance auctions are auctions for binary single-parameter mechanism design problems whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal [2014] recently introduced these auctions and proved that they satisfy a remarkable list of incentive guarantees: in addition to being dominant-strategy incentive-compatible, they are weakly group-strategyproof, can be implemented by ascending-clock auctions, and admit outcome-equivalent full-information pay-as-bid versions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional incentive properties. The goal of this paper is to initiate the study of deferred-acceptance auctions from an approximation standpoint. We study these auctions through the lens of two canonical welfare-maximization problems, in knapsack auctions and in combinatorial auctions with single-minded bidders.

**The Performance of Deferred-Acceptance Auctions**Vasilis Gkatzelis, Stanford University

Joint work with Paul Duetting and Tim Roughgarden

Deferred-acceptance auctions are auctions for binary single-parameter mechanism design problems whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal [2014] recently introduced these auctions and proved that they satisfy a remarkable list of incentive guarantees: in addition to being dominant-strategy incentive-compatible, they are weakly group-strategyproof, can be implemented by ascending-clock auctions, and admit outcome-equivalent full-information pay-as-bid versions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional incentive properties. The goal of this paper is to initiate the study of deferred-acceptance auctions from an approximation standpoint. We study these auctions through the lens of two canonical welfare-maximization problems, in knapsack auctions and in combinatorial auctions with single-minded bidders.

x

Alexandros Voudouris, University of Patras

According to the proportional allocation mechanism, users compete for a divisible resource by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of $26.8\%$ on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to $50\%$ over both equilibrium concepts. Our analysis is simpler and it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between $36\%$ and $50\%$) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.

**Welfare guarantees for proportional allocations**Alexandros Voudouris, University of Patras

According to the proportional allocation mechanism, users compete for a divisible resource by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of $26.8\%$ on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to $50\%$ over both equilibrium concepts. Our analysis is simpler and it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between $36\%$ and $50\%$) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.

x

Angelina Vidali, Duke University, Durham, North Carolina, USA

Joint work with Annamária Kovács, Goethe University, Frankfurt/M, Germany

Our work is a step towards the important problem of globaly characterizing truthful mechanisms with multi-parameter, additive player-valuations like unrelated scheduling or additive combinatorial auctions. Very few mechanisms are known for these multi-parameter nondownward closed settings and the question is: Can we prove that no other mechanisms exist? We characterize decisive, strongly monotone mechanisms for two tasks or items as either task independent mechanisms or ’player-grouping minimizers’, a new monotone generalization of affine minimizers. We present a general lemma implying the local linearity of payment functions in ’most’ cases.

**A characterization result for strongly monotone scheduling mechanisms**Angelina Vidali, Duke University, Durham, North Carolina, USA

Joint work with Annamária Kovács, Goethe University, Frankfurt/M, Germany

Our work is a step towards the important problem of globaly characterizing truthful mechanisms with multi-parameter, additive player-valuations like unrelated scheduling or additive combinatorial auctions. Very few mechanisms are known for these multi-parameter nondownward closed settings and the question is: Can we prove that no other mechanisms exist? We characterize decisive, strongly monotone mechanisms for two tasks or items as either task independent mechanisms or ’player-grouping minimizers’, a new monotone generalization of affine minimizers. We present a general lemma implying the local linearity of payment functions in ’most’ cases.

x

Thodoris Lykouris, Cornell University

Joint work with Dimitris Fotakis, Evangelos Markakis, Svetlana Obraztsova

We study influence maximization problems over social networks, in the presence of competition. Our focus is on diffusion processes within the family of threshold models. Motivated by the general lack of positive results establishing monotonicity and submodularity of the influence function for threshold models, we introduce a general class of switching-selection threshold models where the switching and selection functions may also depend on the node activation history. This extension allows us to establish monotonicity and submodularity when (i) the switching function is linear and depends on the influence by all active neigh- bors, and (ii) the selection function is linear and depends on the influence by the nodes activated only in the last step. This implies a (1 − 1/e − ε)-approximation for the influence maximization problem in the competitive setting. On the nega- tive side, we present a collection of counterexamples establishing that the restric- tions above are essentially necessary. Moreover, we show that switching-selection threshold games with properties (i) and (ii) are valid utility games, and thus their Price of Anarchy is at most 2.

**Influence Maximization in Switching-Selection Threshold Models**Thodoris Lykouris, Cornell University

Joint work with Dimitris Fotakis, Evangelos Markakis, Svetlana Obraztsova

We study influence maximization problems over social networks, in the presence of competition. Our focus is on diffusion processes within the family of threshold models. Motivated by the general lack of positive results establishing monotonicity and submodularity of the influence function for threshold models, we introduce a general class of switching-selection threshold models where the switching and selection functions may also depend on the node activation history. This extension allows us to establish monotonicity and submodularity when (i) the switching function is linear and depends on the influence by all active neigh- bors, and (ii) the selection function is linear and depends on the influence by the nodes activated only in the last step. This implies a (1 − 1/e − ε)-approximation for the influence maximization problem in the competitive setting. On the nega- tive side, we present a collection of counterexamples establishing that the restric- tions above are essentially necessary. Moreover, we show that switching-selection threshold games with properties (i) and (ii) are valid utility games, and thus their Price of Anarchy is at most 2.

x

Thanasis Lianeas, National Technical University of Athens

Congestion games ignore the stochastic nature of resource delays and the risk-averse attitude of the players to uncertainty. In the first part of the talk, we introduce two variants of atomic congestion games, one with stochastic players, where each player assigns load to her strategy independently with a given probability, and another with stochastic edges, where the latency functions are random. In both variants, the players are risk-averse, and their individual cost is a player-specific quantile of their delay distribution. We investigate the existence of equilibria and potential functions and the Price of Anarchy. In the second part of the talk, we investigate how and to which extent one can exploit risk-aversion and modify the perceived latencies of the players so that the Price of Anarchy wrt the total latency of the players is improved. The starting point is to introduce some small (and carefully selected) 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.

**Congestion Games with Risk-Averse Players**Thanasis Lianeas, National Technical University of Athens

Congestion games ignore the stochastic nature of resource delays and the risk-averse attitude of the players to uncertainty. In the first part of the talk, we introduce two variants of atomic congestion games, one with stochastic players, where each player assigns load to her strategy independently with a given probability, and another with stochastic edges, where the latency functions are random. In both variants, the players are risk-averse, and their individual cost is a player-specific quantile of their delay distribution. We investigate the existence of equilibria and potential functions and the Price of Anarchy. In the second part of the talk, we investigate how and to which extent one can exploit risk-aversion and modify the perceived latencies of the players so that the Price of Anarchy wrt the total latency of the players is improved. The starting point is to introduce some small (and carefully selected) 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.

x

Manolis Zambetakis, National Technical University of Athens

We investigate the reasons that make symmetric partial verification essentially useless in virtually all domains. Departing from previous work, we consider any possible (finite or infinite) domain and general symmetric verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints, and prove that this property is sufficient for the equivalence of truthfulness and M-truthfulness. In fact, defining appropriate versions of this property, we obtain this result for deterministic and randomized mechanisms with and without money. Moreover,we show that a slightly relaxed version of this property is also necessary for the equivalence of truthfulness and M-truthfulness. Our conditions provide a generic and convenient way of checking whether truthful implementation can take advantage of any symmetric verification scheme in any domain. Since the simplest case of symmetric verification is local verification, our results imply, as a special case, the equivalence of local truthfulness and global truthfulness in the setting without money. To complete the picture, we consider asymmetric verification, and prove that a social choice function is M-truthfully implementable by some asymmetric verification M if and only if f does not admit a cycle of profitable deviations.

**Mechanism Design with Verification**Manolis Zambetakis, National Technical University of Athens

We investigate the reasons that make symmetric partial verification essentially useless in virtually all domains. Departing from previous work, we consider any possible (finite or infinite) domain and general symmetric verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints, and prove that this property is sufficient for the equivalence of truthfulness and M-truthfulness. In fact, defining appropriate versions of this property, we obtain this result for deterministic and randomized mechanisms with and without money. Moreover,we show that a slightly relaxed version of this property is also necessary for the equivalence of truthfulness and M-truthfulness. Our conditions provide a generic and convenient way of checking whether truthful implementation can take advantage of any symmetric verification scheme in any domain. Since the simplest case of symmetric verification is local verification, our results imply, as a special case, the equivalence of local truthfulness and global truthfulness in the setting without money. To complete the picture, we consider asymmetric verification, and prove that a social choice function is M-truthfully implementable by some asymmetric verification M if and only if f does not admit a cycle of profitable deviations.

x

Vangelis Paschos, University Paris-Dauphine

Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this talk, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems as dominating set, feedback vertex set, min set cover.

**Sparsification and subexponential approximation**Vangelis Paschos, University Paris-Dauphine

Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this talk, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems as dominating set, feedback vertex set, min set cover.

x

Orestis Telelis, Athens University of Economics and Business

This is a joint work, with Vangelis Markakis.

We analyze equilibria of mechanisms for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study two non-truthful mechanisms that are, however, practically relevant to multi-agent environments, by virtue of their simplicity. Both mechanisms employ an item bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to VCG-based payment rules. For expressive classes of the agents’ valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently, we derive worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium.

**Item Bidding from Combinatorial Public Projects**Orestis Telelis, Athens University of Economics and Business

This is a joint work, with Vangelis Markakis.

We analyze equilibria of mechanisms for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study two non-truthful mechanisms that are, however, practically relevant to multi-agent environments, by virtue of their simplicity. Both mechanisms employ an item bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to VCG-based payment rules. For expressive classes of the agents’ valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently, we derive worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium.

x

Raimundas Vidunas, University of Athens

We establish the maximal number of Nash equilibria in bimatrix 5x4 games.

**Nash equilibria in bimatrix 5x4 games**Raimundas Vidunas, University of Athens

We establish the maximal number of Nash equilibria in bimatrix 5x4 games.

x

Giorgos Panagiotakos, National Technical University of Athens

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the locally bounded adversary model of Koo (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption distribution. On the positive side we devise protocols that match the obtained bounds and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible. Among others, we show that Koo's Certified Propagation Algorithm (CPA) is unique against locally bounded adversaries in ad hoc networks, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness in this case too. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.

**Reliable Broadcast with Respect to Topology Knowledge**Giorgos Panagiotakos, National Technical University of Athens

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the locally bounded adversary model of Koo (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption distribution. On the positive side we devise protocols that match the obtained bounds and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible. Among others, we show that Koo's Certified Propagation Algorithm (CPA) is unique against locally bounded adversaries in ad hoc networks, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness in this case too. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.

x

Chrysida Galanaki, University of Athens

Joint work with C. Nomikos, P. Rondogiannis, and W. W. Wadge

We present infinite games of perfect information that capture the semantics of logic programs with negation and other non-monotonic operators. We consider the following cases: (i) Normal logic programs, that have a finite number of rules and negation-as-failure, (ii) Infinite logic programs, that have an infinite number of rules, and (iii) Intensional logic programs, that have non-monotonic intensional operators.

**Game Semantics for Logic Programming**Chrysida Galanaki, University of Athens

Joint work with C. Nomikos, P. Rondogiannis, and W. W. Wadge

We present infinite games of perfect information that capture the semantics of logic programs with negation and other non-monotonic operators. We consider the following cases: (i) Normal logic programs, that have a finite number of rules and negation-as-failure, (ii) Infinite logic programs, that have an infinite number of rules, and (iii) Intensional logic programs, that have non-monotonic intensional operators.

x

Dimitris Letsios, Technical University of Munich

We consider the problem of scheduling a set of jobs, under precedence constraints, on a set of speed scalable parallel processors. The goal is to minimize the makespan of the schedule, i.e. the time at which the last job finishes its execution, without violating a given energy budget. This situation finds applications in computer devices whose life-time depends on a limited battery efficiency. In order to handle the energy consumption we use the energy model introduced in [Yao et al., FOCS’95], which captures the intuitive idea that the higher is the processor’s speed the higher is the energy consumption. We propose a (2-1/m)-approximation algorithm improving the best known poly-log(m)-approximation algorithm for the problem [Pruhs et al., TOCS 2008], where m is the number of the processors. We also extend the simple idea used for the above problem, in order to propose a generalized framework that finds applications to other scheduling problems in the speed scaling setting.

**Multiprocessor Speed Scaling with Precedence Constraints**Dimitris Letsios, Technical University of Munich

We consider the problem of scheduling a set of jobs, under precedence constraints, on a set of speed scalable parallel processors. The goal is to minimize the makespan of the schedule, i.e. the time at which the last job finishes its execution, without violating a given energy budget. This situation finds applications in computer devices whose life-time depends on a limited battery efficiency. In order to handle the energy consumption we use the energy model introduced in [Yao et al., FOCS’95], which captures the intuitive idea that the higher is the processor’s speed the higher is the energy consumption. We propose a (2-1/m)-approximation algorithm improving the best known poly-log(m)-approximation algorithm for the problem [Pruhs et al., TOCS 2008], where m is the number of the processors. We also extend the simple idea used for the above problem, in order to propose a generalized framework that finds applications to other scheduling problems in the speed scaling setting.

x

Costantinos Daskalakis, MIT

Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.

**Reductions from Mechanism to Algorithm Design**Costantinos Daskalakis, MIT

Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.

x

Euripides Markou, University of Thessaly

Joint work with Nicolas Nisse and Stephane Perennes

In Graph Searching, a team of searchers tries to capture an invisible fugitive who is moving arbitrary fast in a graph. Many variants of this problem have been studied with respect to the constraints that the searchers' strategy must satisfy. We study here the Exclusive Graph Searching problem in which two searchers can not occupy simultaneously a node. We will discuss the complexity of finding the minimum number of searchers capable of solving the problem in various classes of graphs. We show that the problem is NP-hard in planar graphs with maximum degree $3$. We will also present a graph family in which the problem of finding a monotone strategy of a minimum number of searchers remains NP-hard and some other graph families in which the problem can be solved in polynomial time.

**Exclusive Graph Searching in Various Graph Classes**Euripides Markou, University of Thessaly

Joint work with Nicolas Nisse and Stephane Perennes

In Graph Searching, a team of searchers tries to capture an invisible fugitive who is moving arbitrary fast in a graph. Many variants of this problem have been studied with respect to the constraints that the searchers' strategy must satisfy. We study here the Exclusive Graph Searching problem in which two searchers can not occupy simultaneously a node. We will discuss the complexity of finding the minimum number of searchers capable of solving the problem in various classes of graphs. We show that the problem is NP-hard in planar graphs with maximum degree $3$. We will also present a graph family in which the problem of finding a monotone strategy of a minimum number of searchers remains NP-hard and some other graph families in which the problem can be solved in polynomial time.

### Participants

First Name |
Last Name |
Affiliation |
---|---|---|

Chris | Adamo | National Technical University of Athens |

Georgios | Amanatidis | Athens University of Economics and Business |

Konstantinos | Ameranis | National Technical University of Athens |

Aris | Anagnostopoulos | Sapienza University of Rome |

Maria | Anagnostou | |

Alexandros | Angelopoulos | National Technical University of Athens |

Antonis | Antonopoulos | National Technical University of Athens |

Spyridon | Argyroiliopoulos | University of Athens |

Spyros | Argyroiliopoulos | University of Athens |

Makis | Arsenis | National Technical University of Athens |

Evangelos | Asimakopoulos | Delcam |

Charalampos | Asimakopoulos | National Technical University of Athens |

Georgia | Avarikioti | University of Athens |

Kyriakos | Axiotis | National Technical University of Athens |

Dimitrios | Bakas | University of Athens |

Katerina | Baousi | National Technical University of Athens |

Petros | Barbagiannis | Athens University of Economics and Business |

Giorgos | Birbas | Athens University of Economics and Business |

Konstandinos | Bitsakos | National Technical University of Athens |

Matthaios | Bournazos | National Technical University of Athens |

Ioannis | Caragiannis | University of Patras |

Angeliki | Chalki | University of Athens |

Evangelos | Chatziafratis | National Technical University of Athens |

Giorgos | Chatziantoniou | National Technical University of Athens |

Panagiotis | Cheilaris | UniversitÃ della Svizzera italiana |

Giorgos | Christodoulou | University of Liverpool |

Ilias | Diakonikolas | University of Edinburgh |

Christina | Diamantopoulou | Î£Î—ÎœÎœÎ¥ Î•ÎœÎ |

Katerina | Dimitrakopoulou | University of Athens |

Nikolaos | Dimitriou | |

Sotirios | Dimos | National Technological University of Athens |

Eleni | Evangelatou | National Technical University of Athens |

Maria | Fostini | National Technical University of Athens |

Dimitris | Fotakis | National Technical University of Athens |

Chrysida | Galanaki | University of Athens |

Myrto | Galenianou | University of Athens |

Panagiotis | Georgakopoulos | National Technical University of Athens |

Evangelia | Gergatsouli | National Technical University of Athens |

Nikolaos | Giachoudis | University of Thessaly |

Yiannis | Giannakopoulos | University of Oxford |

Agamemnon | Giannakopoulos | National Technical University of Athens |

Vasilis | Gkatzelis | Stanford University |

Kostis | Gkionis | National Technical University of Athens |

Maria | Gkolia | National Technical University of Athens |

Themistoklis | Gouleakis | MIT |

Vasilis | Goumas | National Technical University of Athens |

Panagiotis | Grontas | National Technical University of Athens |

Fotios | Gryllakis | University of Patras |

Konstantinos | Kaffes | National Technical University of Athens |

Kanela | Kaligosi | University of Athens |

Dimitrios | Kalogeropoulos | National Technical University of Athens |

Alexandros | Kalomoiros | National Technical University of Athens |

Konstantinos | Kanellis | University of Thessaly |

Pavlos | Kapoutsis | National Technical University of Athens |

Grigoris | Karagiorgos | TEI of Peloponnese |

Anna | Karasoulou | University of Athens |

Christina | Karousatou | National Technical University of Athens |

Yiannis | Katsandredakis | |

Angelos | Katselis | National Technical University of Athens |

Loukas | Kavouras | National Technical University of Athens |

Stefanos | Koffas | National Technical University of Athens |

Christos | Konaxis | University of Athens |

Vasiliki | Kontoura | National Technical University of Athens |

Petros | Kotsalas | National Technical University of Athens |

Natalia | Kotsani | National Technical University of Athens |

Eugenia | Kotzapanagiotou | University of Patras |

Grigorios | Koumoutsos | University Paris Diderot |

George | Kouroupas | Athens University of Economics and Business |

Vlasis | Koutsos | National Technical University of Athens |

Elias | Koutsoupias | University of Oxford |

Marios | Kouvaras | National Technical University of Athens |

Christina | Kozia | University of Patras |

Panagiotis | Kyriazis | National Technical University of Athens |

Nikolaos | Labrou | University of Athens |

Zoi | Lamprakou | National Technical University of Athens |

Philip | Lazos | National Technical University of Athens |

Alexandros | Leivaditis | University of Athens |

Konstantinos | Lentzos | UniversitÃ¤t Konstanz |

Nikos | Leonardos | University of Athens |

Dimitrios | Letsios | Technical University of Munich |

Matthaios | Letsios | |

Thanasis | Lianeas | National Technical University of Athens |

Vasileios | Livanos | National Technical University of Athens |

Michalis | Loulakis | National Technical University of Athens |

Thodoris | Lykouris | Cornell University |

Christiana | Lymouri | National Technical University of Athens |

Andreas | Maggiori | National Technical University of Athens |

Konstantina | Makridaki | Athens University Of Economics and Business |

Michail | Mamakos | University of Macedonia |

Andreas | Mantis | National Technical University of Athens |

Constantinos | Marakos | University of Patras |

Konstantina | Marga | University of Patras |

Alexander | Margelis | Athens University of Economics and Business |

Vangelis | Markakis | Athens University of Economics and Business |

Euripides | Markou | University of Thessaly |

Elena | Melachroinou | University of Patras |

Faidra Georgia | Monachou | National Technical University of Athens |

Alexandros | Moschos | National Technical University Of Athens |

Alexandra | Moshou | National Observation of Athens |

Lampros | Mousselimis | National Technical University of Athens |

Dimitrios | Myrisiotis | National Technical University of Athens |

Ioannis | Nemparis | National Technical University of Athens |

Aikaterini | Nikolidaki | National Technical University of Athens |

Aris | Pagourtzis | National Technical University of Athens |

Gerasimos | Palaiopanos | National Technical University of Athens |

Giorgos | Panagiotakos | National Technical University of Athens |

Dimitrios | Panagopoulos | Eureka Module |

Marianna | Panteli | University of Patras |

Orestis | Papadigenopoulos | National Technical University of Athens |

Giorgos | Papadimitriou | University of Athens |

Michalis | Papadopoullos | |

Maria | Papadopoulou | University of Cyprus |

Dafni | Papadopoulou | |

Vasileios | Papaefthymiou | National Technical University of Athens |

Katia | Papakonstantinopoulou | University of Athens |

Konstantinos | Papanikolaou | University of Athens |

Georgios | Papastergiou | National Technical University of Athens |

Thomas | Papastergiou | |

Despoina | Papatheodorou | National Technical University of Athens |

George | Paraksevopoulos | National Technical University of Athens |

Nikos | Parotsidis | University of Ioannina |

Elena | Partalidou | University of Crete |

Vangelis | Paschos | LAMSADE, University Paris-Dauphine |

George | Patseas | National Technical University of Athens |

Konstantinos | Patsourakos | University of Athens |

Chrystalla | Pavlou | National Technical University of Athens |

Matoula | Petrolia | University of Nantes |

Petros | Petropoulos | National Technical University of Athens |

Stavros | Petsalakis | University of Athens |

Christos | Pilichos | University of Athens |

Charikleia | Podimata | National Technical University of Athens |

Petros | Potikas | National Technical University of Athens |

Nikos | Protopapas | University of Patras |

Despoina | Psaradaki | Technical Educational Institute |

Ioannis | Psarros | University of Athens |

Eleni | Pylia | National Technical University of Athens |

Anna-Isavella | Rerra | Bioinformatics |

Maria | Revythi | Electrical Engineer@Computer Scientist, researcher |

Georgios | Routis | National Technical University of Athens |

Dimitris | Sakavalas | National Technical University of Athens |

Mario | Saldinger | National and Kapodistrian University of Athens |

Eleni | Sapountzi | University of Thessaly |

Dimitris | Schizas | National Technical University of Athens |

Babis | Schoinochoritis | University of Patras |

Emmanouil | Seferis | National Technical University of Athens |

Kyriakos | Sergis | National Technical University of Athens |

Alkmini | Sgouritsa | University of Liverpool |

Evangelos | Sigalas | University of Thessaly |

Ioannis | Sigalas | University of Athens |

Dimitris | Simos | SBA Research |

Georgios Aristeidis | Skarvelas | National Technical University of Athens |

Stratis | Skoulakis | National Technical University of Athens |

Aleksandros | Sobczyk | University of Patras |

Evaggelos | Souldatos | National Technical University of Athens |

Maria Ioanna | Spyrakou | University of Athens |

Betty | Statiri | University of Thessaly |

Aikaterini-Panagiota | Stouka | University of Athens |

Orestis | Telelis | Athens University of Economics and Business |

Peli | Teloni | University of Athens |

Iakovos | Thiraios | National Technical University of Athens |

Leonidas | Tsepenekas | National Technical University of Athens |

Elias | Tsigaridas | INRIA |

Sofia | Tsilidou | |

Dimitris | Tsipras | National Technical University of Athens |

Evanthia | Tsitsoka | University of Patras |

Panagiotis | Tsokas | University of Patras |

Ioannis | Tzanakakis | Technical University of Crete |

Isidoros | Tziotis | University of Athens |

Thomaida | Tzovara | Athens University of Economics and Business |

Charilaos | Tzovas | National Technical University of Athens |

Panagiotis | Vasilopoulos | National Technical University of Athens |

Simon | Vellas | National Technical University of Athens |

Vasiliki | Velona | |

Theodora | Vergou | |

Angelina | Vidali | Duke University |

Raimundas | Vidunas | University of Athens |

John | Violos | PhD Student |

Aristotelis | Vlachos | National Technical University of Athens |

Christos | Vlassopoulos | Athens University of Economics and Business |

Emmanouil Vasileios | Vlatakis Gkaragkounis | National Technological University of Athens |

Panagiota | Vompiri | Athens University Of Economics and Business |

Alexandros | Voudouris | University of Patras |

Georgios | Vountourakis | University of Athens |

Ioannis | Vrontakis | University of Patras |

Lefteris | Xenarios | University of Athens |

George | Xenophontos | National Technical University of Athens |

Stathis | Zachos | National Technical University of Athens |

Zafeirakis | Zafeirakopoulos | RISC-Linz |

Lydia | Zakynthinou | National Technical University of Athens |

Nikolaos-Rafail | Zampelis | National Technical University of Athens |

Manolis | Zampetakis | National Technical University of Athens |

Nikolaos | Zarifis | National Technical University of Athens |

George | Zirdelis | National Technical University of Athens |

Vassilis | Zissimopoulos | University of Athens |

### Venue

Προβολή μεγαλύτερου χάρτη

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.