--- _id: '559' 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).' alternative_title: - LNCS author: - first_name: Hamza M full_name: Abusalah, Hamza M id: 40297222-F248-11E8-B48F-1D18A9856A87 last_name: Abusalah - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 last_name: Alwen - first_name: Bram full_name: Cohen, Bram last_name: Cohen - first_name: Danylo full_name: Khilko, Danylo last_name: Khilko - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Leonid full_name: Reyzin, Leonid last_name: Reyzin citation: 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' 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. 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.' 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.' 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. short: H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin, in:, Springer, 2017, pp. 357–379. conference: end_date: 2017-12-07 location: Hong Kong, China name: 'ASIACRYPT: Theory and Applications of Cryptology and Information Security' start_date: 2017-12-03 date_created: 2018-12-11T11:47:10Z date_published: 2017-11-18T00:00:00Z date_updated: 2023-09-07T12:30:22Z day: '18' department: - _id: KrPi doi: 10.1007/978-3-319-70697-9_13 ec_funded: 1 intvolume: ' 10625' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2017/893.pdf month: '11' oa: 1 oa_version: Submitted Version page: 357 - 379 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: isbn: - 978-331970696-2 publication_status: published publisher: Springer publist_id: '7257' quality_controlled: '1' related_material: record: - id: '83' relation: dissertation_contains status: public scopus_import: 1 status: public title: Beyond Hellman’s time-memory trade-offs with applications to proofs of space type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10625 year: '2017' ... --- _id: '550' 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. article_number: '63' author: - first_name: Johannes full_name: Alt, Johannes id: 36D3D8B6-F248-11E8-B48F-1D18A9856A87 last_name: Alt citation: ama: Alt J. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 2017;22. doi:10.1214/17-ECP97 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 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. ieee: J. Alt, “Singularities of the density of states of random Gram matrices,” Electronic Communications in Probability, vol. 22. Institute of Mathematical Statistics, 2017. ista: Alt J. 2017. Singularities of the density of states of random Gram matrices. Electronic Communications in Probability. 22, 63. 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. short: J. Alt, Electronic Communications in Probability 22 (2017). date_created: 2018-12-11T11:47:07Z date_published: 2017-11-21T00:00:00Z date_updated: 2023-09-07T12:38:08Z day: '21' ddc: - '539' department: - _id: LaEr doi: 10.1214/17-ECP97 ec_funded: 1 file: - access_level: open_access checksum: 0ec05303a0de190de145654237984c79 content_type: application/pdf creator: system date_created: 2018-12-12T10:08:04Z date_updated: 2020-07-14T12:47:00Z file_id: '4663' file_name: IST-2018-926-v1+1_euclid.ecp.1511233247.pdf file_size: 470876 relation: main_file file_date_updated: 2020-07-14T12:47:00Z has_accepted_license: '1' intvolume: ' 22' language: - iso: eng month: '11' oa: 1 oa_version: Published Version project: - _id: 258DCDE6-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '338804' name: Random matrices, universality and disordered quantum systems publication: Electronic Communications in Probability publication_identifier: issn: - 1083589X publication_status: published publisher: Institute of Mathematical Statistics publist_id: '7265' pubrep_id: '926' quality_controlled: '1' related_material: record: - id: '149' relation: dissertation_contains status: public scopus_import: 1 status: public title: Singularities of the density of states of random Gram matrices tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 22 year: '2017' ... --- _id: '647' 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. alternative_title: - LNCS author: - first_name: Sergiy full_name: Bogomolov, Sergiy id: 369D9A44-F248-11E8-B48F-1D18A9856A87 last_name: Bogomolov orcid: 0000-0002-0686-0365 - first_name: Mirco full_name: Giacobbe, Mirco id: 3444EA5E-F248-11E8-B48F-1D18A9856A87 last_name: Giacobbe orcid: 0000-0001-8180-0904 - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Hui full_name: Kong, Hui id: 3BDE25AA-F248-11E8-B48F-1D18A9856A87 last_name: Kong orcid: 0000-0002-3066-6941 citation: 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' 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. 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.' 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. conference: end_date: 2017-09-07 location: Berlin, Germany name: 'FORMATS: Formal Modelling and Analysis of Timed Systems' start_date: 2017-09-05 date_created: 2018-12-11T11:47:41Z date_published: 2017-09-01T00:00:00Z date_updated: 2023-09-07T12:53:00Z day: '01' ddc: - '005' department: - _id: ToHe doi: 10.1007/978-3-319-65765-3_7 file: - access_level: open_access checksum: faf546914ba29bcf9974ee36b6b16750 content_type: application/pdf creator: system date_created: 2018-12-12T10:12:38Z date_updated: 2020-07-14T12:47:31Z file_id: '4956' file_name: IST-2017-831-v1+1_main.pdf file_size: 3806864 relation: main_file file_date_updated: 2020-07-14T12:47:31Z has_accepted_license: '1' language: - iso: eng month: '09' oa: 1 oa_version: Submitted Version page: 116 - 132 project: - _id: 25F5A88A-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Moderne Concurrency Paradigms - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication_identifier: isbn: - 978-331965764-6 publication_status: published publisher: Springer publist_id: '7129' pubrep_id: '831' quality_controlled: '1' related_material: record: - id: '6894' relation: dissertation_contains status: public scopus_import: 1 status: public title: Conic abstractions for hybrid systems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: '10419 ' year: '2017' ... --- _id: '631' abstract: - lang: eng text: Template polyhedra generalize intervals and octagons to polyhedra whose facets are orthogonal to a given set of arbitrary directions. They have been employed in the abstract interpretation of programs and, with particular success, in the reachability analysis of hybrid automata. While previously, the choice of directions has been left to the user or a heuristic, we present a method for the automatic discovery of directions that generalize and eliminate spurious counterexamples. We show that for the class of convex hybrid automata, i.e., hybrid automata with (possibly nonlinear) convex constraints on derivatives, such directions always exist and can be found using convex optimization. We embed our method inside a CEGAR loop, thus enabling the time-unbounded reachability analysis of an important and richer class of hybrid automata than was previously possible. We evaluate our method on several benchmarks, demonstrating also its superior efficiency for the special case of linear hybrid automata. acknowledgement: This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), by the European Commission under grant 643921 (UnCoVerCPS), and by the ARC project DP140104219 (Robust AI Planning for Hybrid Systems). alternative_title: - LNCS author: - first_name: Sergiy full_name: Bogomolov, Sergiy id: 369D9A44-F248-11E8-B48F-1D18A9856A87 last_name: Bogomolov orcid: 0000-0002-0686-0365 - first_name: Goran full_name: Frehse, Goran last_name: Frehse - first_name: Mirco full_name: Giacobbe, Mirco id: 3444EA5E-F248-11E8-B48F-1D18A9856A87 last_name: Giacobbe orcid: 0000-0001-8180-0904 - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: 'Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. Counterexample guided refinement of template polyhedra. In: Vol 10205. Springer; 2017:589-606. doi:10.1007/978-3-662-54577-5_34' apa: 'Bogomolov, S., Frehse, G., Giacobbe, M., & Henzinger, T. A. (2017). Counterexample guided refinement of template polyhedra (Vol. 10205, pp. 589–606). Presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden: Springer. https://doi.org/10.1007/978-3-662-54577-5_34' chicago: Bogomolov, Sergiy, Goran Frehse, Mirco Giacobbe, and Thomas A Henzinger. “Counterexample Guided Refinement of Template Polyhedra,” 10205:589–606. Springer, 2017. https://doi.org/10.1007/978-3-662-54577-5_34. ieee: 'S. Bogomolov, G. Frehse, M. Giacobbe, and T. A. Henzinger, “Counterexample guided refinement of template polyhedra,” presented at the TACAS: Tools and Algorithms for the Construction and Analysis of Systems, Uppsala, Sweden, 2017, vol. 10205, pp. 589–606.' ista: 'Bogomolov S, Frehse G, Giacobbe M, Henzinger TA. 2017. Counterexample guided refinement of template polyhedra. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 10205, 589–606.' mla: Bogomolov, Sergiy, et al. Counterexample Guided Refinement of Template Polyhedra. Vol. 10205, Springer, 2017, pp. 589–606, doi:10.1007/978-3-662-54577-5_34. short: S. Bogomolov, G. Frehse, M. Giacobbe, T.A. Henzinger, in:, Springer, 2017, pp. 589–606. conference: end_date: 2017-04-29 location: Uppsala, Sweden name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems' start_date: 2017-04-22 date_created: 2018-12-11T11:47:36Z date_published: 2017-03-31T00:00:00Z date_updated: 2023-09-07T12:53:00Z day: '31' ddc: - '000' department: - _id: ToHe doi: 10.1007/978-3-662-54577-5_34 file: - access_level: open_access checksum: f395d0d20102b89aeaad8b4ef4f18f4f content_type: application/pdf creator: system date_created: 2018-12-12T10:11:41Z date_updated: 2020-07-14T12:47:27Z file_id: '4897' file_name: IST-2017-741-v1+1_main.pdf file_size: 569863 relation: main_file - access_level: open_access checksum: f416ee1ae4497b23ecdf28b1f18bb8df content_type: application/pdf creator: system date_created: 2018-12-12T10:11:42Z date_updated: 2020-07-14T12:47:27Z file_id: '4898' file_name: IST-2018-741-v2+2_main.pdf file_size: 563276 relation: main_file file_date_updated: 2020-07-14T12:47:27Z has_accepted_license: '1' intvolume: ' 10205' language: - iso: eng month: '03' oa: 1 oa_version: Submitted Version page: 589 - 606 project: - _id: 25F5A88A-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11402-N23 name: Moderne Concurrency Paradigms - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication_identifier: isbn: - 978-366254576-8 publication_status: published publisher: Springer publist_id: '7162' pubrep_id: '966' quality_controlled: '1' related_material: record: - id: '6894' relation: dissertation_contains status: public scopus_import: 1 status: public title: Counterexample guided refinement of template polyhedra type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10205 year: '2017' ... --- _id: '1144' abstract: - lang: eng text: We show that matrix elements of functions of N × N Wigner matrices fluctuate on a scale of order N−1/2 and we identify the limiting fluctuation. Our result holds for any function f of the matrix that has bounded variation thus considerably relaxing the regularity requirement imposed in [7, 11]. acknowledgement: Partially supported by the IST Austria Excellence Scholarship. article_number: '86' author: - first_name: László full_name: Erdös, László id: 4DBD5372-F248-11E8-B48F-1D18A9856A87 last_name: Erdös orcid: 0000-0001-5366-9603 - first_name: Dominik J full_name: Schröder, Dominik J id: 408ED176-F248-11E8-B48F-1D18A9856A87 last_name: Schröder orcid: 0000-0002-2904-1856 citation: ama: Erdös L, Schröder DJ. Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. 2017;21. doi:10.1214/16-ECP38 apa: Erdös, L., & Schröder, D. J. (2017). Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/16-ECP38 chicago: Erdös, László, and Dominik J Schröder. “Fluctuations of Functions of Wigner Matrices.” Electronic Communications in Probability. Institute of Mathematical Statistics, 2017. https://doi.org/10.1214/16-ECP38. ieee: L. Erdös and D. J. Schröder, “Fluctuations of functions of Wigner matrices,” Electronic Communications in Probability, vol. 21. Institute of Mathematical Statistics, 2017. ista: Erdös L, Schröder DJ. 2017. Fluctuations of functions of Wigner matrices. Electronic Communications in Probability. 21, 86. mla: Erdös, László, and Dominik J. Schröder. “Fluctuations of Functions of Wigner Matrices.” Electronic Communications in Probability, vol. 21, 86, Institute of Mathematical Statistics, 2017, doi:10.1214/16-ECP38. short: L. Erdös, D.J. Schröder, Electronic Communications in Probability 21 (2017). date_created: 2018-12-11T11:50:23Z date_published: 2017-01-02T00:00:00Z date_updated: 2023-09-07T12:54:12Z day: '02' ddc: - '510' department: - _id: LaEr doi: 10.1214/16-ECP38 ec_funded: 1 file: - access_level: open_access content_type: application/pdf creator: system date_created: 2018-12-12T10:18:10Z date_updated: 2018-12-12T10:18:10Z file_id: '5329' file_name: IST-2017-747-v1+1_euclid.ecp.1483347665.pdf file_size: 440770 relation: main_file file_date_updated: 2018-12-12T10:18:10Z has_accepted_license: '1' intvolume: ' 21' language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: 258DCDE6-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '338804' name: Random matrices, universality and disordered quantum systems publication: Electronic Communications in Probability publication_status: published publisher: Institute of Mathematical Statistics publist_id: '6214' pubrep_id: '747' quality_controlled: '1' related_material: record: - id: '6179' relation: dissertation_contains status: public scopus_import: 1 status: public title: Fluctuations of functions of Wigner matrices tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 21 year: '2017' ... --- _id: '486' abstract: - lang: eng text: Color texture reproduction in 3D printing commonly ignores volumetric light transport (cross-talk) between surface points on a 3D print. Such light diffusion leads to significant blur of details and color bleeding, and is particularly severe for highly translucent resin-based print materials. Given their widely varying scattering properties, this cross-talk between surface points strongly depends on the internal structure of the volume surrounding each surface point. Existing scattering-aware methods use simplified models for light diffusion, and often accept the visual blur as an immutable property of the print medium. In contrast, our work counteracts heterogeneous scattering to obtain the impression of a crisp albedo texture on top of the 3D print, by optimizing for a fully volumetric material distribution that preserves the target appearance. Our method employs an efficient numerical optimizer on top of a general Monte-Carlo simulation of heterogeneous scattering, supported by a practical calibration procedure to obtain scattering parameters from a given set of printer materials. Despite the inherent translucency of the medium, we reproduce detailed surface textures on 3D prints. We evaluate our system using a commercial, five-tone 3D print process and compare against the printer’s native color texturing mode, demonstrating that our method preserves high-frequency features well without having to compromise on color gamut. article_number: '241' article_processing_charge: No article_type: original author: - first_name: Oskar full_name: Elek, Oskar last_name: Elek - first_name: Denis full_name: Sumin, Denis last_name: Sumin - first_name: Ran full_name: Zhang, Ran id: 4DDBCEB0-F248-11E8-B48F-1D18A9856A87 last_name: Zhang orcid: 0000-0002-3808-281X - first_name: Tim full_name: Weyrich, Tim last_name: Weyrich - first_name: Karol full_name: Myszkowski, Karol last_name: Myszkowski - first_name: Bernd full_name: Bickel, Bernd id: 49876194-F248-11E8-B48F-1D18A9856A87 last_name: Bickel orcid: 0000-0001-6511-9385 - first_name: Alexander full_name: Wilkie, Alexander last_name: Wilkie - first_name: Jaroslav full_name: Krivanek, Jaroslav last_name: Krivanek citation: ama: Elek O, Sumin D, Zhang R, et al. Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. 2017;36(6). doi:10.1145/3130800.3130890 apa: Elek, O., Sumin, D., Zhang, R., Weyrich, T., Myszkowski, K., Bickel, B., … Krivanek, J. (2017). Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. ACM. https://doi.org/10.1145/3130800.3130890 chicago: Elek, Oskar, Denis Sumin, Ran Zhang, Tim Weyrich, Karol Myszkowski, Bernd Bickel, Alexander Wilkie, and Jaroslav Krivanek. “Scattering-Aware Texture Reproduction for 3D Printing.” ACM Transactions on Graphics. ACM, 2017. https://doi.org/10.1145/3130800.3130890. ieee: O. Elek et al., “Scattering-aware texture reproduction for 3D printing,” ACM Transactions on Graphics, vol. 36, no. 6. ACM, 2017. ista: Elek O, Sumin D, Zhang R, Weyrich T, Myszkowski K, Bickel B, Wilkie A, Krivanek J. 2017. Scattering-aware texture reproduction for 3D printing. ACM Transactions on Graphics. 36(6), 241. mla: Elek, Oskar, et al. “Scattering-Aware Texture Reproduction for 3D Printing.” ACM Transactions on Graphics, vol. 36, no. 6, 241, ACM, 2017, doi:10.1145/3130800.3130890. short: O. Elek, D. Sumin, R. Zhang, T. Weyrich, K. Myszkowski, B. Bickel, A. Wilkie, J. Krivanek, ACM Transactions on Graphics 36 (2017). date_created: 2018-12-11T11:46:44Z date_published: 2017-11-20T00:00:00Z date_updated: 2023-09-07T13:11:15Z day: '20' ddc: - '003' - '000' - '005' department: - _id: BeBi doi: 10.1145/3130800.3130890 ec_funded: 1 file: - access_level: open_access checksum: 48386fa6956c3645fc89594dc898b147 content_type: application/pdf creator: system date_created: 2018-12-12T10:10:46Z date_updated: 2020-07-14T12:46:35Z file_id: '4836' file_name: IST-2018-1052-v1+1_ElekSumin2017SGA.pdf file_size: 107349827 relation: main_file - access_level: open_access checksum: 21c89c28fb8d70f6602f752bf997aa0f content_type: application/pdf creator: bbickel date_created: 2019-12-16T14:48:57Z date_updated: 2020-07-14T12:46:35Z file_id: '7189' file_name: ElekSumin2017SGA_reduced_file_size.pdf file_size: 4683145 relation: main_file file_date_updated: 2020-07-14T12:46:35Z has_accepted_license: '1' intvolume: ' 36' issue: '6' language: - iso: eng month: '11' oa: 1 oa_version: Submitted Version project: - _id: 2508E324-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '642841' name: Distributed 3D Object Design - _id: 24F9549A-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '715767' name: 'MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling' - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme publication: ACM Transactions on Graphics publication_identifier: issn: - '07300301' publication_status: published publisher: ACM publist_id: '7334' pubrep_id: '1052' quality_controlled: '1' related_material: record: - id: '8386' relation: dissertation_contains status: public scopus_import: 1 status: public title: Scattering-aware texture reproduction for 3D printing type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 36 year: '2017' ... --- _id: '637' abstract: - lang: eng text: For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs. alternative_title: - LNCS author: - first_name: Zahra full_name: Jafargholi, Zahra last_name: Jafargholi - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Karen full_name: Klein, Karen id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87 last_name: Klein - first_name: Ilan full_name: Komargodski, Ilan last_name: Komargodski - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Daniel full_name: Wichs, Daniel last_name: Wichs citation: ama: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:10.1007/978-3-319-63688-7_5' apa: 'Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz & H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5' chicago: Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5. ieee: 'Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.' ista: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.' mla: Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5. short: Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163. conference: end_date: 2017-07-24 location: Santa Barbara, CA, United States name: 'CRYPTO: Cryptology' start_date: 2017-07-20 date_created: 2018-12-11T11:47:38Z date_published: 2017-01-01T00:00:00Z date_updated: 2023-09-07T13:32:11Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-319-63688-7_5 ec_funded: 1 editor: - first_name: Jonathan full_name: Katz, Jonathan last_name: Katz - first_name: Hovav full_name: Shacham, Hovav last_name: Shacham intvolume: ' 10401' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2017/515 month: '01' oa: 1 oa_version: Submitted Version page: 133 - 163 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication_identifier: isbn: - 978-331963687-0 publication_status: published publisher: Springer publist_id: '7151' quality_controlled: '1' related_material: record: - id: '10035' relation: dissertation_contains status: public scopus_import: 1 status: public title: Be adaptive avoid overcommitting type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 10401 year: '2017' ... --- _id: '9842' abstract: - lang: eng text: Mathematica notebooks used to generate figures. article_processing_charge: No author: - first_name: Alison full_name: Etheridge, Alison last_name: Etheridge - first_name: Nicholas H full_name: Barton, Nicholas H id: 4880FE40-F248-11E8-B48F-1D18A9856A87 last_name: Barton orcid: 0000-0002-8548-5240 citation: ama: 'Etheridge A, Barton NH. Data for: Establishment in a new habitat by polygenic adaptation. 2017. doi:10.17632/nw68fxzjpm.1' apa: 'Etheridge, A., & Barton, N. H. (2017). Data for: Establishment in a new habitat by polygenic adaptation. Mendeley Data. https://doi.org/10.17632/nw68fxzjpm.1' chicago: 'Etheridge, Alison, and Nicholas H Barton. “Data for: Establishment in a New Habitat by Polygenic Adaptation.” Mendeley Data, 2017. https://doi.org/10.17632/nw68fxzjpm.1.' ieee: 'A. Etheridge and N. H. Barton, “Data for: Establishment in a new habitat by polygenic adaptation.” Mendeley Data, 2017.' ista: 'Etheridge A, Barton NH. 2017. Data for: Establishment in a new habitat by polygenic adaptation, Mendeley Data, 10.17632/nw68fxzjpm.1.' mla: 'Etheridge, Alison, and Nicholas H. Barton. Data for: Establishment in a New Habitat by Polygenic Adaptation. Mendeley Data, 2017, doi:10.17632/nw68fxzjpm.1.' short: A. Etheridge, N.H. Barton, (2017). date_created: 2021-08-09T13:18:55Z date_published: 2017-12-29T00:00:00Z date_updated: 2023-09-11T13:41:21Z day: '29' department: - _id: NiBa doi: 10.17632/nw68fxzjpm.1 main_file_link: - open_access: '1' url: https://doi.org/10.17632/nw68fxzjpm.1 month: '12' oa: 1 oa_version: Published Version publisher: Mendeley Data related_material: record: - id: '564' relation: used_in_publication status: public status: public title: 'Data for: Establishment in a new habitat by polygenic adaptation' type: research_data_reference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf year: '2017' ... --- _id: '202' abstract: - lang: eng text: 'Restriction-modification (RM) represents the simplest and possibly the most widespread mechanism of self/non-self discrimination in nature. In order to provide bacteria with immunity against bacteriophages and other parasitic genetic elements, RM systems rely on a balance between two enzymes: the restriction enzyme, which cleaves non-self DNA at specific restriction sites, and the modification enzyme, which tags the host’s DNA as self and thus protects it from cleavage. In this thesis, I use population and single-cell level experiments in combination with mathematical modeling to study different aspects of the interplay between RM systems, bacteria and bacteriophages. First, I analyze how mutations in phage restriction sites affect the probability of phage escape – an inherently stochastic process, during which phages accidently get modified instead of restricted. Next, I use single-cell experiments to show that RM systems can, with a low probability, attack the genome of their bacterial host and that this primitive form of autoimmunity leads to a tradeoff between the evolutionary cost and benefit of RM systems. Finally, I investigate the nature of interactions between bacteria, RM systems and temperate bacteriophages to find that, as a consequence of phage escape and its impact on population dynamics, RM systems can promote acquisition of symbiotic bacteriophages, rather than limit it. The results presented here uncover new fundamental biological properties of RM systems and highlight their importance in the ecology and evolution of bacteria, bacteriophages and their interactions.' acknowledgement: "During my PhD studies, I received help from many people, all of which unfortunately cannot be listed here. I thank them deeply and hope that I never made them regret their kindness.\r\nI would like to express my deepest gratitude to Călin Guet, who went far beyond his responsibilities as an advisor and was to me also a great mentor and a friend. Călin never questioned my potential or lacked compassion and I cannot thank him enough for cultivating in me an independent scientist. I was amazed by his ability to recognize the most fascinating scientific problems in objects of study that others would find mundane. I hope I adopted at least a fraction of this ability.\r\nI will be forever grateful to Bruce Levin for all his support and especially for giving me the best possible example of how one can practice excellent science with humor and style. Working with Bruce was a true privilege.\r\nI thank Jonathan Bollback and Gašper Tkačik for serving in my PhD committee and the Austrian Academy of Science for funding my PhD research via the DOC fellowship.\r\nI thank all our lab members: Tobias Bergmiller for his guidance, especially in the first years of my research, and for being a good friend throughout; Remy Chait for staying in the lab at unreasonable hours and for the good laughs at bad jokes we shared; Anna Staron for supportively listening to my whines whenever I had to run a gel; Magdalena Steinrück for her pioneering work in the lab; Kathrin Tomasek for keeping the entropic forces in check and for her FACS virtuosity; Isabella Tomanek for always being nice to me, no matter how much bench space I took from her.\r\nI thank all my collaborators: Reiko Okura and Yuichi Wakamoto for performing and analyzing the microfluidic experiments; Long Qian and Edo Kussell for their bioinformatics analysis; Dominik Refardt for the λ kan phage; Moritz for his help with the mathematical modeling. I thank Fabienne Jesse for her tireless editorial work on all our manuscripts.\r\nFinally, I would like to thank my family and especially my wife Edita, who sacrificed a lot so that I can pursue my goals and dreams.\r\n" alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Maros full_name: Pleska, Maros id: 4569785E-F248-11E8-B48F-1D18A9856A87 last_name: Pleska orcid: 0000-0001-7460-7479 citation: ama: Pleska M. Biology of restriction-modification systems at the single-cell and population level. 2017. doi:10.15479/AT:ISTA:th_916 apa: Pleska, M. (2017). Biology of restriction-modification systems at the single-cell and population level. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_916 chicago: Pleska, Maros. “Biology of Restriction-Modification Systems at the Single-Cell and Population Level.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_916. ieee: M. Pleska, “Biology of restriction-modification systems at the single-cell and population level,” Institute of Science and Technology Austria, 2017. ista: Pleska M. 2017. Biology of restriction-modification systems at the single-cell and population level. Institute of Science and Technology Austria. mla: Pleska, Maros. Biology of Restriction-Modification Systems at the Single-Cell and Population Level. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_916. short: M. Pleska, Biology of Restriction-Modification Systems at the Single-Cell and Population Level, Institute of Science and Technology Austria, 2017. date_created: 2018-12-11T11:45:10Z date_published: 2017-10-01T00:00:00Z date_updated: 2023-09-15T12:04:56Z day: '01' ddc: - '576' - '579' degree_awarded: PhD department: - _id: CaGu doi: 10.15479/AT:ISTA:th_916 file: - access_level: open_access checksum: 33cfb59674e91f82e3738396d3fb3776 content_type: application/pdf creator: system date_created: 2018-12-12T10:08:48Z date_updated: 2020-07-14T12:45:24Z file_id: '4710' file_name: IST-2018-916-v1+3_2017_Pleska_Maros_Thesis.pdf file_size: 18569590 relation: main_file - access_level: closed checksum: dcc239968decb233e7f98cf1083d8c26 content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document creator: dernst date_created: 2019-04-05T08:33:14Z date_updated: 2020-07-14T12:45:24Z file_id: '6204' file_name: 2017_Pleska_Maros_Thesis.docx file_size: 2801649 relation: source_file file_date_updated: 2020-07-14T12:45:24Z has_accepted_license: '1' language: - iso: eng month: '10' oa: 1 oa_version: Published Version page: '126' project: - _id: 251D65D8-B435-11E9-9278-68D0E5697425 grant_number: '24210' name: Effects of Stochasticity on the Function of Restriction-Modi cation Systems at the Single-Cell Level (DOC Fellowship) publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria publist_id: '7711' pubrep_id: '916' related_material: record: - id: '1243' relation: part_of_dissertation status: public - id: '561' relation: part_of_dissertation status: public - id: '457' relation: part_of_dissertation status: public status: public supervisor: - first_name: Calin C full_name: Guet, Calin C id: 47F8433E-F248-11E8-B48F-1D18A9856A87 last_name: Guet orcid: 0000-0001-6220-2052 title: Biology of restriction-modification systems at the single-cell and population level tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2017' ... --- _id: '6287' abstract: - lang: eng text: The main objects considered in the present work are simplicial and CW-complexes with vertices forming a random point cloud. In particular, we consider a Poisson point process in R^n and study Delaunay and Voronoi complexes of the first and higher orders and weighted Delaunay complexes obtained as sections of Delaunay complexes, as well as the Čech complex. Further, we examine theDelaunay complex of a Poisson point process on the sphere S^n, as well as of a uniform point cloud, which is equivalent to the convex hull, providing a connection to the theory of random polytopes. Each of the complexes in question can be endowed with a radius function, which maps its cells to the radii of appropriately chosen circumspheres, called the radius of the cell. Applying and developing discrete Morse theory for these functions, joining it together with probabilistic and sometimes analytic machinery, and developing several integral geometric tools, we aim at getting the distributions of circumradii of typical cells. For all considered complexes, we are able to generalize and obtain up to constants the distribution of radii of typical intervals of all types. In low dimensions the constants can be computed explicitly, thus providing the explicit expressions for the expected numbers of cells. In particular, it allows to find the expected density of simplices of every dimension for a Poisson point process in R^4, whereas the result for R^3 was known already in 1970's. alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Anton full_name: Nikitenko, Anton id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87 last_name: Nikitenko orcid: 0000-0002-0659-3201 citation: ama: Nikitenko A. Discrete Morse theory for random complexes . 2017. doi:10.15479/AT:ISTA:th_873 apa: Nikitenko, A. (2017). Discrete Morse theory for random complexes . Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_873 chicago: Nikitenko, Anton. “Discrete Morse Theory for Random Complexes .” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_873. ieee: A. Nikitenko, “Discrete Morse theory for random complexes ,” Institute of Science and Technology Austria, 2017. ista: Nikitenko A. 2017. Discrete Morse theory for random complexes . Institute of Science and Technology Austria. mla: Nikitenko, Anton. Discrete Morse Theory for Random Complexes . Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_873. short: A. Nikitenko, Discrete Morse Theory for Random Complexes , Institute of Science and Technology Austria, 2017. date_created: 2019-04-09T15:04:32Z date_published: 2017-10-27T00:00:00Z date_updated: 2023-09-15T12:10:34Z day: '27' ddc: - '514' - '516' - '519' degree_awarded: PhD department: - _id: HeEd doi: 10.15479/AT:ISTA:th_873 file: - access_level: open_access checksum: ece7e598a2f060b263c2febf7f3fe7f9 content_type: application/pdf creator: dernst date_created: 2019-04-09T14:54:51Z date_updated: 2020-07-14T12:47:26Z file_id: '6289' file_name: 2017_Thesis_Nikitenko.pdf file_size: 2324870 relation: main_file - access_level: closed checksum: 99b7ad76e317efd447af60f91e29b49b content_type: application/zip creator: dernst date_created: 2019-04-09T14:54:51Z date_updated: 2020-07-14T12:47:26Z file_id: '6290' file_name: 2017_Thesis_Nikitenko_source.zip file_size: 2863219 relation: source_file file_date_updated: 2020-07-14T12:47:26Z has_accepted_license: '1' language: - iso: eng month: '10' oa: 1 oa_version: Published Version page: '86' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria pubrep_id: '873' related_material: record: - id: '718' relation: part_of_dissertation status: public - id: '5678' relation: part_of_dissertation status: public - id: '87' relation: part_of_dissertation status: public status: public supervisor: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 title: 'Discrete Morse theory for random complexes ' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2017' ...