Group Testing with Random Pools: Phase Transitions and Optimal Strategy

The problem of Group Testing is to identify defective items out of a set of objects by means of pool queries of the form “Does the pool contain at least a defective?”. The aim is of course to perform detection with the fewest possible queries, a problem which has relevant practical applications in different fields including molecular biology and computer science. Here we study GT in the probabilistic setting focusing on the regime of small defective probability and large number of objects, p→0 and N→∞. We construct and analyze one-stage algorithms for which we establish the occurrence of a non-detection/detection phase transition resulting in a sharp threshold, \(\overline{M}\), for the number of tests. By optimizing the pool design we construct algorithms whose detection threshold follows the optimal scaling \(\overline{M}\propto Np|\log p|\). Then we consider two-stages algorithms and analyze their performance for different choices of the first stage pools. In particular, via a proper random choice of the pools, we construct algorithms which attain the optimal value (previously determined in (Mézard and Toninelli, arXiv:0706.3104)) for the mean number of tests required for complete detection. We finally discuss the optimal pool design in the case of finite p.     

On Quantum Phase Transition. I. Spinless Electrons Strongly Correlated with Ions

We study a large class F of models of the quantum statistical mechanics dealing with two types of particles. First the spinless electrons are quantum particles obeying to the Fermi statistics, they can hop. Secondly the ions which cannot move, are classical particles. The Falicov–Kimball (FK) model⁽¹⁾ is a well known model belonging to F, for which the existence of an antiferomagnetic phase transition was proven in the seminal paper of Kennedy and Lieb.⁽²⁾ This result was extended by Lebowitz and Macris.⁽³⁾ A new approach to this problem based on quantum selection of the ground states was proposed in ref. 4. In this paper we extend this approach to show that, under the strong insulating condition, any hamiltonian of the class F admits, at every temperature, an effective hamiltonian, which governs the behaviour of the ions interacting through forces mediated by the electrons. The effective hamiltonians are long range many body Ising hamiltonians, which can be computed by a cluster expansion expressed in term of the quantum fluctuations. Our main result is that we can apply the powerfull results of the classical statistical mechanics to our quantum models. In particular we can use the classical Pirogov–Sinai theory to establish a hierarchy of phase diagrams, we can also study of the behaviour of the quantum inter- faces,⁽²⁹⁾ and so on...     

Mean-Field Driven First-Order Phase Transitions in Systems with Long-Range Interactions

We consider a class of spin systems on ℤ ^d with vector valued spins (S _x ) that interact via the pair-potentials J _x,y S _x ⋅S _y . The interactions are generally spread-out in the sense that the J _x,y 's exhibit either exponential or power-law fall-off. Under the technical condition of reflection positivity and for sufficiently spread out interactions, we prove that the model exhibits a first-order phase transition whenever the associated mean-field theory signals such a transition. As a consequence, e.g., in dimensions d≥3, we can finally provide examples of the 3-state Potts model with spread-out, exponentially decaying interactions, which undergoes a first-order phase transition as the temperature varies. Similar transitions are established in dimensions d = 1,2 for power-law decaying interactions and in high dimensions for next-nearest neighbor couplings. In addition, we also investigate the limit of infinitely spread-out interactions. Specifically, we show that once the mean-field theory is in a unique “state,” then in any sequence of translation-invariant Gibbs states various observables converge to their mean-field values and the states themselves converge to a product measure.     

低温诱导桑蚕体内腺体相行为的高分辨^13C固体核磁共振研究

为什么蚕在常温常压水溶液条件下即能纺出力学性能优异的蚕丝纤维, 一直是科学家们感兴趣的问题. 在过去的几十年, 人们曾用多种表征手段, 如双折射、扫描电镜、原子力显微镜和电子散射等, 在界观尺度下对蚕在吐丝过程中腺体的相行为进行研究. 发现腺体在靠近吐丝口时呈液晶态, 并认为这是导致蚕丝力学性能的重要因素. 本文则在分子水平尺度下利用核磁共振方法, 对五龄蚕活体在常温和6 ℃下存储数天后解剖的腺体进行研究. 经对化学位移及其线型的各向异性分析发现, 当将体内腺体沿吐丝方向分为3部, 即后部、中部及靠近吐丝口的前部时, 常温下, 腺体后部和中后部分子呈无规线团, 而腺体中中部、中前部和前部分子呈液晶态. 6 ℃时, 中后部分子亦呈液晶态, 前部分子排列则各向异性更大, 说明更为有序. 这种液晶态呈分形结构, 在小于纳米尺度下为无规线团, 大于纳米尺度呈有序排列. 这表明, 降温过程可使呈无规线团的丝素蛋白分子转变为液晶态, 其效果如同蚕在吐丝过程中对其腺体施加的剪切应力. 该结果对于人们探索人工合成高性能类丝素纤维的纺丝工艺和条件将有启发和指导作用.