The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>

We show analogues of a theorem due to Valiant and Vazirani
for intractable parameterized complexity classes such as W[P], W[SAT]
and the classes of the W-hierarchy as well as those of the A-hierarchy.
We do so by proving a general ``logical'' version of it which may be of
independent interest

... more >>>