Title: Existence and computation of equilibria of first-price auctions with integral valuations and bidsSpeaker: Rocio SantillanTime: Tue Nov 25th 2008, 14:15-15:00Location: Turing-014Abstract:In classical auction theory, the existence of pure strategy Nash equilibria (PSNE) of first-price auctions has been established under avariety of mild…

Deciding the Undecidable - Who's That Rice Fellow Anyway?Every computer program yields a number of questions. The bigone is "Does it work?", but more specifictasks of debugging andoptimization pose a wide variety of separate questions. In an idealworld, automatic tools would provide the programmers with these answer,but unfortunately the famous…

Title: Program Development by Proof Transformation: Recent EvolutionsAbstract:To Prune a constructive proof M means to drop all the redundant case distinctionsand existential eliminations inferences in M. Christopher Alan Goad showed that a program extracted from a pruned proof can be more performing w.r.t. a program extracted from the same but…

Title: Theory of mind and bounded rationality without interpretive overheadAbstract:Computers and humans that work well together have beliefs about eachother's intentions, about each other's desires about each other'sbeliefs, and so on. To practise such a _theory of mind_, agents needto slip easily into each other's shoes. Ideally, when Agent A…

Title: Deterministic Structures over P2P NetworksSpeakers: Kostas Tsichlas, Aristotle University of Thessaloniki & Spyros Sioutas, Ionian UniversityAbstract: We design a new P2P data structure, called the Deterministic Distributed tree (DDtree). The DDtree compares favourably to other designs for the following reasons: a) it divides the overlay…

This thesis describes the optimal minimum spanning tree algorithm given by Pettieand Ramachandran (in Journal of the ACM, 2002). The algorithm presented finds aminimum spanning tree of a graph with n vertices and m edges deterministically in timeO (T* (m, n)), where T* is the minimum number of edge-weight comparisons needed todetermine the…

Title: Compressed Representations of Permutations, and ApplicationsSpeake: Jérémy Barbay, Universidad de ChileAbstract:We explore various techniques to compress a permutation $\\pi$ over $n$ integers, takingadvantage of ordered subsequences in $\\pi$, while supporting its application $\\pi(i)$ and the application of its inverse $\\pi^{-1}(i)$ in…