Title: On Pure and (approximate) Strong Equilibria of Facility Location GamesSpeaker: Orestis TelelisTime: Tue Nov 4th 2008, 14:15-15:00Location: Turing-014Abstract:We study social cost losses in Facility Location games, where n selfish agents install facilities over anetwork and connect to them, so as to forward their localdemand (expressed by a…

Title: Towards compatible and interderivable semantic specifications for theScheme programming language, part II: reduction semantics and abstractmachinesSpeaker: Olivier DanvyAbstract:We present a context-sensitive reduction semantics for a lambda-calculuswith explicit substitutions and store and we show that the functionalimplementation of this…

Title: Towards compatible and interderivable semantic specifications for theScheme programming language, part II: reduction semantics and abstractmachinesSpeaker: Olivier DanvyAbstract:We present a context-sensitive reduction semantics for a lambda-calculuswith explicit substitutions and store and we show that the functionalimplementation of this…

Title: Incremental Topological OrderingSpeaker: Deepak Ajwani, Aarhus University, MADALGOAbstract:I will present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges inserted. I will then show an average case…

Transparency – looking back at three decades of researchSince the early days of HCI, transparency has been a conceptual focus and a concern for design - isit possible to make the computer go away, be unnoticedto the human user? Should the computer be viewed as a conversation partner or disappear just like we do not need to know about car…

Title: Deterministic Graphical Games RevisitedSpeaker: Daniel AnderssonTime: Tue Nov 11th 2008, 14:15-15:00Location: Turing-014Abstract:We revisit Washburn's deterministic graphical games, a natural generalization of the perfect information win/lose games commonly solved by retrograde analysis. We study the complexity of solving deterministic…

Title: Online Sorted Range ReportingSpeaker: Mark Greve, Aarhus University, MADALGOAbstract: We study the following extension of the static one-dimensional range reporting problem. For an array A of n elements, build a data structure that supports the query: Given two indices i=j and an integer k, report the k smallest elements in the sub array…

Title: Privacy-enhancing first-price auctions using rational cryptographySpeaker: Jesper Buus NielsenTime: Tue Nov 18th 2008, 14:15-16:00Location: Turing-014Abstract: TBAWe consider enhancing a sealed-bid single-item auction with privacy concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about…

Title: "On Context Awareness in Ubiquitous Computing"Speaker: Doina BucurAbstract:This talk visits the author's PhD dissertation (available online at http://www.daimi.au.dk/~doina/), submitted on Sept 1 to the University of Aarhus, and entitled "On Context Awareness in Ubiquitous Computing". The thesis contributes to the field of ubiquitous…

Title: Using the right BVH in each situationSpeaker: Peter Hachenberger, MADALGO, Aarhus UniversityAbstract:Bounded volume hierarchies (BVHs) are efficient and versatile search data structures for geometric data, which are similar to binary space partitions (BSPs). Like BSPs, they store the geometric data in the leafs of a search tree. While each…

Title: On Context Awareness in Ubiquitous ComputingAbstractThis dissertation contributes to the young ?eld of ubiquitous computing, a so-called third wave of computing expected to succeed the current Internet era. Theparadigm of ubiquitous computing calls for distributing the computation power among the people and objects in the human environment…

Title: Delphin – Yet Another Way to Program with Programs.Speaker: Carsten Schuermann, IT University of Copenhagen Abstract: Many different dependently typed programming languages are currently developed invarious places, often with the promise of better (faster, more efficient, more concise, verifiable) code. Application areas of…

Title: Selecting Sums in ArraysSpeaker: Allan Grønlund Jørgensen, Aarhus University, MADALGOAbstract:In an array of $n$ numbers each of the $\\binom{n}{2}+n$ contiguous subarrays define a sum. In this paper we focus on algorithms for selecting and reporting maximal sums from an array of numbers. First, we consider the problem of reporting $k$…

Title: The Expressivity of Universal Timed CCP:Undecidability of Monadic FLTL and Closure operators for SecurityAbstract:The timed concurrent constraint programing model (tcc) is a declarative framework, closely related to First-Order Linear Temporal Logic (FLTL), for modeling reactive systems. The universal tcc formalism (utcc) is an…