5th Athens Colloquium on Algorithms and Complexity – ACAC 2010 August 26 – 27, National Technical University of Athens, Greece
Thursday, August 26
9:15 – 9:30	Opening Remarks
9:30 – 10:30	Invited Session 1 Lefteris Kirousis, University of Patras and RA Computer Technology Institute Coloring Random Graphs: A Short and Biased Survey
10:30 – 11:00	Coffee Break
11:00 – 13:00	Session 1 Ioannis Caragiannis, University of Patras and RA Computer Technology Institute Socially Desirable Approximations for Dodgson's Voting Rule Evangelos Markakis, Athens University of Economics and Business Approximation Algorithms and Mechanism Design for Minimax Approval Voting Orestis Telelis, CWI Amsterdam Discrete Strategies in Keyword Auctions and their Inefficiency for Locally Aware Bidders Angelina Vidali, Max-Planck Institut fur Informatik Unification of Characterizations of Combinatorial Auction's Subdomains
13:00 – 14:00	Lunch Break
14:00 – 16:00	Session 2 Aris Anagnostopoulos, University of Rome La Sapienza Online Network Design with Outliers Panagiotis Cheilaris, Ben-Gurion University of the Negev Graph Unique-Maximum and Conflict-Free Colourings Tobias Mueller, CWI Amsterdam Line Arrangements and Geometric Graph Classes Tamara Mchedlidze, National Technical University of Athens Unilateral Orientation of Mixed Graphs
16:00 – 16:30	Coffee Break
16:30 – 18:00	Session 3 Aristeidis Tentes, New York University On the (In)Security of RSA Signatures Paris Koutris, National Technical University of Athens k-shot Distributed Broadcasting in Radio Networks Othon Michail, RA Computer Technology Institute, Patras New Models for Population Protocols
Friday, August 27
9:30 – 10:30	Invited Session 2 Ioannis Emiris, National and Kapodistrian University of Athens Euclidean Embeddings of Rigid Graphs
10:30 – 11:00	Coffee Break
11:00 – 13:00	Session 4 Iordanis Kerenidis, CNRS - University Paris On the Power of a Unique Quantum Witness Spyridon Antonakopoulos, Bell Laboratories, Alcatel-Lucent Minimum-Cost Network Design with (Dis)economies of Scale Nikos Mutsanas, IDSIA, Lugano Scheduling with Precedence Constraints of Low Fractional Dimension Elias Tsigaridas, Aarhus University Random Polynomials and Expected Complexity of Real Solving
13:00 – 14:00	Lunch Break
14:00 – 15:30	Session 5 Alexis Kaporis, University of the Aegean Interpolation Search Emmanouil Pountourakis, Northwestern University A Complete Characterization of Group-Strategyproof Mechanisms of Cost-Sharing Vasilis Gkatzelis, Courant Institute, New York University Coordination Mechanisms for Weighted Sum of Completion Times in Machine Scheduling
15:30 – 16:00	Coffee Break
16:00 – 17:00	Session 6 Simon Yoffe, Tel-Aviv Academic College A Simple and Efficient Union-Find-Delete Algorithm Vissarion Fisikopoulos, National and Kapodistrian University of Athens Enumerating Classes of Regular Triangulations
17:00 – 17:45	Break
17:45 – 18:30	Invited Session 3 Costis Daskalakis, Massachussets Institute of Technology Geometrically Embedded Local Search
21:00	Dinner, Taverna Virinis (Archimidous 11, Pagkrati, Tel: 210-7012153)