@article{3197,
abstract = {The problem of obtaining the maximum a posteriori estimate of a general discrete Markov random field (i.e., a Markov random field defined using a discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximation algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger (1976) for a special case and independently in Chekuri et al. (2001), Koster et al. (1998), and Wainwright et al. (2005) for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation of Ravikumar and Lafferty (2006); and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki (2003) for two label problems and later extended by Kumar et al. (2006) for a general label set.
We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e., provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which define constraints using random variables that form cycles or cliques in the graphical model representation of the random field. Using some examples we show that the new SOCP relaxations strictly dominate the previous approaches.},
author = {Kumar, M Pawan and Vladimir Kolmogorov and Torr, Philip H},
journal = {Journal of Machine Learning Research},
pages = {71 -- 106},
publisher = {Microtome Publishing},
title = {{An analysis of convex relaxations for MAP estimation of discrete MRFs}},
volume = {10},
year = {2009},
}
@inproceedings{3503,
abstract = {We give polynomial-time algorithms for computing the values of Markov decision processes (MDPs) with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path in the MDP is the limsup (resp. liminf) of all rewards along the path. The value of an MDP is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the MDP. Using our result on MDPs, we show that turn-based stochastic games with limsup and liminf objectives can be solved in NP ∩ coNP. },
author = {Krishnendu Chatterjee and Thomas Henzinger},
pages = {32 -- 45},
publisher = {Springer},
title = {{Probabilistic systems with limsup and liminf objectives}},
doi = {10.1007/978-3-642-03092-5_4},
volume = {5489},
year = {2009},
}
@article{9453,
abstract = {Parent-of-origin-specific (imprinted) gene expression is regulated in Arabidopsis thaliana endosperm by cytosine demethylation of the maternal genome mediated by the DNA glycosylase DEMETER, but the extent of the methylation changes is not known. Here, we show that virtually the entire endosperm genome is demethylated, coupled with extensive local non-CG hypermethylation of small interfering RNA–targeted sequences. Mutation of DEMETER partially restores endosperm CG methylation to levels found in other tissues, indicating that CG demethylation is specific to maternal sequences. Endosperm demethylation is accompanied by CHH hypermethylation of embryo transposable elements. Our findings demonstrate extensive reconfiguration of the endosperm methylation landscape that likely reinforces transposon silencing in the embryo.},
author = {Hsieh, Tzung-Fu and Ibarra, Christian A. and Silva, Pedro and Zemach, Assaf and Eshed-Williams, Leor and Fischer, Robert L. and ZILBERMAN, Daniel},
issn = {1095-9203},
journal = {Science},
keywords = {Multidisciplinary},
number = {5933},
pages = {1451--1454},
publisher = {American Association for the Advancement of Science},
title = {{Genome-wide demethylation of Arabidopsis endosperm}},
doi = {10.1126/science.1172417},
volume = {324},
year = {2009},
}
@inproceedings{2331,
abstract = {We present a review of recent work on the mathematical aspects of the BCS gap equation, covering our results of Ref. 9 as well our recent joint work with Hamza and Solovej and with Frank and Naboko, respectively. In addition, we mention some related new results.},
author = {Hainzl, Christian and Robert Seiringer},
pages = {117 -- 136},
publisher = {World Scientific Publishing},
title = {{ Spectral properties of the BCS gap equation of superfluidity}},
doi = {10.1142/9789812832382_0009},
year = {2008},
}
@inproceedings{2332,
abstract = {We present a rigorous proof of the appearance of quantized vortices in dilute trapped Bose gases with repulsive two-body interactions subject to rotation, which was obtained recently in joint work with Elliott Lieb.14 Starting from the many-body Schrödinger equation, we show that the ground state of such gases is, in a suitable limit, well described by the nonlinear Gross-Pitaevskii equation. In the case of axially symmetric traps, our results show that the appearance of quantized vortices causes spontaneous symmetry breaking in the ground state.},
author = {Robert Seiringer},
pages = {241 -- 254},
publisher = {World Scientific Publishing},
title = {{Vortices and Spontaneous Symmetry Breaking in Rotating Bose Gases}},
doi = {10.1142/9789812832382_0017},
year = {2008},
}
@article{2374,
abstract = {A lower bound is derived on the free energy (per unit volume) of a homogeneous Bose gas at density Q and temperature T. In the dilute regime, i.e., when a3 1, where a denotes the scattering length of the pair-interaction potential, our bound differs to leading order from the expression for non-interacting particles by the term 4πa(2 2}-[ - c]2+). Here, c(T) denotes the critical density for Bose-Einstein condensation (for the non-interacting gas), and [ · ]+ = max{ ·, 0} denotes the positive part. Our bound is uniform in the temperature up to temperatures of the order of the critical temperature, i.e., T ~ 2/3 or smaller. One of the key ingredients in the proof is the use of coherent states to extend the method introduced in [17] for estimating correlations to temperatures below the critical one.},
author = {Robert Seiringer},
journal = {Communications in Mathematical Physics},
number = {3},
pages = {595 -- 636},
publisher = {Springer},
title = {{Free energy of a dilute Bose gas: Lower bound}},
doi = {10.1007/s00220-008-0428-2},
volume = {279},
year = {2008},
}
@article{2376,
abstract = {We derive upper and lower bounds on the critical temperature Tc and the energy gap Ξ (at zero temperature) for the BCS gap equation, describing spin- 1 2 fermions interacting via a local two-body interaction potential λV(x). At weak coupling λ 1 and under appropriate assumptions on V(x), our bounds show that Tc ∼A exp(-B/λ) and Ξ∼C exp(-B/λ) for some explicit coefficients A, B, and C depending on the interaction V(x) and the chemical potential μ. The ratio A/C turns out to be a universal constant, independent of both V(x) and μ. Our analysis is valid for any μ; for small μ, or low density, our formulas reduce to well-known expressions involving the scattering length of V(x).},
author = {Hainzl, Christian and Robert Seiringer},
journal = {Physical Review B - Condensed Matter and Materials Physics},
number = {18},
publisher = {American Physical Society},
title = {{Critical temperature and energy gap for the BCS equation}},
doi = {10.1103/PhysRevB.77.184517},
volume = {77},
year = {2008},
}
@article{2377,
abstract = {We prove that the critical temperature for the BCS gap equation is given by T c = μ ( 8\π e γ-2+ o(1)) e π/(2μa) in the low density limit μ→ 0, with γ denoting Euler's constant. The formula holds for a suitable class of interaction potentials with negative scattering length a in the absence of bound states.},
author = {Hainzl, Christian and Robert Seiringer},
journal = {Letters in Mathematical Physics},
number = {2-3},
pages = {99 -- 107},
publisher = {Springer},
title = {{The BCS critical temperature for potentials with negative scattering length}},
doi = {10.1007/s11005-008-0242-y},
volume = {84},
year = {2008},
}
@article{2378,
abstract = {We derive a lower bound on the ground state energy of the Hubbard model for given value of the total spin. In combination with the upper bound derived previously by Giuliani (J. Math. Phys. 48:023302, [2007]), our result proves that in the low density limit the leading order correction compared to the ground state energy of a non-interacting lattice Fermi gas is given by 8πaσ uσ d , where σ u(d) denotes the density of the spin-up (down) particles, and a is the scattering length of the contact interaction potential. This result extends previous work on the corresponding continuum model to the lattice case.},
author = {Robert Seiringer and Yin, Jun},
journal = {Journal of Statistical Physics},
number = {6},
pages = {1139 -- 1154},
publisher = {Springer},
title = {{Ground state energy of the low density hubbard model}},
doi = {10.1007/s10955-008-9527-x},
volume = {131},
year = {2008},
}
@article{2379,
author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer},
journal = {Journal of the American Mathematical Society},
number = {4},
pages = {925 -- 950},
publisher = {American Mathematical Society},
title = {{Hardy-Lieb-Thirring inequalities for fractional Schrödinger operators}},
doi = {10.1090/S0894-0347-07-00582-6},
volume = {21},
year = {2008},
}