1998 Best Student ICALP Paper Award

Chi-Jen Lu and Slawomir Lasota

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


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"


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.
e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.