[{"type":"journal_article","abstract":[{"lang":"eng","text":"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."}],"publist_id":"5042","issue":"1","title":"A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow","publication_status":"published","status":"public","publisher":"Elsevier","intvolume":" 106","department":[{"_id":"BjHo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2030","year":"2015","date_updated":"2021-01-12T06:54:51Z","date_created":"2018-12-11T11:55:18Z","volume":106,"oa_version":"Preprint","author":[{"id":"374A3F1A-F248-11E8-B48F-1D18A9856A87","first_name":"Liang","last_name":"Shi","full_name":"Shi, Liang"},{"full_name":"Rampp, Markus","last_name":"Rampp","first_name":"Markus"},{"id":"3A374330-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2057-2754","first_name":"Björn","last_name":"Hof","full_name":"Hof, Björn"},{"full_name":"Avila, Marc","first_name":"Marc","last_name":"Avila"}],"scopus_import":1,"month":"01","day":"01","quality_controlled":"1","page":"1 - 11","publication":"Computers and Fluids","oa":1,"citation":{"ista":"Shi L, Rampp M, Hof B, Avila M. 2015. A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. Computers and Fluids. 106(1), 1–11.","ieee":"L. Shi, M. Rampp, B. Hof, and M. Avila, “A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow,” Computers and Fluids, vol. 106, no. 1. Elsevier, pp. 1–11, 2015.","apa":"Shi, L., Rampp, M., Hof, B., & Avila, M. (2015). A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. Computers and Fluids. Elsevier. https://doi.org/10.1016/j.compfluid.2014.09.021","ama":"Shi L, Rampp M, Hof B, Avila M. A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow. Computers and Fluids. 2015;106(1):1-11. doi:10.1016/j.compfluid.2014.09.021","chicago":"Shi, Liang, Markus Rampp, Björn Hof, and Marc Avila. “A Hybrid MPI-OpenMP Parallel Implementation for Pseudospectral Simulations with Application to Taylor-Couette Flow.” Computers and Fluids. Elsevier, 2015. https://doi.org/10.1016/j.compfluid.2014.09.021.","mla":"Shi, Liang, et al. “A Hybrid MPI-OpenMP Parallel Implementation for Pseudospectral Simulations with Application to Taylor-Couette Flow.” Computers and Fluids, vol. 106, no. 1, Elsevier, 2015, pp. 1–11, doi:10.1016/j.compfluid.2014.09.021.","short":"L. Shi, M. Rampp, B. Hof, M. Avila, Computers and Fluids 106 (2015) 1–11."},"main_file_link":[{"url":"http://arxiv.org/abs/1311.2481","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1016/j.compfluid.2014.09.021","date_published":"2015-01-01T00:00:00Z"},{"citation":{"ista":"Edelsbrunner H, Jablonski G, Mrozek M. 2015. The persistent homology of a self-map. Foundations of Computational Mathematics. 15(5), 1213–1244.","apa":"Edelsbrunner, H., Jablonski, G., & Mrozek, M. (2015). The persistent homology of a self-map. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-014-9223-y","ieee":"H. Edelsbrunner, G. Jablonski, and M. Mrozek, “The persistent homology of a self-map,” Foundations of Computational Mathematics, vol. 15, no. 5. Springer, pp. 1213–1244, 2015.","ama":"Edelsbrunner H, Jablonski G, Mrozek M. The persistent homology of a self-map. Foundations of Computational Mathematics. 2015;15(5):1213-1244. doi:10.1007/s10208-014-9223-y","chicago":"Edelsbrunner, Herbert, Grzegorz Jablonski, and Marian Mrozek. “The Persistent Homology of a Self-Map.” Foundations of Computational Mathematics. Springer, 2015. https://doi.org/10.1007/s10208-014-9223-y.","mla":"Edelsbrunner, Herbert, et al. “The Persistent Homology of a Self-Map.” Foundations of Computational Mathematics, vol. 15, no. 5, Springer, 2015, pp. 1213–44, doi:10.1007/s10208-014-9223-y.","short":"H. Edelsbrunner, G. Jablonski, M. Mrozek, Foundations of Computational Mathematics 15 (2015) 1213–1244."},"publication":"Foundations of Computational Mathematics","page":"1213 - 1244","date_published":"2015-10-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01","_id":"2035","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 15","title":"The persistent homology of a self-map","ddc":["000"],"status":"public","pubrep_id":"486","oa_version":"Published Version","file":[{"date_created":"2018-12-12T10:08:10Z","date_updated":"2020-07-14T12:45:26Z","checksum":"3566f3a8b0c1bc550e62914a88c584ff","relation":"main_file","file_id":"4670","file_size":1317546,"content_type":"application/pdf","creator":"system","file_name":"IST-2016-486-v1+1_s10208-014-9223-y.pdf","access_level":"open_access"}],"type":"journal_article","issue":"5","abstract":[{"text":"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.\r\n","lang":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"project":[{"_id":"255D761E-B435-11E9-9278-68D0E5697425","grant_number":"318493","name":"Topological Complex Systems","call_identifier":"FP7"}],"quality_controlled":"1","doi":"10.1007/s10208-014-9223-y","language":[{"iso":"eng"}],"month":"10","acknowledgement":"This research is partially supported by the Toposys project FP7-ICT-318493-STREP, by ESF under the ACAT Research Network Programme, by the Russian Government under mega project 11.G34.31.0053, and by the Polish National Science Center under Grant No. N201 419639.","year":"2015","publisher":"Springer","department":[{"_id":"HeEd"}],"publication_status":"published","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Jablonski, Grzegorz","id":"4483EF78-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3536-9866","first_name":"Grzegorz","last_name":"Jablonski"},{"full_name":"Mrozek, Marian","last_name":"Mrozek","first_name":"Marian"}],"volume":15,"date_created":"2018-12-11T11:55:20Z","date_updated":"2021-01-12T06:54:53Z","publist_id":"5022","ec_funded":1,"file_date_updated":"2020-07-14T12:45:26Z","license":"https://creativecommons.org/licenses/by/4.0/"},{"day":"01","scopus_import":1,"date_published":"2015-01-01T00:00:00Z","page":"52 - 59","publication":" Information Processing Letters","citation":{"ista":"Bérard B, Chatterjee K, Sznajder N. 2015. Probabilistic opacity for Markov decision processes. Information Processing Letters. 115(1), 52–59.","ieee":"B. Bérard, K. Chatterjee, and N. Sznajder, “Probabilistic opacity for Markov decision processes,” Information Processing Letters, vol. 115, no. 1. Elsevier, pp. 52–59, 2015.","apa":"Bérard, B., Chatterjee, K., & Sznajder, N. (2015). Probabilistic opacity for Markov decision processes. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2014.09.001","ama":"Bérard B, Chatterjee K, Sznajder N. Probabilistic opacity for Markov decision processes. Information Processing Letters. 2015;115(1):52-59. doi:10.1016/j.ipl.2014.09.001","chicago":"Bérard, Béatrice, Krishnendu Chatterjee, and Nathalie Sznajder. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters. Elsevier, 2015. https://doi.org/10.1016/j.ipl.2014.09.001.","mla":"Bérard, Béatrice, et al. “Probabilistic Opacity for Markov Decision Processes.” Information Processing Letters, vol. 115, no. 1, Elsevier, 2015, pp. 52–59, doi:10.1016/j.ipl.2014.09.001.","short":"B. Bérard, K. Chatterjee, N. Sznajder, Information Processing Letters 115 (2015) 52–59."},"abstract":[{"text":"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.","lang":"eng"}],"issue":"1","type":"journal_article","oa_version":"Preprint","status":"public","title":"Probabilistic opacity for Markov decision processes","intvolume":" 115","_id":"2034","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"01","language":[{"iso":"eng"}],"doi":"10.1016/j.ipl.2014.09.001","quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","call_identifier":"FWF"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"main_file_link":[{"url":"http://arxiv.org/abs/1407.4225","open_access":"1"}],"oa":1,"ec_funded":1,"publist_id":"5025","date_updated":"2021-01-12T06:54:52Z","date_created":"2018-12-11T11:55:20Z","volume":115,"author":[{"last_name":"Bérard","first_name":"Béatrice","full_name":"Bérard, Béatrice"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"first_name":"Nathalie","last_name":"Sznajder","full_name":"Sznajder, Nathalie"}],"publication_status":"published","publisher":"Elsevier","department":[{"_id":"KrCh"}],"year":"2015"},{"date_published":"2015-02-01T00:00:00Z","doi":"10.1007/s00205-014-0781-6","language":[{"iso":"eng"}],"publication":"Archive for Rational Mechanics and Analysis","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1402.1153"}],"citation":{"chicago":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” Archive for Rational Mechanics and Analysis. Springer, 2015. https://doi.org/10.1007/s00205-014-0781-6.","mla":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” Archive for Rational Mechanics and Analysis, vol. 215, no. 2, Springer, 2015, pp. 381–417, doi:10.1007/s00205-014-0781-6.","short":"P. Nam, R. Seiringer, Archive for Rational Mechanics and Analysis 215 (2015) 381–417.","ista":"Nam P, Seiringer R. 2015. Collective excitations of Bose gases in the mean-field regime. Archive for Rational Mechanics and Analysis. 215(2), 381–417.","ieee":"P. Nam and R. Seiringer, “Collective excitations of Bose gases in the mean-field regime,” Archive for Rational Mechanics and Analysis, vol. 215, no. 2. Springer, pp. 381–417, 2015.","apa":"Nam, P., & Seiringer, R. (2015). Collective excitations of Bose gases in the mean-field regime. Archive for Rational Mechanics and Analysis. Springer. https://doi.org/10.1007/s00205-014-0781-6","ama":"Nam P, Seiringer R. Collective excitations of Bose gases in the mean-field regime. Archive for Rational Mechanics and Analysis. 2015;215(2):381-417. doi:10.1007/s00205-014-0781-6"},"oa":1,"quality_controlled":"1","page":"381 - 417","month":"02","day":"01","scopus_import":1,"author":[{"full_name":"Nam, Phan","id":"404092F4-F248-11E8-B48F-1D18A9856A87","first_name":"Phan","last_name":"Nam"},{"full_name":"Seiringer, Robert","last_name":"Seiringer","first_name":"Robert","orcid":"0000-0002-6781-0521","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2021-01-12T06:55:13Z","date_created":"2018-12-11T11:55:37Z","volume":215,"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2085","year":"2015","status":"public","title":"Collective excitations of Bose gases in the mean-field regime","publication_status":"published","publisher":"Springer","department":[{"_id":"RoSe"}],"intvolume":" 215","abstract":[{"lang":"eng","text":"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. "}],"issue":"2","publist_id":"4951","type":"journal_article"},{"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1309.5106"}],"oa":1,"citation":{"ista":"Erdös L, Knowles A. 2015. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. Communications in Mathematical Physics. 333(3), 1365–1416.","apa":"Erdös, L., & Knowles, A. (2015). The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. Communications in Mathematical Physics. Springer. https://doi.org/10.1007/s00220-014-2119-5","ieee":"L. Erdös and A. Knowles, “The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case,” Communications in Mathematical Physics, vol. 333, no. 3. Springer, pp. 1365–1416, 2015.","ama":"Erdös L, Knowles A. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. Communications in Mathematical Physics. 2015;333(3):1365-1416. doi:10.1007/s00220-014-2119-5","chicago":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” Communications in Mathematical Physics. Springer, 2015. https://doi.org/10.1007/s00220-014-2119-5.","mla":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” Communications in Mathematical Physics, vol. 333, no. 3, Springer, 2015, pp. 1365–416, doi:10.1007/s00220-014-2119-5.","short":"L. Erdös, A. Knowles, Communications in Mathematical Physics 333 (2015) 1365–1416."},"publication":"Communications in Mathematical Physics","page":"1365 - 1416","quality_controlled":"1","date_published":"2015-02-01T00:00:00Z","doi":"10.1007/s00220-014-2119-5","language":[{"iso":"eng"}],"scopus_import":1,"day":"01","month":"02","_id":"2166","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2015","intvolume":" 333","publisher":"Springer","department":[{"_id":"LaEr"}],"status":"public","publication_status":"published","title":"The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case","author":[{"orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","first_name":"László","full_name":"Erdös, László"},{"first_name":"Antti","last_name":"Knowles","full_name":"Knowles, Antti"}],"volume":333,"oa_version":"Preprint","date_updated":"2021-01-12T06:55:43Z","date_created":"2018-12-11T11:56:05Z","type":"journal_article","publist_id":"4818","issue":"3","abstract":[{"lang":"eng","text":"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). "}]},{"pubrep_id":"390","oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:45:17Z","date_created":"2018-12-12T10:11:27Z","checksum":"7370e164d0a731f442424a92669efc34","file_id":"4881","relation":"main_file","creator":"system","file_size":380203,"content_type":"application/pdf","file_name":"IST-2015-390-v1+1_1502.07639.pdf","access_level":"open_access"}],"_id":"1832","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 11","title":"Aspect-oriented linearizability proofs","status":"public","ddc":["000"],"issue":"1","abstract":[{"text":"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. ","lang":"eng"}],"type":"journal_article","date_published":"2015-04-01T00:00:00Z","citation":{"short":"S. Chakraborty, T.A. Henzinger, A. Sezgin, V. Vafeiadis, Logical Methods in Computer Science 11 (2015).","mla":"Chakraborty, Soham, et al. “Aspect-Oriented Linearizability Proofs.” Logical Methods in Computer Science, vol. 11, no. 1, 20, International Federation of Computational Logic, 2015, doi:10.2168/LMCS-11(1:20)2015.","chicago":"Chakraborty, Soham, Thomas A Henzinger, Ali Sezgin, and Viktor Vafeiadis. “Aspect-Oriented Linearizability Proofs.” Logical Methods in Computer Science. International Federation of Computational Logic, 2015. https://doi.org/10.2168/LMCS-11(1:20)2015.","ama":"Chakraborty S, Henzinger TA, Sezgin A, Vafeiadis V. Aspect-oriented linearizability proofs. Logical Methods in Computer Science. 2015;11(1). doi:10.2168/LMCS-11(1:20)2015","ieee":"S. Chakraborty, T. A. Henzinger, A. Sezgin, and V. Vafeiadis, “Aspect-oriented linearizability proofs,” Logical Methods in Computer Science, vol. 11, no. 1. International Federation of Computational Logic, 2015.","apa":"Chakraborty, S., Henzinger, T. A., Sezgin, A., & Vafeiadis, V. (2015). Aspect-oriented linearizability proofs. Logical Methods in Computer Science. International Federation of Computational Logic. https://doi.org/10.2168/LMCS-11(1:20)2015","ista":"Chakraborty S, Henzinger TA, Sezgin A, Vafeiadis V. 2015. Aspect-oriented linearizability proofs. Logical Methods in Computer Science. 11(1), 20."},"publication":"Logical Methods in Computer Science","article_type":"original","has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"2328"}]},"author":[{"full_name":"Chakraborty, Soham","first_name":"Soham","last_name":"Chakraborty"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"first_name":"Ali","last_name":"Sezgin","full_name":"Sezgin, Ali"},{"full_name":"Vafeiadis, Viktor","first_name":"Viktor","last_name":"Vafeiadis"}],"volume":11,"date_updated":"2023-02-23T10:38:13Z","date_created":"2018-12-11T11:54:15Z","year":"2015","publisher":"International Federation of Computational Logic","department":[{"_id":"ToHe"}],"publication_status":"published","ec_funded":1,"publist_id":"5271","file_date_updated":"2020-07-14T12:45:17Z","license":"https://creativecommons.org/licenses/by-nd/4.0/","article_number":"20","doi":"10.2168/LMCS-11(1:20)2015","language":[{"iso":"eng"}],"tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling"}],"quality_controlled":"1","month":"04"},{"publist_id":"4673","date_updated":"2023-02-23T10:46:30Z","date_created":"2018-12-11T11:56:41Z","volume":44,"author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Thapper","first_name":"Johan","full_name":"Thapper, Johan"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2518"}]},"publication_status":"published","department":[{"_id":"VlKo"}],"publisher":"SIAM","year":"2015","month":"02","language":[{"iso":"eng"}],"doi":"10.1137/130945648","quality_controlled":"1","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1311.4219","open_access":"1"}],"external_id":{"arxiv":["1311.4219"]},"abstract":[{"lang":"eng","text":"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).\r\nOur 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.\r\nUsing 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. "}],"issue":"1","type":"journal_article","oa_version":"Preprint","title":"The power of linear programming for general-valued CSPs","status":"public","intvolume":" 44","_id":"2271","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"01","scopus_import":1,"date_published":"2015-02-01T00:00:00Z","page":"1 - 36","publication":"SIAM Journal on Computing","citation":{"mla":"Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:10.1137/130945648.","short":"V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.","chicago":"Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2015. https://doi.org/10.1137/130945648.","ama":"Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 2015;44(1):1-36. doi:10.1137/130945648","ista":"Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36.","apa":"Kolmogorov, V., Thapper, J., & Živný, S. (2015). The power of linear programming for general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/130945648","ieee":"V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” SIAM Journal on Computing, vol. 44, no. 1. SIAM, pp. 1–36, 2015."}},{"day":"10","month":"07","date_published":"2015-07-10T00:00:00Z","doi":"10.1515/forum-2013-6024","quality_controlled":0,"page":"2025 - 2050","publication":"Forum Mathematicum","oa":1,"citation":{"ieee":"T. D. Browning and R. Munshi, “Pairs of diagonal quadratic forms and linear correlations among sums of two squares,” Forum Mathematicum, vol. 27, no. 4. Walter de Gruyter GmbH, pp. 2025–2050, 2015.","apa":"Browning, T. D., & Munshi, R. (2015). Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. Walter de Gruyter GmbH. https://doi.org/10.1515/forum-2013-6024","ista":"Browning TD, Munshi R. 2015. Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. 27(4), 2025–2050.","ama":"Browning TD, Munshi R. Pairs of diagonal quadratic forms and linear correlations among sums of two squares. Forum Mathematicum. 2015;27(4):2025-2050. doi:10.1515/forum-2013-6024","chicago":"Browning, Timothy D, and Ritabrata Munshi. “Pairs of Diagonal Quadratic Forms and Linear Correlations among Sums of Two Squares.” Forum Mathematicum. Walter de Gruyter GmbH, 2015. https://doi.org/10.1515/forum-2013-6024.","short":"T.D. Browning, R. Munshi, Forum Mathematicum 27 (2015) 2025–2050.","mla":"Browning, Timothy D., and Ritabrata Munshi. “Pairs of Diagonal Quadratic Forms and Linear Correlations among Sums of Two Squares.” Forum Mathematicum, vol. 27, no. 4, Walter de Gruyter GmbH, 2015, pp. 2025–50, doi:10.1515/forum-2013-6024."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1302.2434"}],"extern":1,"abstract":[{"lang":"eng","text":"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."}],"issue":"4","publist_id":"7645","type":"journal_article","date_created":"2018-12-11T11:45:28Z","date_updated":"2021-01-12T06:58:18Z","volume":27,"author":[{"full_name":"Timothy Browning","orcid":"0000-0002-8314-0177","id":"35827D50-F248-11E8-B48F-1D18A9856A87","last_name":"Browning","first_name":"Timothy D"},{"first_name":"Ritabrata","last_name":"Munshi","full_name":"Munshi, Ritabrata"}],"publication_status":"published","title":"Pairs of diagonal quadratic forms and linear correlations among sums of two squares","status":"public","intvolume":" 27","publisher":"Walter de Gruyter GmbH","year":"2015","_id":"257","acknowledgement":"While working on this paper the first author was supported by ERC grant 306457 and the second author was supported by SwarnaJayanti Fellowship 2011–12, DST, Government of India."},{"date_created":"2018-12-11T11:45:28Z","date_updated":"2021-01-12T06:58:22Z","oa_version":"None","author":[{"full_name":"Browning, Timothy D","first_name":"Timothy D","last_name":"Browning","id":"35827D50-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8314-0177"}],"title":"A survey of applications of the circle method to rational points","status":"public","publication_status":"published","publisher":"Cambridge University Press","_id":"258","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","abstract":[{"text":"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.","lang":"eng"}],"publist_id":"7644","type":"book_chapter","language":[{"iso":"eng"}],"doi":"10.1017/CBO9781316106877.009","date_published":"2015-08-01T00:00:00Z","quality_controlled":"1","page":"89 - 113","publication":"Arithmetic and Geometry","citation":{"ama":"Browning TD. A survey of applications of the circle method to rational points. In: Arithmetic and Geometry. Cambridge University Press; 2015:89-113. doi:10.1017/CBO9781316106877.009","ista":"Browning TD. 2015.A survey of applications of the circle method to rational points. In: Arithmetic and Geometry. , 89–113.","apa":"Browning, T. D. (2015). A survey of applications of the circle method to rational points. In Arithmetic and Geometry (pp. 89–113). Cambridge University Press. https://doi.org/10.1017/CBO9781316106877.009","ieee":"T. D. Browning, “A survey of applications of the circle method to rational points,” in Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113.","mla":"Browning, Timothy D. “A Survey of Applications of the Circle Method to Rational Points.” Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113, doi:10.1017/CBO9781316106877.009.","short":"T.D. Browning, in:, Arithmetic and Geometry, Cambridge University Press, 2015, pp. 89–113.","chicago":"Browning, Timothy D. “A Survey of Applications of the Circle Method to Rational Points.” In Arithmetic and Geometry, 89–113. Cambridge University Press, 2015. https://doi.org/10.1017/CBO9781316106877.009."},"day":"01","month":"08"},{"page":"671 - 732","quality_controlled":0,"citation":{"ista":"Browning TD, Vishe P. 2015. Rational points on cubic hypersurfaces over F_q(t) . Geometric and Functional Analysis. 25(3), 671–732.","apa":"Browning, T. D., & Vishe, P. (2015). Rational points on cubic hypersurfaces over F_q(t) . Geometric and Functional Analysis. Birkhäuser. https://doi.org/10.1007/s00039-015-0328-5","ieee":"T. D. Browning and P. Vishe, “Rational points on cubic hypersurfaces over F_q(t) ,” Geometric and Functional Analysis, vol. 25, no. 3. Birkhäuser, pp. 671–732, 2015.","ama":"Browning TD, Vishe P. Rational points on cubic hypersurfaces over F_q(t) . Geometric and Functional Analysis. 2015;25(3):671-732. doi:10.1007/s00039-015-0328-5","chicago":"Browning, Timothy D, and Pankaj Vishe. “Rational Points on Cubic Hypersurfaces over F_q(T) .” Geometric and Functional Analysis. Birkhäuser, 2015. https://doi.org/10.1007/s00039-015-0328-5.","mla":"Browning, Timothy D., and Pankaj Vishe. “Rational Points on Cubic Hypersurfaces over F_q(T) .” Geometric and Functional Analysis, vol. 25, no. 3, Birkhäuser, 2015, pp. 671–732, doi:10.1007/s00039-015-0328-5.","short":"T.D. Browning, P. Vishe, Geometric and Functional Analysis 25 (2015) 671–732."},"publication":"Geometric and Functional Analysis","date_published":"2015-06-11T00:00:00Z","doi":"10.1007/s00039-015-0328-5","month":"06","day":"11","publisher":"Birkhäuser","intvolume":" 25","publication_status":"published","title":"Rational points on cubic hypersurfaces over F_q(t) ","status":"public","acknowledgement":"EP/J018260/1\tEngineering and Physical Sciences Research Council EPSRC","_id":"259","year":"2015","volume":25,"date_updated":"2021-01-12T06:58:25Z","date_created":"2018-12-11T11:45:29Z","author":[{"full_name":"Timothy Browning","orcid":"0000-0002-8314-0177","id":"35827D50-F248-11E8-B48F-1D18A9856A87","last_name":"Browning","first_name":"Timothy D"},{"last_name":"Vishe","first_name":"Pankaj","full_name":"Vishe, Pankaj"}],"type":"journal_article","extern":1,"publist_id":"7643","issue":"3","abstract":[{"lang":"eng","text":"The Hasse principle and weak approximation is established for non-singular cubic hypersurfaces X over the function field "}]}]