[{"_id":"6662","type":"journal_article","article_type":"original","date_created":"2019-07-22T13:23:48Z","publication_identifier":{"eissn":["1615-3383"]},"status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.05932"}],"issue":"3","month":"06","volume":19,"language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","author":[{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Montanari, Andrea","first_name":"Andrea","last_name":"Montanari"}],"publication":"Foundations of Computational Mathematics","intvolume":" 19","arxiv":1,"oa":1,"doi":"10.1007/s10208-018-9395-y","page":"703-773","year":"2019","day":"01","abstract":[{"lang":"eng","text":"In phase retrieval, we want to recover an unknown signal đ‘„âˆˆâ„‚đ‘‘ from n quadratic measurements of the form 𝑩𝑖=|⟹𝑎𝑖,đ‘„âŸ©|2+đ‘€đ‘–, where 𝑎𝑖∈ℂ𝑑 are known sensing vectors and đ‘€đ‘– is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator đ‘„^(𝑩) that is positively correlated with the signal đ‘„? We consider the case of Gaussian vectors 𝑎𝑎𝑖. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For đ‘›â‰€đ‘‘âˆ’đ‘œ(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For đ‘›â‰„đ‘‘+𝑜(𝑑), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements 𝑩𝑖 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm."}],"publication_status":"published","title":"Fundamental limits of weak recovery with applications to phase retrieval","publisher":"Springer","date_published":"2019-06-01T00:00:00Z","citation":{"mla":"Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics, vol. 19, no. 3, Springer, 2019, pp. 703–73, doi:10.1007/s10208-018-9395-y.","short":"M. Mondelli, A. Montanari, Foundations of Computational Mathematics 19 (2019) 703–773.","ieee":"M. Mondelli and A. Montanari, “Fundamental limits of weak recovery with applications to phase retrieval,” Foundations of Computational Mathematics, vol. 19, no. 3. Springer, pp. 703–773, 2019.","ama":"Mondelli M, Montanari A. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 2019;19(3):703-773. doi:10.1007/s10208-018-9395-y","ista":"Mondelli M, Montanari A. 2019. Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. 19(3), 703–773.","chicago":"Mondelli, Marco, and Andrea Montanari. “Fundamental Limits of Weak Recovery with Applications to Phase Retrieval.” Foundations of Computational Mathematics. Springer, 2019. https://doi.org/10.1007/s10208-018-9395-y.","apa":"Mondelli, M., & Montanari, A. (2019). Fundamental limits of weak recovery with applications to phase retrieval. Foundations of Computational Mathematics. Springer. https://doi.org/10.1007/s10208-018-9395-y"},"date_updated":"2021-01-12T08:08:28Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1708.05932"]}},{"title":"Construction of polar codes with sublinear complexity","date_published":"2019-05-01T00:00:00Z","publisher":"IEEE","publication_status":"published","abstract":[{"text":"Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by SchĂŒrch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered.","lang":"eng"}],"external_id":{"arxiv":["1612.05295"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791.","mla":"Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.","ama":"Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667","ista":"Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear complexity. IEEE. 65(5), 2782–2791.","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” IEEE. IEEE, 2019. https://doi.org/10.1109/tit.2018.2889667.","apa":"Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar codes with sublinear complexity. IEEE. IEEE. https://doi.org/10.1109/tit.2018.2889667","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019."},"extern":"1","date_updated":"2023-02-23T12:50:20Z","publication":"IEEE","arxiv":1,"intvolume":" 65","related_material":{"record":[{"id":"6729","relation":"earlier_version","status":"public"}]},"doi":"10.1109/tit.2018.2889667","year":"2019","page":"2782-2791","day":"01","oa":1,"volume":65,"language":[{"iso":"eng"}],"issue":"5","month":"05","author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","last_name":"Mondelli","first_name":"Marco"},{"full_name":"Hassani, Hamed","last_name":"Hassani","first_name":"Hamed"},{"full_name":"Urbanke, Rudiger","first_name":"Rudiger","last_name":"Urbanke"}],"oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1612.05295"}],"status":"public","type":"journal_article","_id":"6663","date_created":"2019-07-23T07:32:57Z"},{"oa":1,"doi":"10.1007/s41468-019-00029-8","year":"2019","page":"29–58","day":"01","intvolume":" 3","publication":"Journal of Applied and Computational Topology","department":[{"_id":"HeEd"}],"date_updated":"2023-08-22T12:37:47Z","citation":{"short":"J.-D. Boissonnat, A. Lieutier, M. Wintraecken, Journal of Applied and Computational Topology 3 (2019) 29–58.","mla":"Boissonnat, Jean-Daniel, et al. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology, vol. 3, no. 1–2, Springer Nature, 2019, pp. 29–58, doi:10.1007/s41468-019-00029-8.","ieee":"J.-D. Boissonnat, A. Lieutier, and M. Wintraecken, “The reach, metric distortion, geodesic convexity and the variation of tangent spaces,” Journal of Applied and Computational Topology, vol. 3, no. 1–2. Springer Nature, pp. 29–58, 2019.","ista":"Boissonnat J-D, Lieutier A, Wintraecken M. 2019. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 3(1–2), 29–58.","chicago":"Boissonnat, Jean-Daniel, AndrĂ© Lieutier, and Mathijs Wintraecken. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology. Springer Nature, 2019. https://doi.org/10.1007/s41468-019-00029-8.","ama":"Boissonnat J-D, Lieutier A, Wintraecken M. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 2019;3(1-2):29–58. doi:10.1007/s41468-019-00029-8","apa":"Boissonnat, J.-D., Lieutier, A., & Wintraecken, M. (2019). The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-019-00029-8"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"lang":"eng","text":"In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points."}],"ddc":["000"],"publisher":"Springer Nature","file_date_updated":"2020-07-14T12:47:36Z","date_published":"2019-06-01T00:00:00Z","title":"The reach, metric distortion, geodesic convexity and the variation of tangent spaces","date_created":"2019-07-24T08:37:29Z","article_type":"original","type":"journal_article","_id":"6671","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"status":"public","ec_funded":1,"quality_controlled":"1","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"oa_version":"Published Version","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"first_name":"AndrĂ©","last_name":"Lieutier","full_name":"Lieutier, AndrĂ©"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"has_accepted_license":"1","month":"06","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:47:36Z","date_created":"2019-07-31T08:09:56Z","file_name":"2019_JournAppliedComputTopol_Boissonnat.pdf","relation":"main_file","creator":"dernst","checksum":"a5b244db9f751221409cf09c97ee0935","file_id":"6741","file_size":2215157,"access_level":"open_access"}],"issue":"1-2","language":[{"iso":"eng"}],"volume":3,"article_processing_charge":"Yes (via OA deal)"},{"external_id":{"arxiv":["1703.06487"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","date_updated":"2021-01-12T08:08:30Z","citation":{"apa":"Boissonnat, J.-D., Rouxel-LabbĂ©, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292","chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-LabbĂ©, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.","ista":"Boissonnat J-D, Rouxel-LabbĂ© M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097.","ama":"Boissonnat J-D, Rouxel-LabbĂ© M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292","ieee":"J.-D. Boissonnat, M. Rouxel-LabbĂ©, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019.","mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292.","short":"J.-D. Boissonnat, M. Rouxel-LabbĂ©, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097."},"date_published":"2019-05-21T00:00:00Z","publisher":"Society for Industrial & Applied Mathematics (SIAM)","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","publication_status":"published","abstract":[{"lang":"eng","text":"The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\\mathbb{R}^2$ and on surfaces embedded in $\\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\\mathcal{P}$ in a domain $\\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened."}],"day":"21","year":"2019","page":"1046-1097","doi":"10.1137/17m1152292","oa":1,"arxiv":1,"intvolume":" 48","publication":"SIAM Journal on Computing","author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Rouxel-LabbĂ©, Mael","first_name":"Mael","last_name":"Rouxel-LabbĂ©"},{"orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"volume":48,"month":"05","issue":"3","main_file_link":[{"url":"https://arxiv.org/abs/1703.06487","open_access":"1"}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"status":"public","date_created":"2019-07-24T08:42:12Z","type":"journal_article","_id":"6672"},{"type":"conference","_id":"6673","date_created":"2019-07-24T08:59:36Z","status":"public","publication_identifier":{"isbn":["9781450361842"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.09363"}],"conference":{"start_date":"2019-06-22","end_date":"2019-06-24","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Phoenix, AZ, United States"},"ec_funded":1,"oa_version":"Preprint","quality_controlled":"1","project":[{"call_identifier":"H2020","grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning"}],"author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian"},{"first_name":"Giorgi","last_name":"Nadiradze","orcid":"0000-0001-5634-0731","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","full_name":"Nadiradze, Giorgi"},{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","full_name":"Koval, Nikita","last_name":"Koval","first_name":"Nikita"}],"month":"06","article_processing_charge":"No","language":[{"iso":"eng"}],"oa":1,"day":"01","page":"145-154","doi":"10.1145/3323165.3323201","year":"2019","scopus_import":"1","related_material":{"record":[{"id":"10429","relation":"dissertation_contains","status":"public"}]},"publication":"31st ACM Symposium on Parallelism in Algorithms and Architectures","arxiv":1,"citation":{"ieee":"D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, United States, 2019, pp. 145–154.","ista":"Alistarh D-A, Nadiradze G, Koval N. 2019. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. 31st ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 145–154.","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In 31st ACM Symposium on Parallelism in Algorithms and Architectures, 145–54. ACM Press, 2019. https://doi.org/10.1145/3323165.3323201.","ama":"Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: 31st ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press; 2019:145-154. doi:10.1145/3323165.3323201","apa":"Alistarh, D.-A., Nadiradze, G., & Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In 31st ACM Symposium on Parallelism in Algorithms and Architectures (pp. 145–154). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3323165.3323201","mla":"Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–54, doi:10.1145/3323165.3323201.","short":"D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–154."},"department":[{"_id":"DaAl"}],"date_updated":"2023-09-07T13:31:39Z","external_id":{"isi":["000507618500018"],"arxiv":["2003.09363"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"publication_status":"published","abstract":[{"lang":"eng","text":"Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(Ƃog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers."}],"title":"Efficiency guarantees for parallel incremental algorithms under relaxed schedulers","publisher":"ACM Press","date_published":"2019-06-01T00:00:00Z"},{"scopus_import":"1","related_material":{"record":[{"id":"14364","relation":"later_version","status":"public"}]},"arxiv":1,"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","oa":1,"page":"986-996","day":"01","year":"2019","doi":"10.1145/3313276.3316407","publication_status":"published","abstract":[{"lang":"eng","text":"It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.\r\n\r\nUsing proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≄ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power."}],"isi":1,"date_published":"2019-06-01T00:00:00Z","publisher":"ACM Press","title":"Why extension-based proofs fail","department":[{"_id":"DaAl"}],"date_updated":"2023-12-13T12:28:28Z","citation":{"ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, United States, 2019, pp. 986–996.","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 986–996.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 986–96. ACM Press, 2019. https://doi.org/10.1145/3313276.3316407.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM Press; 2019:986-996. doi:10.1145/3313276.3316407","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2019). Why extension-based proofs fail. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 986–996). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316407","mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–96, doi:10.1145/3313276.3316407.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM Press, 2019, pp. 986–996."},"external_id":{"arxiv":["1811.01421"],"isi":["000523199100089"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"location":"Phoenix, AZ, United States","name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","start_date":"2019-06-23"},"date_created":"2019-07-24T09:13:05Z","_id":"6676","type":"conference","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1811.01421"}],"publication_identifier":{"isbn":["9781450367059"]},"status":"public","month":"06","language":[{"iso":"eng"}],"article_processing_charge":"No","quality_controlled":"1","oa_version":"Preprint","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"Ellen, Faith","last_name":"Ellen","first_name":"Faith"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"},{"last_name":"Zhu","first_name":"Leqi","full_name":"Zhu, Leqi"}]},{"title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","publisher":"ACM Press","date_published":"2019-06-01T00:00:00Z","isi":1,"publication_status":"published","abstract":[{"lang":"eng","text":"The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)."}],"external_id":{"isi":["000523199100100"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.","short":"A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–1114.","ieee":"A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400","ista":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.","ama":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400","chicago":"Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400."},"department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T13:15:55Z","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019","scopus_import":"1","related_material":{"record":[{"relation":"dissertation_contains","id":"7896","status":"public"}]},"year":"2019","day":"01","page":"1103-1114","doi":"10.1145/3313276.3316400","oa":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"month":"06","author":[{"full_name":"Choudhuri, Arka Rai","last_name":"Choudhuri","first_name":"Arka Rai"},{"last_name":"Hubáček","first_name":"Pavel","full_name":"Hubáček, Pavel"},{"last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Rosen","first_name":"Alon","full_name":"Rosen, Alon"},{"first_name":"Guy N.","last_name":"Rothblum","full_name":"Rothblum, Guy N."}],"oa_version":"Preprint","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020"}],"quality_controlled":"1","conference":{"location":"Phoenix, AZ, United States","name":"STOC: Symposium on Theory of Computing","start_date":"2019-06-23","end_date":"2019-06-26"},"ec_funded":1,"status":"public","publication_identifier":{"isbn":["9781450367059"]},"main_file_link":[{"url":"https://eprint.iacr.org/2019/549","open_access":"1"}],"_id":"6677","type":"conference","date_created":"2019-07-24T09:20:53Z"},{"date_created":"2019-07-25T09:08:28Z","type":"journal_article","_id":"6680","publication_identifier":{"eissn":["1558-5646"],"issn":["0014-3820"]},"status":"public","has_accepted_license":"1","month":"09","issue":"9","file":[{"relation":"main_file","file_id":"6881","checksum":"772ce7035965153959b946a1033de1ca","creator":"kschuh","access_level":"open_access","file_size":937573,"content_type":"application/pdf","date_created":"2019-09-17T10:56:27Z","date_updated":"2020-07-14T12:47:37Z","file_name":"2019_Evolution_Sachdeva.pdf"}],"language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","volume":73,"quality_controlled":"1","oa_version":"Published Version","author":[{"id":"42377A0A-F248-11E8-B48F-1D18A9856A87","full_name":"Sachdeva, Himani","last_name":"Sachdeva","first_name":"Himani"}],"related_material":{"record":[{"id":"9802","relation":"research_data","status":"public"}]},"scopus_import":"1","intvolume":" 73","publication":"Evolution","oa":1,"day":"01","year":"2019","page":"1729-1745","doi":"10.1111/evo.13812","abstract":[{"lang":"eng","text":"This paper analyzes how partial selfing in a large source population influences its ability to colonize a new habitat via the introduction of a few founder individuals. Founders experience inbreeding depression due to partially recessive deleterious alleles as well as maladaptation to the new environment due to selection on a large number of additive loci. I first introduce a simplified version of the Inbreeding History Model (Kelly, 2007) in order to characterize mutation‐selection balance in a large, partially selfing source population under selection involving multiple non‐identical loci. I then use individual‐based simulations to study the eco‐evolutionary dynamics of founders establishing in the new habitat under a model of hard selection. The study explores how selfing rate shapes establishment probabilities of founders via effects on both inbreeding depression and adaptability to the new environment, and also distinguishes the effects of selfing on the initial fitness of founders from its effects on the long‐term adaptive response of the populations they found. A high rate of (but not complete) selfing is found to aid establishment over a wide range of parameters, even in the absence of mate limitation. The sensitivity of the results to assumptions about the nature of polygenic selection are discussed."}],"publication_status":"published","ddc":["576"],"isi":1,"date_published":"2019-09-01T00:00:00Z","publisher":"Wiley","file_date_updated":"2020-07-14T12:47:37Z","title":"Effect of partial selfing and polygenic selection on establishment in a new habitat","date_updated":"2023-08-29T06:43:58Z","department":[{"_id":"NiBa"}],"citation":{"mla":"Sachdeva, Himani. “Effect of Partial Selfing and Polygenic Selection on Establishment in a New Habitat.” Evolution, vol. 73, no. 9, Wiley, 2019, pp. 1729–45, doi:10.1111/evo.13812.","short":"H. Sachdeva, Evolution 73 (2019) 1729–1745.","ieee":"H. Sachdeva, “Effect of partial selfing and polygenic selection on establishment in a new habitat,” Evolution, vol. 73, no. 9. Wiley, pp. 1729–1745, 2019.","apa":"Sachdeva, H. (2019). Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. Wiley. https://doi.org/10.1111/evo.13812","chicago":"Sachdeva, Himani. “Effect of Partial Selfing and Polygenic Selection on Establishment in a New Habitat.” Evolution. Wiley, 2019. https://doi.org/10.1111/evo.13812.","ama":"Sachdeva H. Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. 2019;73(9):1729-1745. doi:10.1111/evo.13812","ista":"Sachdeva H. 2019. Effect of partial selfing and polygenic selection on establishment in a new habitat. Evolution. 73(9), 1729–1745."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000481300600001"]}},{"_id":"6681","type":"dissertation","date_created":"2019-07-26T11:14:34Z","status":"public","publication_identifier":{"issn":["2663-337X"]},"file":[{"file_id":"6771","checksum":"3231e7cbfca3b5687366f84f0a57a0c0","creator":"szhechev","access_level":"open_access","file_size":1464227,"relation":"main_file","file_name":"Stephan_Zhechev_thesis.pdf","content_type":"application/pdf","date_created":"2019-08-07T13:02:50Z","date_updated":"2020-07-14T12:47:37Z"},{"date_created":"2019-08-07T13:03:22Z","date_updated":"2020-07-14T12:47:37Z","content_type":"application/octet-stream","file_name":"Stephan_Zhechev_thesis.tex","relation":"source_file","access_level":"closed","file_size":303988,"checksum":"85d65eb27b4377a9e332ee37a70f08b6","file_id":"6772","creator":"szhechev"},{"date_updated":"2020-07-14T12:47:37Z","date_created":"2019-08-07T13:03:34Z","content_type":"application/zip","file_name":"supplementary_material.zip","relation":"supplementary_material","file_size":1087004,"access_level":"closed","creator":"szhechev","checksum":"86b374d264ca2dd53e712728e253ee75","file_id":"6773"}],"month":"08","has_accepted_license":"1","article_processing_charge":"No","language":[{"iso":"eng"}],"oa_version":"Published Version","author":[{"full_name":"Zhechev, Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","last_name":"Zhechev"}],"supervisor":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"related_material":{"record":[{"relation":"part_of_dissertation","id":"6774","status":"public"}]},"oa":1,"doi":"10.15479/AT:ISTA:6681","year":"2019","page":"104","day":"08","ddc":["514"],"publication_status":"published","abstract":[{"lang":"eng","text":"The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≄ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≄ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≄ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≄ 5 and (k, d) Ìž= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K â†Ș→ Rd of K into a d-dimensional Euclidean space."}],"title":"Algorithmic aspects of homotopy theory and embeddability","file_date_updated":"2020-07-14T12:47:37Z","publisher":"Institute of Science and Technology Austria","date_published":"2019-08-08T00:00:00Z","citation":{"ieee":"S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019.","apa":"Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681","chicago":"Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681.","ista":"Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria.","ama":"Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681","short":"S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019.","mla":"Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681."},"department":[{"_id":"UlWa"}],"date_updated":"2023-09-07T13:10:36Z","alternative_title":["ISTA Thesis"],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"degree_awarded":"PhD"},{"department":[{"_id":"BeVi"}],"date_updated":"2023-08-29T06:42:22Z","citation":{"ista":"Cossard G, Toups MA, Pannell J. 2019. Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of botany. 123(7), 1119–1131.","ama":"Cossard G, Toups MA, Pannell J. Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of botany. 2019;123(7):1119-1131. doi:10.1093/aob/mcy183","chicago":"Cossard, Guillaume, Melissa A Toups, and John Pannell. “Sexual Dimorphism and Rapid Turnover in Gene Expression in Pre-Reproductive Seedlings of a Dioecious Herb.” Annals of Botany. Oxford University Press, 2019. https://doi.org/10.1093/aob/mcy183.","apa":"Cossard, G., Toups, M. A., & Pannell, J. (2019). Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb. Annals of Botany. Oxford University Press. https://doi.org/10.1093/aob/mcy183","ieee":"G. Cossard, M. A. Toups, and J. Pannell, “Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb,” Annals of botany, vol. 123, no. 7. Oxford University Press, pp. 1119–1131, 2019.","short":"G. Cossard, M.A. Toups, J. Pannell, Annals of Botany 123 (2019) 1119–1131.","mla":"Cossard, Guillaume, et al. “Sexual Dimorphism and Rapid Turnover in Gene Expression in Pre-Reproductive Seedlings of a Dioecious Herb.” Annals of Botany, vol. 123, no. 7, Oxford University Press, 2019, pp. 1119–31, doi:10.1093/aob/mcy183."},"external_id":{"pmid":["30289430"],"isi":["000493043500004"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","abstract":[{"text":"Sexual dimorphism in morphology, physiology or life history traits is common in dioecious plants at reproductive maturity, but it is typically inconspicuous or absent in juveniles. Although plants of different sexes probably begin to diverge in gene expression both before their reproduction commences and before dimorphism becomes readily apparent, to our knowledge transcriptome-wide differential gene expression has yet to be demonstrated for any angiosperm species.","lang":"eng"}],"isi":1,"pmid":1,"date_published":"2019-06-04T00:00:00Z","publisher":"Oxford University Press","title":"Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb","oa":1,"page":"1119-1131","year":"2019","doi":"10.1093/aob/mcy183","day":"04","scopus_import":"1","intvolume":" 123","publication":"Annals of botany","quality_controlled":"1","oa_version":"Published Version","author":[{"full_name":"Cossard, Guillaume","last_name":"Cossard","first_name":"Guillaume"},{"id":"4E099E4E-F248-11E8-B48F-1D18A9856A87","full_name":"Toups, Melissa A","last_name":"Toups","first_name":"Melissa A","orcid":"0000-0002-9752-7380"},{"first_name":"John ","last_name":"Pannell","full_name":"Pannell, John "}],"month":"06","issue":"7","language":[{"iso":"eng"}],"volume":123,"article_processing_charge":"No","date_created":"2019-07-28T21:59:15Z","article_type":"original","type":"journal_article","_id":"6710","main_file_link":[{"url":"https://doi.org/10.1093/aob/mcy183","open_access":"1"}],"status":"public","publication_identifier":{"eissn":["1095-8290"],"issn":["0305-7364"]}},{"status":"public","_id":"6713","type":"journal_article","date_created":"2019-07-28T21:59:17Z","author":[{"last_name":"Castro","first_name":"JoĂŁo Pl","full_name":"Castro, JoĂŁo Pl"},{"last_name":"Yancoskie","first_name":"Michelle N.","full_name":"Yancoskie, Michelle N."},{"full_name":"Marchini, Marta","first_name":"Marta","last_name":"Marchini"},{"full_name":"Belohlavy, Stefanie","id":"43FE426A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9849-498X","last_name":"Belohlavy","first_name":"Stefanie"},{"first_name":"Layla","last_name":"Hiramatsu","full_name":"Hiramatsu, Layla"},{"full_name":"Kučka, Marek","first_name":"Marek","last_name":"Kučka"},{"full_name":"Beluch, William H.","first_name":"William H.","last_name":"Beluch"},{"last_name":"Naumann","first_name":"Ronald","full_name":"Naumann, Ronald"},{"last_name":"Skuplik","first_name":"Isabella","full_name":"Skuplik, Isabella"},{"first_name":"John","last_name":"Cobb","full_name":"Cobb, John"},{"orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rolian, Campbell","last_name":"Rolian","first_name":"Campbell"},{"first_name":"Yingguang Frank","last_name":"Chan","full_name":"Chan, Yingguang Frank"}],"oa_version":"Published Version","quality_controlled":"1","article_processing_charge":"No","volume":8,"language":[{"iso":"eng"}],"file":[{"file_name":"2019_eLife_Castro.pdf","date_created":"2019-07-29T07:41:18Z","date_updated":"2020-07-14T12:47:38Z","content_type":"application/pdf","access_level":"open_access","file_size":6748249,"file_id":"6721","checksum":"fa0936fe58f0d9e3f8e75038570e5a17","creator":"apreinsp","relation":"main_file"}],"article_number":"e42014","month":"06","has_accepted_license":"1","doi":"10.7554/eLife.42014","year":"2019","day":"06","oa":1,"publication":"eLife","intvolume":" 8","related_material":{"record":[{"id":"9804","relation":"research_data","status":"public"},{"relation":"dissertation_contains","id":"11388","status":"public"}]},"scopus_import":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"pmid":["31169497"],"isi":["000473588700001"]},"citation":{"mla":"Castro, JoĂŁo Pl, et al. “An Integrative Genomic Analysis of the Longshanks Selection Experiment for Longer Limbs in Mice.” ELife, vol. 8, e42014, eLife Sciences Publications, 2019, doi:10.7554/eLife.42014.","short":"J.P. Castro, M.N. Yancoskie, M. Marchini, S. Belohlavy, L. Hiramatsu, M. Kučka, W.H. Beluch, R. Naumann, I. Skuplik, J. Cobb, N.H. Barton, C. Rolian, Y.F. Chan, ELife 8 (2019).","ieee":"J. P. Castro et al., “An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice,” eLife, vol. 8. eLife Sciences Publications, 2019.","apa":"Castro, J. P., Yancoskie, M. N., Marchini, M., Belohlavy, S., Hiramatsu, L., Kučka, M., 
 Chan, Y. F. (2019). An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. ELife. eLife Sciences Publications. https://doi.org/10.7554/eLife.42014","ista":"Castro JP, Yancoskie MN, Marchini M, Belohlavy S, Hiramatsu L, Kučka M, Beluch WH, Naumann R, Skuplik I, Cobb J, Barton NH, Rolian C, Chan YF. 2019. An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. eLife. 8, e42014.","chicago":"Castro, JoĂŁo Pl, Michelle N. Yancoskie, Marta Marchini, Stefanie Belohlavy, Layla Hiramatsu, Marek Kučka, William H. Beluch, et al. “An Integrative Genomic Analysis of the Longshanks Selection Experiment for Longer Limbs in Mice.” ELife. eLife Sciences Publications, 2019. https://doi.org/10.7554/eLife.42014.","ama":"Castro JP, Yancoskie MN, Marchini M, et al. An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice. eLife. 2019;8. doi:10.7554/eLife.42014"},"date_updated":"2024-03-25T23:30:11Z","department":[{"_id":"NiBa"}],"title":"An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice","publisher":"eLife Sciences Publications","file_date_updated":"2020-07-14T12:47:38Z","date_published":"2019-06-06T00:00:00Z","pmid":1,"ddc":["576"],"isi":1,"abstract":[{"text":"Evolutionary studies are often limited by missing data that are critical to understanding the history of selection. Selection experiments, which reproduce rapid evolution under controlled conditions, are excellent tools to study how genomes evolve under selection. Here we present a genomic dissection of the Longshanks selection experiment, in which mice were selectively bred over 20 generations for longer tibiae relative to body mass, resulting in 13% longer tibiae in two replicates. We synthesized evolutionary theory, genome sequences and molecular genetics to understand the selection response and found that it involved both polygenic adaptation and discrete loci of major effect, with the strongest loci tending to be selected in parallel between replicates. We show that selection may favor de-repression of bone growth through inactivating two limb enhancers of an inhibitor, Nkx3-2. Our integrative genomic analyses thus show that it is possible to connect individual base-pair changes to the overall selection response.","lang":"eng"}],"publication_status":"published"},{"year":"2019","doi":"10.3389/fmicb.2019.01171","day":"03","oa":1,"intvolume":" 10","publication":"Frontiers in Microbiology","scopus_import":"1","external_id":{"isi":["000470131200001"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"department":[{"_id":"CaGu"}],"date_updated":"2023-08-29T06:41:20Z","citation":{"short":"C. Igler, S.T. Abedon, Frontiers in Microbiology 10 (2019).","mla":"Igler, Claudia, and Stephen T. Abedon. “Commentary: A Host-Produced Quorum-Sensing Autoinducer Controls a Phage Lysis-Lysogeny Decision.” Frontiers in Microbiology, vol. 10, 1171, Frontiers, 2019, doi:10.3389/fmicb.2019.01171.","chicago":"Igler, Claudia, and Stephen T. Abedon. “Commentary: A Host-Produced Quorum-Sensing Autoinducer Controls a Phage Lysis-Lysogeny Decision.” Frontiers in Microbiology. Frontiers, 2019. https://doi.org/10.3389/fmicb.2019.01171.","ista":"Igler C, Abedon ST. 2019. Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. 10, 1171.","ama":"Igler C, Abedon ST. Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. 2019;10. doi:10.3389/fmicb.2019.01171","apa":"Igler, C., & Abedon, S. T. (2019). Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision. Frontiers in Microbiology. Frontiers. https://doi.org/10.3389/fmicb.2019.01171","ieee":"C. Igler and S. T. Abedon, “Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision,” Frontiers in Microbiology, vol. 10. Frontiers, 2019."},"publisher":"Frontiers","file_date_updated":"2020-07-14T12:47:38Z","date_published":"2019-06-03T00:00:00Z","title":"Commentary: A host-produced quorum-sensing autoinducer controls a phage lysis-lysogeny decision","publication_status":"published","abstract":[{"text":"With the recent publication by Silpe and Bassler (2019), considering phage detection of a bacterial quorum-sensing (QS) autoinducer, we now have as many as five examples of phage-associated intercellular communication (Table 1). Each potentially involves ecological inferences by phages as to concentrations of surrounding phage-infected or uninfected bacteria. While the utility of phage detection of bacterial QS molecules may at first glance appear to be straightforward, we suggest in this commentary that the underlying ecological explanation is unlikely to be simple.","lang":"eng"}],"ddc":["570"],"isi":1,"status":"public","date_created":"2019-07-28T21:59:18Z","_id":"6717","type":"journal_article","author":[{"first_name":"Claudia","last_name":"Igler","id":"46613666-F248-11E8-B48F-1D18A9856A87","full_name":"Igler, Claudia"},{"full_name":"Abedon, Stephen T.","first_name":"Stephen T.","last_name":"Abedon"}],"project":[{"_id":"251EE76E-B435-11E9-9278-68D0E5697425","grant_number":"24573","name":"Design principles underlying genetic switch architecture (DOC Fellowship)"}],"quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"volume":10,"article_processing_charge":"Yes (via OA deal)","month":"06","has_accepted_license":"1","article_number":"1171","file":[{"access_level":"open_access","file_size":246151,"checksum":"317a06067e9a8e717bb55f23e0d77ba7","file_id":"6722","creator":"apreinsp","relation":"main_file","file_name":"2019_Frontiers_Igler.pdf","date_created":"2019-07-29T07:51:54Z","date_updated":"2020-07-14T12:47:38Z","content_type":"application/pdf"}]},{"ec_funded":1,"conference":{"start_date":"2019-07-08","end_date":"2019-07-12","name":"ICALP 2019: International Colloquim on Automata, Languages and Programming","location":"Patras, Greece"},"date_created":"2019-07-29T12:23:29Z","type":"conference","_id":"6725","status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-109-2"]},"has_accepted_license":"1","month":"07","file":[{"relation":"main_file","file_size":575475,"access_level":"open_access","creator":"dernst","checksum":"f5ebee8eec6ae09e30365578ee63a492","file_id":"6738","date_updated":"2020-07-14T12:47:38Z","date_created":"2019-07-31T07:01:45Z","content_type":"application/pdf","file_name":"2019_LIPICS_Kolmogorov.pdf"}],"language":[{"iso":"eng"}],"volume":132,"project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa_version":"Published Version","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"}],"scopus_import":1,"intvolume":" 132","arxiv":1,"publication":"46th International Colloquium on Automata, Languages and Programming","oa":1,"doi":"10.4230/LIPICS.ICALP.2019.77","page":"77:1-77:12","year":"2019","day":"01","abstract":[{"text":"A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‟√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant ÎŽ<1 there is no O(3‟√3ÎŽ|D|) algorithm, assuming that SETH holds.","lang":"eng"}],"publication_status":"published","ddc":["000"],"file_date_updated":"2020-07-14T12:47:38Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik","date_published":"2019-07-01T00:00:00Z","title":"Testing the complexity of a valued CSP language","date_updated":"2021-01-12T08:08:40Z","department":[{"_id":"VlKo"}],"citation":{"ieee":"V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12.","apa":"Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77","chicago":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.","ista":"Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.","ama":"Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77","short":"V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik, 2019, p. 77:1-77:12.","mla":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum fĂŒr Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1803.02289"]},"alternative_title":["LIPIcs"]},{"scopus_import":"1","editor":[{"last_name":"Buchmann","first_name":"J","full_name":"Buchmann, J"},{"full_name":"Nitaj, A","last_name":"Nitaj","first_name":"A"},{"last_name":"Rachidi","first_name":"T","full_name":"Rachidi, T"}],"publication":"Progress in Cryptology – AFRICACRYPT 2019","intvolume":" 11627","oa":1,"year":"2019","doi":"10.1007/978-3-030-23696-0_9","page":"157-180","day":"29","series_title":"LNCS","publication_status":"published","abstract":[{"text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so.","lang":"eng"}],"title":"Sampling the integers with low relative error","date_published":"2019-06-29T00:00:00Z","publisher":"Springer Nature","citation":{"mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.","ieee":"M. Walter, “Sampling the integers with low relative error,” in Progress in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019 (Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9","chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180."},"department":[{"_id":"KrPi"}],"date_updated":"2023-02-23T12:50:15Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","conference":{"name":"AFRICACRYPT: International Conference on Cryptology in Africa","location":"Rabat, Morocco","start_date":"2019-07-09","end_date":"2019-07-11"},"ec_funded":1,"type":"book_chapter","_id":"6726","date_created":"2019-07-29T12:25:31Z","status":"public","publication_identifier":{"isbn":["978-3-0302-3695-3"],"eisbn":["978-3-0302-3696-0"],"issn":["0302-9743","1611-3349"]},"main_file_link":[{"url":"https://eprint.iacr.org/2019/068","open_access":"1"}],"month":"06","volume":11627,"article_processing_charge":"No","language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"author":[{"full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael"}],"place":"Cham"},{"month":"04","publication_status":"published","abstract":[{"lang":"eng","text":"We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≀i≀r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable đ”Œ(y), when d3/2â‰Șrâ‰Șd2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting. "}],"date_published":"2019-04-01T00:00:00Z","publisher":"Proceedings of Machine Learning Research","language":[{"iso":"eng"}],"title":"On the connection between learning two-layers neural networks and tensor decomposition","volume":89,"article_processing_charge":"No","quality_controlled":"1","extern":"1","date_updated":"2021-01-12T08:08:49Z","oa_version":"Preprint","citation":{"apa":"Mondelli, M., & Montanari, A. (2019). On the connection between learning two-layers neural networks and tensor  decomposition. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (Vol. 89, pp. 1051–1060). Naha, Okinawa, Japan: Proceedings of Machine Learning Research.","ista":"Mondelli M, Montanari A. 2019. On the connection between learning two-layers neural networks and tensor  decomposition. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. AISTATS: Artificial Intelligence and Statistics vol. 89, 1051–1060.","ama":"Mondelli M, Montanari A. On the connection between learning two-layers neural networks and tensor  decomposition. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. Vol 89. Proceedings of Machine Learning Research; 2019:1051-1060.","chicago":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor  Decomposition.” In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 89:1051–60. Proceedings of Machine Learning Research, 2019.","ieee":"M. Mondelli and A. Montanari, “On the connection between learning two-layers neural networks and tensor  decomposition,” in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Naha, Okinawa, Japan, 2019, vol. 89, pp. 1051–1060.","short":"M. Mondelli, A. Montanari, in:, Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 2019, pp. 1051–1060.","mla":"Mondelli, Marco, and Andrea Montanari. “On the Connection between Learning Two-Layers Neural Networks and Tensor  Decomposition.” Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, vol. 89, Proceedings of Machine Learning Research, 2019, pp. 1051–60."},"author":[{"orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425"},{"last_name":"Montanari","first_name":"Andrea","full_name":"Montanari, Andrea"}],"external_id":{"arxiv":["1802.07301"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"conference":{"start_date":"2019-04-16","end_date":"2019-04-18","location":"Naha, Okinawa, Japan","name":"AISTATS: Artificial Intelligence and Statistics"},"intvolume":" 89","publication":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics","oa":1,"date_created":"2019-07-31T09:31:26Z","type":"conference","_id":"6747","page":"1051-1060","day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1802.07301"}],"status":"public","year":"2019"},{"department":[{"_id":"MaMo"}],"date_updated":"2021-01-12T08:08:51Z","citation":{"ista":"Hashemi SA, Condo C, Mondelli M, Gross WJ. 2019. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 67(22), 8854897.","ama":"Hashemi SA, Condo C, Mondelli M, Gross WJ. Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. 2019;67(22). doi:10.1109/TSP.2019.2944738","chicago":"Hashemi, Seyyed Ali, Carlo Condo, Marco Mondelli, and Warren J Gross. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing. IEEE, 2019. https://doi.org/10.1109/TSP.2019.2944738.","apa":"Hashemi, S. A., Condo, C., Mondelli, M., & Gross, W. J. (2019). Rate-flexible fast polar decoders. IEEE Transactions on Signal Processing. IEEE. https://doi.org/10.1109/TSP.2019.2944738","ieee":"S. A. Hashemi, C. Condo, M. Mondelli, and W. J. Gross, “Rate-flexible fast polar decoders,” IEEE Transactions on Signal Processing, vol. 67, no. 22. IEEE, 2019.","short":"S.A. Hashemi, C. Condo, M. Mondelli, W.J. Gross, IEEE Transactions on Signal Processing 67 (2019).","mla":"Hashemi, Seyyed Ali, et al. “Rate-Flexible Fast Polar Decoders.” IEEE Transactions on Signal Processing, vol. 67, no. 22, 8854897, IEEE, 2019, doi:10.1109/TSP.2019.2944738."},"external_id":{"arxiv":["1903.09203"]},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication_status":"published","abstract":[{"lang":"eng","text":"Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. "}],"publisher":"IEEE","date_published":"2019-11-15T00:00:00Z","title":"Rate-flexible fast polar decoders","oa":1,"year":"2019","doi":"10.1109/TSP.2019.2944738","day":"15","scopus_import":1,"arxiv":1,"intvolume":" 67","publication":"IEEE Transactions on Signal Processing","quality_controlled":"1","oa_version":"Preprint","author":[{"full_name":"Hashemi, Seyyed Ali","last_name":"Hashemi","first_name":"Seyyed Ali"},{"first_name":"Carlo","last_name":"Condo","full_name":"Condo, Carlo"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco","last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020"},{"first_name":"Warren J","last_name":"Gross","full_name":"Gross, Warren J"}],"month":"11","article_number":"8854897","issue":"22","language":[{"iso":"eng"}],"volume":67,"article_processing_charge":"No","date_created":"2019-07-31T09:51:14Z","article_type":"original","type":"journal_article","_id":"6750","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1903.09203"}],"publication_identifier":{"issn":["1053587X"]},"status":"public"},{"isi":1,"abstract":[{"lang":"eng","text":"Two-player games on graphs are widely studied in formal methods, as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate budgets, which sum up to 1. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a threshold budget in a vertex is a value t ∈ [0, 1] such that if Player 1’s budget exceeds t, he can win the game; and if Player 2’s budget exceeds 1 − t, he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with random-turn games—a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players."}],"publication_status":"published","title":"Infinite-duration bidding games","date_published":"2019-07-16T00:00:00Z","publisher":"ACM","citation":{"short":"G. Avni, T.A. Henzinger, V.K. Chonev, Journal of the ACM 66 (2019).","mla":"Avni, Guy, et al. “Infinite-Duration Bidding Games.” Journal of the ACM, vol. 66, no. 4, 31, ACM, 2019, doi:10.1145/3340295.","chicago":"Avni, Guy, Thomas A Henzinger, and Ventsislav K Chonev. “Infinite-Duration Bidding Games.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3340295.","ista":"Avni G, Henzinger TA, Chonev VK. 2019. Infinite-duration bidding games. Journal of the ACM. 66(4), 31.","ama":"Avni G, Henzinger TA, Chonev VK. Infinite-duration bidding games. Journal of the ACM. 2019;66(4). doi:10.1145/3340295","apa":"Avni, G., Henzinger, T. A., & Chonev, V. K. (2019). Infinite-duration bidding games. Journal of the ACM. ACM. https://doi.org/10.1145/3340295","ieee":"G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,” Journal of the ACM, vol. 66, no. 4. ACM, 2019."},"date_updated":"2023-08-29T07:02:13Z","department":[{"_id":"ToHe"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"arxiv":["1705.01433"],"isi":["000487714900008"]},"related_material":{"record":[{"id":"950","relation":"earlier_version","status":"public"}]},"scopus_import":"1","publication":"Journal of the ACM","intvolume":" 66","arxiv":1,"oa":1,"year":"2019","doi":"10.1145/3340295","day":"16","issue":"4","article_number":"31","month":"07","article_processing_charge":"No","volume":66,"language":[{"iso":"eng"}],"oa_version":"Preprint","project":[{"name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF"},{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369","_id":"264B3912-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"quality_controlled":"1","author":[{"first_name":"Guy","last_name":"Avni","orcid":"0000-0001-5588-8287","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","full_name":"Avni, Guy"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","last_name":"Henzinger","first_name":"Thomas A"},{"first_name":"Ventsislav K","last_name":"Chonev","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","full_name":"Chonev, Ventsislav K"}],"type":"journal_article","_id":"6752","date_created":"2019-08-04T21:59:16Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.01433"}],"status":"public","publication_identifier":{"issn":["00045411"],"eissn":["1557735X"]}},{"oa":1,"page":"1909-1922","year":"2019","doi":"10.1093/gbe/evz133","day":"01","scopus_import":"1","publication":"Genome biology and evolution","intvolume":" 11","citation":{"mla":"Picard, Marion A. L., et al. “Dosage Compensation throughout the Schistosoma Mansoni Lifecycle: Specific Chromatin Landscape of the Z Chromosome.” Genome Biology and Evolution, vol. 11, no. 7, Oxford Academic Press, 2019, pp. 1909–22, doi:10.1093/gbe/evz133.","short":"M.A.L. Picard, B. Vicoso, D. Roquis, I. Bulla, R.C. Augusto, N. Arancibia, C. Grunau, J. Boissier, C. Cosseau, Genome Biology and Evolution 11 (2019) 1909–1922.","ieee":"M. A. L. Picard et al., “Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome,” Genome biology and evolution, vol. 11, no. 7. Oxford Academic Press, pp. 1909–1922, 2019.","apa":"Picard, M. A. L., Vicoso, B., Roquis, D., Bulla, I., Augusto, R. C., Arancibia, N., 
 Cosseau, C. (2019). Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome. Genome Biology and Evolution. Oxford Academic Press. https://doi.org/10.1093/gbe/evz133","ama":"Picard MAL, Vicoso B, Roquis D, et al. Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome. Genome biology and evolution. 2019;11(7):1909-1922. doi:10.1093/gbe/evz133","ista":"Picard MAL, Vicoso B, Roquis D, Bulla I, Augusto RC, Arancibia N, Grunau C, Boissier J, Cosseau C. 2019. Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome. Genome biology and evolution. 11(7), 1909–1922.","chicago":"Picard, Marion A L, Beatriz Vicoso, David Roquis, Ingo Bulla, Ronaldo C. Augusto, Nathalie Arancibia, Christoph Grunau, JĂ©rĂŽme Boissier, and CĂ©line Cosseau. “Dosage Compensation throughout the Schistosoma Mansoni Lifecycle: Specific Chromatin Landscape of the Z Chromosome.” Genome Biology and Evolution. Oxford Academic Press, 2019. https://doi.org/10.1093/gbe/evz133."},"date_updated":"2023-08-29T06:53:58Z","department":[{"_id":"BeVi"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"pmid":["31273378"],"isi":["000484039500018"]},"ddc":["570"],"isi":1,"abstract":[{"text":"Differentiated sex chromosomes are accompanied by a difference in gene dose between X/Z-specific and autosomal genes. At the transcriptomic level, these sex-linked genes can lead to expression imbalance, or gene dosage can be compensated by epigenetic mechanisms and results into expression level equalization. Schistosoma mansoni has been previously described as a ZW species (i.e., female heterogamety, in opposition to XY male heterogametic species) with a partial dosage compensation, but underlying mechanisms are still unexplored. Here, we combine transcriptomic (RNA-Seq) and epigenetic data (ChIP-Seq against H3K4me3, H3K27me3,andH4K20me1histonemarks) in free larval cercariae and intravertebrate parasitic stages. For the first time, we describe differences in dosage compensation status in ZW females, depending on the parasitic status: free cercariae display global dosage compensation, whereas intravertebrate stages show a partial dosage compensation. We also highlight regional differences of gene expression along the Z chromosome in cercariae, but not in the intravertebrate stages. Finally, we feature a consistent permissive chromatin landscape of the Z chromosome in both sexes and stages. We argue that dosage compensation in schistosomes is characterized by chromatin remodeling mechanisms in the Z-specific region.","lang":"eng"}],"publication_status":"published","title":"Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome","file_date_updated":"2020-07-14T12:47:39Z","date_published":"2019-07-01T00:00:00Z","publisher":"Oxford Academic Press","pmid":1,"type":"journal_article","_id":"6755","article_type":"original","date_created":"2019-08-04T21:59:18Z","status":"public","publication_identifier":{"eissn":["1759-6653"]},"oa_version":"Published Version","quality_controlled":"1","author":[{"full_name":"Picard, Marion A L","id":"2C921A7A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8101-2518","first_name":"Marion A L","last_name":"Picard"},{"full_name":"Vicoso, Beatriz","id":"49E1C5C6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4579-8306","first_name":"Beatriz","last_name":"Vicoso"},{"first_name":"David","last_name":"Roquis","full_name":"Roquis, David"},{"full_name":"Bulla, Ingo","first_name":"Ingo","last_name":"Bulla"},{"last_name":"Augusto","first_name":"Ronaldo C.","full_name":"Augusto, Ronaldo C."},{"full_name":"Arancibia, Nathalie","first_name":"Nathalie","last_name":"Arancibia"},{"full_name":"Grunau, Christoph","first_name":"Christoph","last_name":"Grunau"},{"last_name":"Boissier","first_name":"JĂ©rĂŽme","full_name":"Boissier, JĂ©rĂŽme"},{"full_name":"Cosseau, CĂ©line","last_name":"Cosseau","first_name":"CĂ©line"}],"issue":"7","file":[{"relation":"main_file","file_id":"6765","checksum":"f9e8f6863a406dcc5a36b2be001c138c","creator":"dernst","access_level":"open_access","file_size":580205,"content_type":"application/pdf","date_created":"2019-08-05T07:55:02Z","date_updated":"2020-07-14T12:47:39Z","file_name":"2019_GenomeBiology_Picard.pdf"}],"has_accepted_license":"1","month":"07","acknowledged_ssus":[{"_id":"CampIT"}],"article_processing_charge":"No","volume":11,"language":[{"iso":"eng"}]},{"status":"public","publication_identifier":{"issn":["00046361"],"eissn":["14320746"]},"_id":"6756","type":"journal_article","article_type":"original","date_created":"2019-08-04T21:59:18Z","article_processing_charge":"No","volume":627,"language":[{"iso":"eng"}],"article_number":"A163","file":[{"file_name":"2019_AstronomyAstrophysics_Pranav.pdf","date_updated":"2020-07-14T12:47:39Z","date_created":"2019-08-05T08:08:59Z","content_type":"application/pdf","file_size":14420451,"access_level":"open_access","creator":"dernst","file_id":"6766","checksum":"83b9209ed9eefbdcefd89019c5a97805","relation":"main_file"}],"month":"07","has_accepted_license":"1","author":[{"full_name":"Pranav, Pratyush","first_name":"Pratyush","last_name":"Pranav"},{"full_name":"Adler, Robert J.","first_name":"Robert J.","last_name":"Adler"},{"last_name":"Buchert","first_name":"Thomas","full_name":"Buchert, Thomas"},{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Jones, Bernard J.T.","first_name":"Bernard J.T.","last_name":"Jones"},{"full_name":"Schwartzman, Armin","first_name":"Armin","last_name":"Schwartzman"},{"last_name":"Wagner","first_name":"Hubert","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert"},{"full_name":"Van De Weygaert, Rien","first_name":"Rien","last_name":"Van De Weygaert"}],"oa_version":"Published Version","project":[{"_id":"265683E4-B435-11E9-9278-68D0E5697425","grant_number":"M62909-18-1-2038","name":"Toward Computational Information Topology"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","publication":"Astronomy and Astrophysics","intvolume":" 627","arxiv":1,"scopus_import":"1","doi":"10.1051/0004-6361/201834916","day":"17","year":"2019","oa":1,"title":"Unexpected topology of the temperature fluctuations in the cosmic microwave background","file_date_updated":"2020-07-14T12:47:39Z","publisher":"EDP Sciences","date_published":"2019-07-17T00:00:00Z","isi":1,"ddc":["520","530"],"abstract":[{"lang":"eng","text":"We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models."}],"publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000475839300003"],"arxiv":["1812.07678"]},"citation":{"mla":"Pranav, Pratyush, et al. “Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.” Astronomy and Astrophysics, vol. 627, A163, EDP Sciences, 2019, doi:10.1051/0004-6361/201834916.","short":"P. Pranav, R.J. Adler, T. Buchert, H. Edelsbrunner, B.J.T. Jones, A. Schwartzman, H. Wagner, R. Van De Weygaert, Astronomy and Astrophysics 627 (2019).","ieee":"P. Pranav et al., “Unexpected topology of the temperature fluctuations in the cosmic microwave background,” Astronomy and Astrophysics, vol. 627. EDP Sciences, 2019.","ama":"Pranav P, Adler RJ, Buchert T, et al. Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. 2019;627. doi:10.1051/0004-6361/201834916","chicago":"Pranav, Pratyush, Robert J. Adler, Thomas Buchert, Herbert Edelsbrunner, Bernard J.T. Jones, Armin Schwartzman, Hubert Wagner, and Rien Van De Weygaert. “Unexpected Topology of the Temperature Fluctuations in the Cosmic Microwave Background.” Astronomy and Astrophysics. EDP Sciences, 2019. https://doi.org/10.1051/0004-6361/201834916.","ista":"Pranav P, Adler RJ, Buchert T, Edelsbrunner H, Jones BJT, Schwartzman A, Wagner H, Van De Weygaert R. 2019. Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. 627, A163.","apa":"Pranav, P., Adler, R. J., Buchert, T., Edelsbrunner, H., Jones, B. J. T., Schwartzman, A., 
 Van De Weygaert, R. (2019). Unexpected topology of the temperature fluctuations in the cosmic microwave background. Astronomy and Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/201834916"},"date_updated":"2023-08-29T07:01:48Z","department":[{"_id":"HeEd"}]},{"publication":"Electronic Journal of Combinatorics","arxiv":1,"intvolume":" 26","scopus_import":"1","doi":"10.37236/8096","year":"2019","day":"19","oa":1,"title":"On grounded L-graphs and their relatives","publisher":"Electronic Journal of Combinatorics","file_date_updated":"2020-07-14T12:47:39Z","date_published":"2019-07-19T00:00:00Z","ddc":["510"],"publication_status":"published","abstract":[{"lang":"eng","text":"We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. \r\nWe also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions."}],"external_id":{"arxiv":["1808.04148"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"V. JelĂ­nek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019).","mla":"JelĂ­nek, VĂ­t, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics, vol. 26, no. 3, P3.17, Electronic Journal of Combinatorics, 2019, doi:10.37236/8096.","ista":"JelĂ­nek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 26(3), P3.17.","chicago":"JelĂ­nek, VĂ­t, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2019. https://doi.org/10.37236/8096.","ama":"JelĂ­nek V, Töpfer M. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 2019;26(3). doi:10.37236/8096","apa":"JelĂ­nek, V., & Töpfer, M. (2019). On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/8096","ieee":"V. JelĂ­nek and M. Töpfer, “On grounded L-graphs and their relatives,” Electronic Journal of Combinatorics, vol. 26, no. 3. Electronic Journal of Combinatorics, 2019."},"department":[{"_id":"DaAl"}],"date_updated":"2022-03-18T12:32:02Z","ec_funded":1,"publication_identifier":{"eissn":["10778926"]},"status":"public","article_type":"original","type":"journal_article","_id":"6759","date_created":"2019-08-04T21:59:20Z","volume":26,"article_processing_charge":"No","language":[{"iso":"eng"}],"article_number":"P3.17","file":[{"content_type":"application/pdf","date_created":"2019-08-05T06:46:55Z","date_updated":"2020-07-14T12:47:39Z","file_name":"2019_eJourCombinatorics_Jelinek.pdf","relation":"main_file","checksum":"20fc366fc6683ef0b074a019b73a663a","file_id":"6764","creator":"dernst","access_level":"open_access","file_size":533697}],"issue":"3","has_accepted_license":"1","month":"07","author":[{"full_name":"JelĂ­nek, VĂ­t","last_name":"JelĂ­nek","first_name":"VĂ­t"},{"first_name":"Martin","last_name":"Töpfer","id":"4B865388-F248-11E8-B48F-1D18A9856A87","full_name":"Töpfer, Martin"}],"oa_version":"Published Version","project":[{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1"}]