enter search term and/or author name
The approximability of MAX CSP with fixed-value constraints
Vladimir Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin
Article No.: 16
In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to...
We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(⋅) obtained by Armoni, Ta-Shma, Wigderson...
In this article, we show that keeping track of history enables significant improvements in the communication complexity of dynamic network protocols. We present a communication optimal maintenance of a spanning tree in a dynamic network. The...
Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types
Alain Frisch, Giuseppe Castagna, Véronique Benzaken
Article No.: 19
Subtyping relations are usually defined either syntactically by a formal system or semantically by an interpretation of types into an untyped denotational model. This work shows how to define a subtyping relation semantically in the presence of...