Prange’s information set algorithm is a well-known decoding algorithm for linear codes. It decodes corrupted codewords of most 𝔽₂-linear codes C of message length n up to relative error rate O(log n / n) in poly(n) time. We show that the error rate can be improved to O((log n)² / n), provided: (1) the decoder has access to a polynomial-length advice string that depends on C only, and (2) C is n^{-Ω(1)}-balanced. As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate. Our main technical result is that the Hamming weight of Hw, where the rows of H are a random sample of short dual codewords, measures the proximity of a received word w to the code in the regime of interest. Given such H as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding Hw for an arbitrary polynomial-size advice matrix H.

We close the gap between black-box and non-black-box constructions of composable secure multiparty computation in the plain model under the minimal assumption of semi-honest oblivious transfer. The notion of protocol composition we target is angel-based security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an angel that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone. Angel-based security can be achieved using non-black-box constructions in max(R_OT,Õ(log n)) rounds where R_OT is the round-complexity of semi-honest oblivious transfer. However, current best known black-box constructions under the same assumption require max(R_OT,Õ(log² n)) rounds. If R_OT is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor log n. We close this gap by presenting a max(R_OT,Õ(log n)) round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.

Automated visual tracking of cells from video microscopy has many important biomedical applications. In this paper, we model the problem of cell tracking over pairs of video microscopy image frames as a minimum weight matching problem in bipartite graphs. The bipartite matching essentially establishes one-to-one correspondences between the cells in different frames. A key advantage of using bipartite matching is the inherent scalability, which arises from its polynomial time-complexity. We propose two different tracking methods based on bipartite graph matching and properties of Gaussian distributions. In both the methods, i) the centers of the cells appearing in two frames are treated as vertices of a bipartite graph and ii) the weight matrix contains information about distance between the cells (in two frames) and cell velocity. In the first method, we identify fast-moving cells based on distance and filter them out using Gaussian distributions before the matching is applied. In the second method, we remove false matches using Gaussian distributions after the bipartite graph matching is employed. Experimental results indicate that both the methods are promising while the second method has higher accuracy.