[{"citation":{"chicago":"Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.","ista":"Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science and Technology Austria.","mla":"Rolinek, Michal. Complexity of Constraint Satisfaction. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_815.","ieee":"M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science and Technology Austria, 2017.","short":"M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and Technology Austria, 2017.","apa":"Rolinek, M. (2017). Complexity of constraint satisfaction. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_815","ama":"Rolinek M. Complexity of constraint satisfaction. 2017. doi:10.15479/AT:ISTA:th_815"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rolinek","full_name":"Rolinek, Michal"}],"publist_id":"6407","article_processing_charge":"No","title":"Complexity of constraint satisfaction","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"has_accepted_license":"1","year":"2017","day":"01","page":"97","doi":"10.15479/AT:ISTA:th_815","date_published":"2017-05-01T00:00:00Z","date_created":"2018-12-11T11:49:35Z","acknowledgement":"FP7/2007-2013/ERC grant agreement no 616160","publisher":"Institute of Science and Technology Austria","oa":1,"supervisor":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"date_updated":"2023-09-07T12:05:41Z","ddc":["004"],"file_date_updated":"2020-07-14T12:48:18Z","department":[{"_id":"VlKo"}],"_id":"992","type":"dissertation","status":"public","pubrep_id":"815","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","publication_status":"published","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"81761fb939acb7585c36629f765b4373","file_id":"4654","date_updated":"2020-07-14T12:48:18Z","file_size":786145,"creator":"system","date_created":"2018-12-12T10:07:55Z","file_name":"IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf"},{"file_name":"2017_Thesis_Rolinek_source.zip","date_created":"2019-04-05T08:43:24Z","creator":"dernst","file_size":5936337,"date_updated":"2020-07-14T12:48:18Z","checksum":"2b2d7e1d6c1c79a9795a7aa0f860baf3","file_id":"6208","relation":"source_file","access_level":"closed","content_type":"application/zip"}],"language":[{"iso":"eng"}],"ec_funded":1,"abstract":[{"text":"An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of\r\nvariables, a finite domain of labels, and a set of constraints, each constraint acting on\r\na subset of the variables. The goal is to find an assignment of labels to its variables\r\nthat satisfies all constraints (or decide whether one exists). If we allow more general\r\n“soft” constraints, which come with (possibly infinite) costs of particular assignments,\r\nwe obtain instances from a richer class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal is to find an assignment with minimum total cost.\r\nIn this thesis, we focus (assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage, that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe complexity classification modulo (missing pieces of) complexity classification for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’ perfect\r\nmatching algorithm. This generalization contributes to complexity classfications in two\r\nways. First, it gives a new (largest known) polynomial-time solvable class of Boolean\r\nCSPs in which every variable may appear in at most two constraints and second, it\r\nsettles full classification of Boolean CSPs with planar drawing (again parametrized by a\r\nconstraint language).","lang":"eng"}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"05"},{"intvolume":" 49","month":"09","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.05915"}],"scopus_import":1,"oa_version":"Preprint","abstract":[{"text":"Mapping every simplex in the Delaunay mosaic of a discrete point set to the radius of the smallest empty circumsphere gives a generalized discrete Morse function. Choosing the points from a Poisson point process in ℝ n , we study the expected number of simplices in the Delaunay mosaic as well as the expected number of critical simplices and nonsingular intervals in the corresponding generalized discrete gradient. Observing connections with other probabilistic models, we obtain precise expressions for the expected numbers in low dimensions. In particular, we obtain the expected numbers of simplices in the Poisson–Delaunay mosaic in dimensions n ≤ 4.","lang":"eng"}],"ec_funded":1,"issue":"3","related_material":{"record":[{"id":"6287","status":"public","relation":"dissertation_contains"}]},"volume":49,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["00018678"]},"status":"public","type":"journal_article","_id":"718","department":[{"_id":"HeEd"}],"date_updated":"2023-09-07T12:07:12Z","oa":1,"quality_controlled":"1","publisher":"Cambridge University Press","date_created":"2018-12-11T11:48:07Z","date_published":"2017-09-01T00:00:00Z","doi":"10.1017/apr.2017.20","page":"745 - 767","publication":"Advances in Applied Probability","day":"01","year":"2017","project":[{"call_identifier":"FP7","_id":"255D761E-B435-11E9-9278-68D0E5697425","name":"Topological Complex Systems","grant_number":"318493"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes"}],"title":"Expected sizes of poisson Delaunay mosaics and their discrete Morse functions","external_id":{"arxiv":["1607.05915"]},"author":[{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"orcid":"0000-0002-0659-3201","full_name":"Nikitenko, Anton","last_name":"Nikitenko","id":"3E4FF1BA-F248-11E8-B48F-1D18A9856A87","first_name":"Anton"},{"first_name":"Matthias","last_name":"Reitzner","full_name":"Reitzner, Matthias"}],"publist_id":"6962","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Edelsbrunner H, Nikitenko A, Reitzner M. 2017. Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. 49(3), 745–767.","chicago":"Edelsbrunner, Herbert, Anton Nikitenko, and Matthias Reitzner. “Expected Sizes of Poisson Delaunay Mosaics and Their Discrete Morse Functions.” Advances in Applied Probability. Cambridge University Press, 2017. https://doi.org/10.1017/apr.2017.20.","ieee":"H. Edelsbrunner, A. Nikitenko, and M. Reitzner, “Expected sizes of poisson Delaunay mosaics and their discrete Morse functions,” Advances in Applied Probability, vol. 49, no. 3. Cambridge University Press, pp. 745–767, 2017.","short":"H. Edelsbrunner, A. Nikitenko, M. Reitzner, Advances in Applied Probability 49 (2017) 745–767.","apa":"Edelsbrunner, H., Nikitenko, A., & Reitzner, M. (2017). Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. Cambridge University Press. https://doi.org/10.1017/apr.2017.20","ama":"Edelsbrunner H, Nikitenko A, Reitzner M. Expected sizes of poisson Delaunay mosaics and their discrete Morse functions. Advances in Applied Probability. 2017;49(3):745-767. doi:10.1017/apr.2017.20","mla":"Edelsbrunner, Herbert, et al. “Expected Sizes of Poisson Delaunay Mosaics and Their Discrete Morse Functions.” Advances in Applied Probability, vol. 49, no. 3, Cambridge University Press, 2017, pp. 745–67, doi:10.1017/apr.2017.20."}},{"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"author":[{"full_name":"Abusalah, Hamza M","last_name":"Abusalah","first_name":"Hamza M","id":"40297222-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"full_name":"Cohen, Bram","last_name":"Cohen","first_name":"Bram"},{"last_name":"Khilko","full_name":"Khilko, Danylo","first_name":"Danylo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Leonid","full_name":"Reyzin, Leonid","last_name":"Reyzin"}],"publist_id":"7257","title":"Beyond Hellman’s time-memory trade-offs with applications to proofs of space","citation":{"ista":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT: Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625, 357–379.","chicago":"Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13.","short":"H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379.","ieee":"H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L. Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.","ama":"Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer; 2017:357-379. doi:10.1007/978-3-319-70697-9_13","apa":"Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., & Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory and Applications of Cryptology and Information Security, Hong Kong, China: Springer. https://doi.org/10.1007/978-3-319-70697-9_13","mla":"Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publisher":"Springer","quality_controlled":"1","page":"357 - 379","date_created":"2018-12-11T11:47:10Z","doi":"10.1007/978-3-319-70697-9_13","date_published":"2017-11-18T00:00:00Z","year":"2017","day":"18","conference":{"name":"ASIACRYPT: Theory and Applications of Cryptology and Information Security","start_date":"2017-12-03","location":"Hong Kong, China","end_date":"2017-12-07"},"type":"conference","status":"public","_id":"559","department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T12:30:22Z","main_file_link":[{"url":"https://eprint.iacr.org/2017/893.pdf","open_access":"1"}],"scopus_import":1,"alternative_title":["LNCS"],"intvolume":" 10625","month":"11","abstract":[{"lang":"eng","text":"Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever (Formula presented). For functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To prove lower bounds, one considers an adversary who has access to an oracle f: [ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈ Ω(N) and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk) (in particular, S= T≈ (Formula presented). Our construction does not contradict Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle g: [N] × [N] → [ N] and a random permutation oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with π being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must satisfy S2· T∈ Ω(ϵ2N2)."}],"oa_version":"Submitted Version","ec_funded":1,"volume":10625,"related_material":{"record":[{"id":"83","status":"public","relation":"dissertation_contains"}]},"publication_status":"published","publication_identifier":{"isbn":["978-331970696-2"]},"language":[{"iso":"eng"}]},{"date_created":"2018-12-11T11:47:07Z","date_published":"2017-11-21T00:00:00Z","doi":"10.1214/17-ECP97","year":"2017","has_accepted_license":"1","publication":"Electronic Communications in Probability","day":"21","oa":1,"quality_controlled":"1","publisher":"Institute of Mathematical Statistics","publist_id":"7265","author":[{"id":"36D3D8B6-F248-11E8-B48F-1D18A9856A87","first_name":"Johannes","last_name":"Alt","full_name":"Alt, Johannes"}],"title":"Singularities of the density of states of random Gram matrices","citation":{"apa":"Alt, J. (2017). Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/17-ECP97","ama":"Alt J. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 2017;22. doi:10.1214/17-ECP97","short":"J. Alt, Electronic Communications in Probability 22 (2017).","ieee":"J. Alt, “Singularities of the density of states of random Gram matrices,” Electronic Communications in Probability, vol. 22. Institute of Mathematical Statistics, 2017.","mla":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” Electronic Communications in Probability, vol. 22, 63, Institute of Mathematical Statistics, 2017, doi:10.1214/17-ECP97.","ista":"Alt J. 2017. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 22, 63.","chicago":"Alt, Johannes. “Singularities of the Density of States of Random Gram Matrices.” Electronic Communications in Probability. Institute of Mathematical Statistics, 2017. https://doi.org/10.1214/17-ECP97."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"258DCDE6-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Random matrices, universality and disordered quantum systems","grant_number":"338804"}],"article_number":"63","ec_funded":1,"related_material":{"record":[{"id":"149","status":"public","relation":"dissertation_contains"}]},"volume":22,"publication_status":"published","publication_identifier":{"issn":["1083589X"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"0ec05303a0de190de145654237984c79","file_id":"4663","date_updated":"2020-07-14T12:47:00Z","file_size":470876,"creator":"system","date_created":"2018-12-12T10:08:04Z","file_name":"IST-2018-926-v1+1_euclid.ecp.1511233247.pdf"}],"scopus_import":1,"intvolume":" 22","month":"11","abstract":[{"lang":"eng","text":"For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities."}],"oa_version":"Published Version","department":[{"_id":"LaEr"}],"file_date_updated":"2020-07-14T12:47:00Z","date_updated":"2023-09-07T12:38:08Z","ddc":["539"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","pubrep_id":"926","status":"public","_id":"550"},{"date_created":"2018-12-11T11:47:41Z","doi":"10.1007/978-3-319-65765-3_7","date_published":"2017-09-01T00:00:00Z","page":"116 - 132","day":"01","year":"2017","has_accepted_license":"1","oa":1,"publisher":"Springer","quality_controlled":"1","title":"Conic abstractions for hybrid systems","publist_id":"7129","author":[{"last_name":"Bogomolov","orcid":"0000-0002-0686-0365","full_name":"Bogomolov, Sergiy","id":"369D9A44-F248-11E8-B48F-1D18A9856A87","first_name":"Sergiy"},{"first_name":"Mirco","id":"3444EA5E-F248-11E8-B48F-1D18A9856A87","last_name":"Giacobbe","full_name":"Giacobbe, Mirco","orcid":"0000-0001-8180-0904"},{"last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A"},{"first_name":"Hui","id":"3BDE25AA-F248-11E8-B48F-1D18A9856A87","last_name":"Kong","full_name":"Kong, Hui","orcid":"0000-0002-3066-6941"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Bogomolov, Sergiy, Mirco Giacobbe, Thomas A Henzinger, and Hui Kong. “Conic Abstractions for Hybrid Systems,” 10419:116–32. Springer, 2017. https://doi.org/10.1007/978-3-319-65765-3_7.","ista":"Bogomolov S, Giacobbe M, Henzinger TA, Kong H. 2017. Conic abstractions for hybrid systems. FORMATS: Formal Modelling and Analysis of Timed Systems, LNCS, vol. 10419, 116–132.","mla":"Bogomolov, Sergiy, et al. Conic Abstractions for Hybrid Systems. Vol. 10419, Springer, 2017, pp. 116–32, doi:10.1007/978-3-319-65765-3_7.","short":"S. Bogomolov, M. Giacobbe, T.A. Henzinger, H. Kong, in:, Springer, 2017, pp. 116–132.","ieee":"S. Bogomolov, M. Giacobbe, T. A. Henzinger, and H. Kong, “Conic abstractions for hybrid systems,” presented at the FORMATS: Formal Modelling and Analysis of Timed Systems, Berlin, Germany, 2017, vol. 10419, pp. 116–132.","ama":"Bogomolov S, Giacobbe M, Henzinger TA, Kong H. Conic abstractions for hybrid systems. In: Vol 10419. Springer; 2017:116-132. doi:10.1007/978-3-319-65765-3_7","apa":"Bogomolov, S., Giacobbe, M., Henzinger, T. A., & Kong, H. (2017). Conic abstractions for hybrid systems (Vol. 10419, pp. 116–132). Presented at the FORMATS: Formal Modelling and Analysis of Timed Systems, Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-65765-3_7"},"project":[{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"The Wittgenstein Prize","grant_number":"Z211","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"volume":"10419 ","related_material":{"record":[{"id":"6894","status":"public","relation":"dissertation_contains"}]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"faf546914ba29bcf9974ee36b6b16750","file_id":"4956","creator":"system","file_size":3806864,"date_updated":"2020-07-14T12:47:31Z","file_name":"IST-2017-831-v1+1_main.pdf","date_created":"2018-12-12T10:12:38Z"}],"publication_status":"published","publication_identifier":{"isbn":["978-331965764-6"]},"month":"09","scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"Despite researchers’ efforts in the last couple of decades, reachability analysis is still a challenging problem even for linear hybrid systems. Among the existing approaches, the most practical ones are mainly based on bounded-time reachable set over-approximations. For the purpose of unbounded-time analysis, one important strategy is to abstract the original system and find an invariant for the abstraction. In this paper, we propose an approach to constructing a new kind of abstraction called conic abstraction for affine hybrid systems, and to computing reachable sets based on this abstraction. The essential feature of a conic abstraction is that it partitions the state space of a system into a set of convex polyhedral cones which is derived from a uniform conic partition of the derivative space. Such a set of polyhedral cones is able to cut all trajectories of the system into almost straight segments so that every segment of a reach pipe in a polyhedral cone tends to be straight as well, and hence can be over-approximated tightly by polyhedra using similar techniques as HyTech or PHAVer. In particular, for diagonalizable affine systems, our approach can guarantee to find an invariant for unbounded reachable sets, which is beyond the capability of bounded-time reachability analysis tools. We implemented the approach in a tool and experiments on benchmarks show that our approach is more powerful than SpaceEx and PHAVer in dealing with diagonalizable systems."}],"file_date_updated":"2020-07-14T12:47:31Z","department":[{"_id":"ToHe"}],"ddc":["005"],"date_updated":"2023-09-07T12:53:00Z","pubrep_id":"831","status":"public","conference":{"end_date":"2017-09-07","location":"Berlin, Germany","start_date":"2017-09-05","name":"FORMATS: Formal Modelling and Analysis of Timed Systems"},"type":"conference","_id":"647"}]