Among the most important complexity problems in
coding theory are the maximun likelihood decoding
and the computation of the minimun distance.
In this talk, we explain a self-contained, quick and
transparent proof of the NP-hardness of these
problems based on the subset sum problem over
finite fields.

Wave propagation in random media with long-range correlations was recently stimulated by data collections showing that the medium of propagation presented some long-range correlation effects. We will analyze the random Schrdinger equation to show that a wave propagating in a random medium with slowly decaying correlations undergoes some anomalous decoherence effects.

Given two integers, we can compute their greatest common divisor
efficiently using Euclid's algorithm. Howgrave-Graham formulated
an approximate version of this question, asking ``What if instead of
exact multiples of some common divisor, we only know approximations?''
This problem has many applications in cryptography, particularly
partial key recovery for RSA. In this talk, I will show how to extend
Howgrave-Graham's algorithm from two approximate multiples to many
approximate multiples. This gives a more detailed analysis of the
hardness assumption underlying the recent fully homomorphic
cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While
these results do not challenge the suggested parameters, a
$2^{n^{2/3}$ approximation algorithm for lattice basis reduction in
$n$ dimensions could be used to break these parameters.

Joint work with Henry Cohn

Spectral sensing involves a range of technologies for detecting, identifying chemicals and biological agents. An important application is in homeland security where a critical problem is identification of unknown explosives. Though the advances of modern spectroscopy technology have made it possible to classify pure chemicals by spectra, realistic data are often composed of mixtures of chemicals and environmental noise.

In most cases, one has to deal with a so called blind signal(source) separation (BSS) problem. Conventional approaches such as NMF and ICA are non-convex and too general to be robust and reliable in real-world applications. Based on a partial knowlege of the data (e.g. local spectral sparseness), we are able to reduce the problem to a series of convex sub-problems. Compressive sensing algorithms are also brought into play. The methods will be illustrated in processing of datasets from NMR, DOAS,and Raman spectroscopy.