Derandomize algorithm P

[Isak Lyckberg]

Use the method of conditional probabilities to derandomize algorithm P.

[Isak Lyckberg]

So, if I understand this correctly (have been thinking yesterday and this morning), either we argue that the Gaussian elimination solving Ax=y+r for an r, and every y in Y, can be used to calculate E[|X|] and runs in |Y|*n^O(1) time, no matter the A (that is, no matter how large null space A has and how that coincides with an arbitrary r).

Or, we show that we can compute E[|X'|] for Ax' = y+r', where r' is the same as r but with the last bit fixed to either 0 or 1, in |Y|*n^O(1) time.

The question is, can we argue as in the first way, just with referring to Gaussian elimination, or do we have to construct a theorem like in Lemma 6 in The Parity of Directed Hamiltonian Cycles?

[Thore Husfeldt]

No time now, but if I understand your question correctly: The former.

[Isak Lyckberg]

Perfect. Will write up a proper argument as soon as possible. Will be away until Tuesday afternoon, but as soon as possible.

[Isak Lyckberg]

I guess this is solved since... May?