Last update:
August 19, 2009

4th Athens Colloquium on Algorithms and Complexity (ACAC 2009)

August 20-21, 2009

Athens University of Economics and Business

The program is available in PDF.

Thursday, August 20
9:30-10:00 Registration – Coffee
Invited Session
Marios Mavronicolas, University of Cyprus
   Facets of the Fully Mixed Nash Equilibrium Conjecture
11:00-11:30 Coffee break
Session 1
Incentive-Compatible Robust Line Planning
   Apostolos Bessas, Spyros Kontogiannis, Christos Zaroliagis
Taxes for Linear Atomic Congestion Games
   Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos
Efficient Methods for Selfish network Design
   Dimitris Fotakis, Alexis Kaporis, Paul Spirakis
13:00-15:00 Lunch break
Session 2
On the Connection between Interval Size Functions and Path Counting
   Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagoutrzis, Aris Tentes
Optimal Quantum Strong Coin Flipping
   André Chailloux, Iordanis Kerenidis
Duality Bounds on the Cutoff Rate with Applications to Ricean Fading
   Amos Lapidoth, Natalia Miliou
Lower Bounds on the Randomized Communication Complexity of Read-Once Function
   Nikos Leonardos, Michael Saks
17:00-17:30 Coffee break
Session 3
An Exponential Lower Bound on OBDD Refutations for Pigeonhole Formulas
   Olga Tveretina, Carsten Sinz, Hans Zantema
Database Algorithms Solving the Monadic Second-order Logic Evaluation Problem on Finite Trees
   Eugénie Foustoucos, Labrini Kalantzi
On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture
   Stavros Vassos, Hector J. Levesque
Friday, August 21
09:30-10:00 Coffee
Session 4
Multihomogeneous Resultant Formulae for Systems with Scaled Support
   Ioannis Z. Emiris, Angelos Mantzaflaris
Exact Delaunay Graph of Smooth Convex Pseudo-circles: General Predicates, and Implementation for Ellipses
   Ioannis Z. Emiris, Elias P. Tsigaridas, George M. Tzoumas
11:00-11:30 Coffee break
Session 5
Overlapping Coalition Formation
   Georgios Chalkiadakis, Edith Elkind, Evangelos Markakis, Nick Jennings
On the Geometry of Truthfulness
   Angelina Vidali
Complexity of Strong Implementability
   Clemens Thielen, Sven O. Krumke
13:00-15:00 Lunch break
Session 6
Approximating the Max Edge-coloring Problem
   Nicolas Bourgeois, Giorgio Lucarelli, Ioannis Milis, Vangelis Th. Paschos
Local Search Performance Guarantees for Parallel Machine Scheduling with Eligibility Constraints
   Diego Recalde, Cyriel Rutten, Petra Schuurman, Tjark Vredeveld
16:00-16:30 Coffee break
Session 7
Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs
   Ioannis Z. Emiris, Elias P. Tsigaridas, Antonios Varvitsiotis
Cartesian Product of Hypergraphs: Properties and Algorithms
   Alain Bretto, Yannick Silvestre, Theirry Vallée
Regular Matroids with Graphic Cocircuits
   Konstantinos Papalamprou, Leonidas Pitsoulis
21:00 Dinner at Yandes (44 Valtetsiou Street)