1998 Best Student ICALP Paper Award

Chi-Jen Lu and Slawomir Lasota

Chi-Jen Lu:
"Improved pseudorandom generators for combinatorial rectangles"

Abstract:

We explicitly construct a pseudorandom generator using O(log m + log d + log^{3/2} 1/\epsilon) bits that approximates the volume of any combinatorial rectangle in [m]^d = {1,...,m}^d to within \epsilon error. This improves on the previous construction by Armoni, Saks, Wigderson, and Zhou using O(log m + log d + log^2 1/\epsilon) bits. For a subclass of rectangles with at most t >= log 1/\epsilon nontrivial dimensions and each dimension being an interval, we also give a pseudorandom generator using O(loglog d + log 1/\epsilon log^{1/2} t/(log 1/\epsilon)) bits, which again improves the previous upper bound O(loglog d + log 1/\epsilon log t/(log 1/\epsilon)) by Chari, Rohatgi, and Srinivasan.

Slawomir Lasota:
"Partial-congruence factorization of bisimilarity induced by open maps"

Abstract:

We investigate some relationships between bisimilarity defined by open maps and behavioural equivalence factorized by indistinguishability relations. This is done in the setting of a concrete category supporting algebraic constructions of subobject and quotient. Some sufficient condition is found for bisimilarity to be factorizable by the greatest open congruences. Moreover, we find a necessary and sufficient condition for a factorization of bisimilarity: quotients by all maximal open congruences are isomorphic. The general results are motivated and illustrated by important examples: transition systems, event structures and presheaf models.