LCS Technical Memos (1974 - 2003): Recent submissions
Now showing items 232-234 of 486
-
Two Undecidability Results in Probabilistic Automata Theory
(1985-06)The language accepted by a probabilistic finite state acceptor with an isolated cutpoint is known to be regular. We show that determining if a cutpoint is isolated is undecideable. -
A Mixed Integer Linear Programming Problem Which is Efficiently Solvable
(1985-07)Efficient algorithms are known for the simple linear programming problem where each inequality is of the form xj-xi<=aij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This ... -
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
(1986-09)A new model for weak random physical sources is presented. The new model strictly generalizes previous models (e.g. the Santha and Vazirani model [26]). The sources considered output strings according to probability ...
