Offentlige arrangementer

Kristoffer Arnsfelt Hansen, University of Aarhus, Department of Computer Science

There is coffee and cake at this seminar.

Abstract: Semi-algebraic geometry is concerned with the set of real solutions of systems of polynomial equations and inequalities, called semi-algebraic sets. In this lecture we will introduce semi-algebraic sets from basics. Next we will prove the Tarski-Seidenberg theorem, that semi-algebraic sets in (n+1)-dimensional space projects to semi-algebraic sets in n-dimensional space. Coupled with parametric versions of real root counting techniques such as Sturm sequences (that we will also cover from basics) this gives us a decision procedure for determining if the given system has a real solution.

This lecture marks the beginning of a series of lectures on semi-algebraic geometry. The intent is that it will over time transform into a reading/lecture series working towards research problems.

See www.cs.au.dk/~bjarke/compmath/ for details.

Speaker: Martin Olsen, Aarhus University

Abstract:

The founders of Google introduced the PageRank algorithm that computes an estimate of the popularity of each web page based solely on the link structure of the web graph - these estimates are the so called PageRank values. A page will achieve one of the top spots of search results if it has a high PageRank value and it matches the search criteria for the actual Google search.

For a given node t in a directed graph G(V,E) and a positive integer k we study the problem of computing a set of k new links pointing to t - so called backlinks to t - producing the maximum increase in the PageRank value of t. This problem is known as "Link Building" in the www context. We present a theorem showing how the topology of the graph comes in to play when evaluating potential new backlinks. Based on the theorem we show that no FPTAS exists for Link Building under the assumption NP$\

eq$P and we also show that Link Building is W[1]-hard - strongly suggesting that Link Building is not fixed parameter tractable. We prove these results by reduction from the independent set problem on regular graphs. Finally, we use the theorem to characterize sets of backlinks producing a significant increase in the PageRank value of t.

Host: Gerth Stølting Brodal

Speaker:

Kristoffer H. Rose

IBM Thomas J. Watson Research Center

Abstract:

In this talk I'll show how a compiler from a functional language to Java source can be fully implemented on a single page (or so) using higher-order rewriting technology (including HO syntax) for all aspects of the translation, and how analysis and optimization based on formal specifications can be incorporated effectively. All code shown is available from crsx.sourceforge.net.

Biosketch:

I received my Ph.D. in computer science from the University of Copenhagen (DIKU) in 1996 on research in using formal rewriting systems to understand the operational semantics and memory management in functional programming languages. I continued academic research with a year as a post-doc at BRICS (Århus) and three as an associate professor at Ecole Normale Supérieure (Lyon), investigating and further developing results in rewriting, especially explicit substitution. Since joining the IBM Thomas J. Watson Research Center in 2000, I have focused on making XML processing scalable even over diverse and distributed data sources, including large data collections and data not in XML, by applying, combining, and advancing, techniques from programming languages, database query analysis, and higher-order rewriting, to the XML processing languages XSLT and XQuery.