TY - JOUR AB - We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials. AU - Noren, Patrik ID - 1997 IS - May-June JF - Journal of Symbolic Computation TI - The three-state toric homogeneous Markov chain model has Markov degree two VL - 68/Part 2 ER - TY - JOUR AB - The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package. AU - Klimova, Anna AU - Rudas, Tamás ID - 2008 IS - 3 JF - Scandinavian Journal of Statistics TI - Iterative scaling in curved exponential families VL - 42 ER - TY - JOUR AB - The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data. AU - Hein, Nicolas AU - Hillar, Christopher AU - Martin Del Campo Sanchez, Abraham AU - Sottile, Frank AU - Teitler, Zach ID - 2006 IS - 3 JF - Experimental Mathematics TI - The monotone secant conjecture in the real Schubert calculus VL - 24 ER - TY - JOUR AB - The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association. AU - Klimova, Anna AU - Uhler, Caroline AU - Rudas, Tamás ID - 2014 IS - 7 JF - Computational Statistics & Data Analysis TI - Faithfulness and learning hypergraphs from discrete distributions VL - 87 ER - TY - JOUR AB - Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins. AU - Kawada, Daiki AU - Kobayashi, Hiromu AU - Tomita, Tsuyoshi AU - Nakata, Eisuke AU - Nagano, Makoto AU - Siekhaus, Daria E AU - Toshima, Junko AU - Toshimaa, Jiro ID - 2025 IS - 1 JF - Biochimica et Biophysica Acta - Molecular Cell Research TI - The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins VL - 1853 ER - TY - JOUR AB - A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes. AU - Shi, Liang AU - Rampp, Markus AU - Hof, Björn AU - Avila, Marc ID - 2030 IS - 1 JF - Computers and Fluids TI - A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow VL - 106 ER - TY - JOUR AB - Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility. AU - Edelsbrunner, Herbert AU - Jablonski, Grzegorz AU - Mrozek, Marian ID - 2035 IS - 5 JF - Foundations of Computational Mathematics TI - The persistent homology of a self-map VL - 15 ER - TY - JOUR AB - Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers. AU - Bérard, Béatrice AU - Chatterjee, Krishnendu AU - Sznajder, Nathalie ID - 2034 IS - 1 JF - Information Processing Letters TI - Probabilistic opacity for Markov decision processes VL - 115 ER - TY - JOUR AB - We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer. AU - Nam, Phan AU - Seiringer, Robert ID - 2085 IS - 2 JF - Archive for Rational Mechanics and Analysis TI - Collective excitations of Bose gases in the mean-field regime VL - 215 ER - TY - JOUR AB - We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014). AU - Erdös, László AU - Knowles, Antti ID - 2166 IS - 3 JF - Communications in Mathematical Physics TI - The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case VL - 333 ER - TY - JOUR AB - Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof. AU - Chakraborty, Soham AU - Henzinger, Thomas A AU - Sezgin, Ali AU - Vafeiadis, Viktor ID - 1832 IS - 1 JF - Logical Methods in Computer Science TI - Aspect-oriented linearizability proofs VL - 11 ER - TY - JOUR AB - A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2. Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees. AU - Kolmogorov, Vladimir AU - Thapper, Johan AU - Živný, Stanislav ID - 2271 IS - 1 JF - SIAM Journal on Computing TI - The power of linear programming for general-valued CSPs VL - 44 ER - TY - JOUR AB - For suitable pairs of diagonal quadratic forms in eight variables we use the circle method to investigate the density of simultaneous integer solutions and relate this to the problem of estimating linear correlations among sums of two squares. AU - Timothy Browning AU - Munshi, Ritabrata ID - 257 IS - 4 JF - Forum Mathematicum TI - Pairs of diagonal quadratic forms and linear correlations among sums of two squares VL - 27 ER - TY - CHAP AB - Given a number field k and a projective algebraic variety X defined over k, the question of whether X contains a k-rational point is both very natural and very difficult. In the event that the set X(k) of k-rational points is not empty, one can also ask how the points of X(k) are distributed. Are they dense in X under the Zariski topology? Are they dense in the set. AU - Browning, Timothy D ID - 258 T2 - Arithmetic and Geometry TI - A survey of applications of the circle method to rational points ER - TY - JOUR AB - The Hasse principle and weak approximation is established for non-singular cubic hypersurfaces X over the function field AU - Timothy Browning AU - Vishe, Pankaj ID - 259 IS - 3 JF - Geometric and Functional Analysis TI - Rational points on cubic hypersurfaces over F_q(t) VL - 25 ER - TY - JOUR AB - We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability 1 from these vertices. We study for the first time the average-case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average-case running time is linear (as compared to the worst-case linear number of iterations and quadratic time complexity). Second, for the average-case analysis over all MDPs we show that the expected number of iterations is constant and the average-case running time is linear (again as compared to the worst-case linear number of iterations and quadratic time complexity). Finally we also show that when all MDPs are equally likely, the probability that the classical algorithm requires more than a constant number of iterations is exponentially small. AU - Chatterjee, Krishnendu AU - Joglekar, Manas AU - Shah, Nisarg ID - 1598 IS - 3 JF - Theoretical Computer Science TI - Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives VL - 573 ER - TY - JOUR AB - We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology H∗(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in double-struck R3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on double-struck S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard. AU - Attali, Dominique AU - Bauer, Ulrich AU - Devillers, Olivier AU - Glisse, Marc AU - Lieutier, André ID - 1805 IS - 8 JF - Computational Geometry: Theory and Applications TI - Homological reconstruction and simplification in R3 VL - 48 ER - TY - JOUR AB - We present a hybrid intercalation battery based on a sodium/magnesium (Na/Mg) dual salt electrolyte, metallic magnesium anode, and a cathode based on FeS2 nanocrystals (NCs). Compared to lithium or sodium, metallic magnesium anode is safer due to dendrite-free electroplating and offers extremely high volumetric (3833 mAh cm-3) and gravimetric capacities (2205 mAh g-1). Na-ion cathodes, FeS2 NCs in the present study, may serve as attractive alternatives to Mg-ion cathodes due to the higher voltage of operation and fast, highly reversible insertion of Na-ions. In this proof-of-concept study, electrochemical cycling of the Na/Mg hybrid battery was characterized by high rate capability, high Coulombic efficiency of 99.8%, and high energy density. In particular, with an average discharge voltage of ∼1.1 V and a cathodic capacity of 189 mAh g-1 at a current of 200 mA g-1, the presented Mg/FeS2 hybrid battery delivers energy densities of up to 210 Wh kg-1, comparable to commercial Li-ion batteries and approximately twice as high as state-of-the-art Mg-ion batteries based on Mo6S8 cathodes. Further significant gains in the energy density are expected from the development of Na/Mg electrolytes with a broader electrochemical stability window. Fully based on Earth-abundant elements, hybrid Na-Mg batteries are highly promising for large-scale stationary energy storage. AU - Walter, Marc AU - Kravchyk, Kostiantyn AU - Ibáñez, Maria AU - Kovalenko, Maksym ID - 333 IS - 21 JF - Chemistry of Materials TI - Efficient and inexpensive sodium magnesium hybrid battery VL - 27 ER - TY - JOUR AB - A simple and effective method to introduce precise amounts of doping in nanomaterials produced from the bottom-up assembly of colloidal nanoparticles (NPs) is described. The procedure takes advantage of a ligand displacement step to incorporate controlled concentrations of halide ions while removing carboxylic acids from the NP surface. Upon consolidation of the NPs into dense pellets, halide ions diffuse within the crystal structure, doping the anion sublattice and achieving n-type electrical doping. Through the characterization of the thermoelectric properties of nanocrystalline PbS, we demonstrate this strategy to be effective to control charge transport properties on thermoelectric nanomaterials assembled from NP building blocks. This approach is subsequently extended to PbTexSe1-x@PbS core-shell NPs, where a significant enhancement of the thermoelectric figure of merit is achieved. AU - Ibáñez, Maria AU - Korkosz, Rachel AU - Luo, Zhishan AU - Riba, Pau AU - Cadavid, Doris AU - Ortega, Silvia AU - Cabot, Andreu AU - Kanatzidis, Mercouri ID - 354 IS - 12 JF - Journal of the American Chemical Society TI - Electron doping in bottom up engineered thermoelectric nanomaterials through HCl mediated ligand displacement VL - 137 ER - TY - JOUR AB - A cation exchange-based route was used to produce Cu2ZnSnS4 (CZTS)-Ag2S nanoparticles with controlled composition. We report a detailed study of the formation of such CZTS-Ag2S nanoheterostructures and of their photocatalytic properties. When compared to pure CZTS, the use of nanoscale p-n heterostructures as light absorbers for photocatalytic water splitting provides superior photocurrents. We associate this experimental fact to a higher separation efficiency of the photogenerated electron-hole pairs. We believe this and other type-II nanoheterostructures will open the door to the use of CZTS, with excellent light absorption properties and made of abundant and environmental friendly elements, to the field of photocatalysis. AU - Yu, Xuelian AU - Liu, Jingjing AU - Genç, Aziz AU - Ibáñez, Maria AU - Luo, Zhishan AU - Shavel, Alexey AU - Arbiol, Jordi AU - Zhang, Guangjin AU - Zhang, Yihe AU - Cabot, Andreu ID - 360 IS - 38 JF - Langmuir TI - Cu2ZnSnS4-Ag2S nanoscale p-n heterostructures as sensitizers for photoelectrochemical water splitting VL - 31 ER -