enter search term and/or author name
We close affirmatively a question that has been open for long time: decidability of the HOM problem. The HOM problem consists in determining, given a tree homomorphism H and a regular tree language L represented by a tree automaton,...
Decomposing combinatorial auctions and set packing problems
Georg Gottlob, Gianluigi Greco
Article No.: 24
Combinatorial auctions allow bidders to bid on bundles of items rather than just on single items. The winner determination problem in combinatorial auctions is the problem of determining the allocation of items to bidders such that the sum of the...
Matrix sparsification and nested dissection over arbitrary fields
Noga Alon, Raphael Yuster
Article No.: 25
The generalized nested dissection method, developed by Lipton et al. , is a seminal method for solving a linear system Ax=b where A is a symmetric positive definite matrix. The method runs extremely fast whenever...
All-pairs shortest paths in O(n2) time with high probability
Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick
Article No.: 26
We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n2), in expectation...
In the traditional data exchange setting, source instances are restricted to be complete in the sense that every fact is either true or false in these instances. Although natural for a typical database translation scenario, this restriction...
Game semantics for a polymorphic programming language
Article No.: 29
This article presents a game semantics for higher-rank polymorphism, leading to a new model of the calculus System F, and a programming language which extends it with mutable variables. In contrast to previous game models of polymorphism, it is...