Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.

A positivity result in the theory of Macdonald polynomials

We outline here a proof that a certain rational function Cn(q, t), which has come to be known as the “q, t-Catalan,” is in fact a polynomial with positive integer coefficients. This has been an open problem since 1994. Because Cn(q, t) evaluates to the Catalan number at t = q = 1, it has also been an open problem to find a pair of statistics a, b on the collection

Adjoint modular Galois representations and their Selmer groups

In the last 15 years, many class number formulas and main conjectures have been proven. Here, we discuss such formulas on the Selmer groups of the three-dimensional adjoint representation ad(φ) of a two-dimensional modular Galois representation φ. We start with the p-adic Galois representation φ0 of a modular elliptic curve E and present a formula expressing in terms of L(1, ad(φ0)) the intersection number of the elliptic curve E and the complementary abelian variety inside the Jacobian of the modular curve. Then we explain how one can deduce a formula for the order of the Selmer group Sel(ad(φ0)) from the proof of Wiles of the Shimura–Taniyama conjecture. After that, we generalize the formula in an Iwasawa theoretic setting of one and two variables. Here the first variable, T, is the weight variable of the universal p-ordinary Hecke algebra, and the second variable is the cyclotomic variable S. In the one-variable case, we let φ denote the p-ordinary Galois representation with values in GL2(Zp[[T]]) lifting φ0, and the characteristic power series of the Selmer group Sel(ad(φ)) is given by a p-adic L-function interpolating L(1, ad(φk)) for weight k + 2 specialization φk of φ. In the two-variable case, we state a main conjecture on the characteristic power series in Zp[[T, S]] of Sel(ad(φ) ⊗ ν−1), where ν is the universal cyclotomic character with values in Zp[[S]]. Finally, we describe our recent results toward the proof of the conjecture and a possible strategy of proving the main conjecture using p-adic Siegel modular forms.

Gene recognition via spliced sequence alignment.

Gene recognition is one of the most important problems in computational molecular biology. Previous attempts to solve this problem were based on statistics, and applications of combinatorial methods for gene recognition were almost unexplored. Recent advances in large-scale cDNA sequencing open a way toward a new approach to gene recognition that uses previously sequenced genes as a clue for recognition of newly sequenced genes. This paper describes a spliced alignment algorithm and software tool that explores all possible exon assemblies in polynomial time and finds the multiexon structure with the best fit to a related protein. Unlike other existing methods, the algorithm successfully recognizes genes even in the case of short exons or exons with unusual codon usage; we also report correct assemblies for genes with more than 10 exons. On a test sample of human genes with known mammalian relatives, the average correlation between the predicted and actual proteins was 99%. The algorithm correctly reconstructed 87% of genes and the rare discrepancies between the predicted and real exon-intron structures were caused either by short (less than 5 amino acids) initial/terminal exons or by alternative splicing. Moreover, the algorithm predicts human genes reasonably well when the homologous protein is nonvertebrate or even prokaryotic. The surprisingly good performance of the method was confirmed by extensive simulations: in particular, with target proteins at 160 accepted point mutations (PAM) (25% similarity), the correlation between the predicted and actual genes was still as high as 95%.

The cutoff phenomenon in finite Markov chains.

Natural mixing processes modeled by Markov chains often show a sharp cutoff in their convergence to long-time behavior. This paper presents problems where the cutoff can be proved (card shuffling, the Ehrenfests' urn). It shows that chains with polynomial growth (drunkard's walk) do not show cutoffs. The best general understanding of such cutoffs (high multiplicity of second eigenvalues due to symmetry) is explored. Examples are given where the symmetry is broken but the cutoff phenomenon persists.