@article{12142, abstract = {Theory for liability-scale models of the underlying genetic basis of complex disease provides an important way to interpret, compare, and understand results generated from biological studies. In particular, through estimation of the liability-scale heritability (LSH), liability models facilitate an understanding and comparison of the relative importance of genetic and environmental risk factors that shape different clinically important disease outcomes. Increasingly, large-scale biobank studies that link genetic information to electronic health records, containing hundreds of disease diagnosis indicators that mostly occur infrequently within the sample, are becoming available. Here, we propose an extension of the existing liability-scale model theory suitable for estimating LSH in biobank studies of low-prevalence disease. In a simulation study, we find that our derived expression yields lower mean square error (MSE) and is less sensitive to prevalence misspecification as compared to previous transformations for diseases with =< 2% population prevalence and LSH of =< 0.45, especially if the biobank sample prevalence is less than that of the wider population. Applying our expression to 13 diagnostic outcomes of =< 3% prevalence in the UK Biobank study revealed important differences in LSH obtained from the different theoretical expressions that impact the conclusions made when comparing LSH across disease outcomes. This demonstrates the importance of careful consideration for estimation and prediction of low-prevalence disease outcomes and facilitates improved inference of the underlying genetic basis of =< 2% population prevalence diseases, especially where biobank sample ascertainment results in a healthier sample population.}, author = {Ojavee, Sven E. and Kutalik, Zoltan and Robinson, Matthew Richard}, issn = {0002-9297}, journal = {The American Journal of Human Genetics}, keywords = {Genetics (clinical), Genetics}, number = {11}, pages = {2009--2017}, publisher = {Elsevier}, title = {{Liability-scale heritability estimation for biobank studies of low-prevalence disease}}, doi = {10.1016/j.ajhg.2022.09.011}, volume = {109}, year = {2022}, } @article{12151, abstract = {The k-sample G(k,W) from a graphon W:[0,1]2→[0,1] is the random graph on {1,…,k}, where we sample x1,…,xk∈[0,1] uniformly at random and make each pair {i,j}⊆{1,…,k} an edge with probability W(xi,xj), with all these choices being mutually independent. Let the random variable Xk(W) be the number of edges in G(k,W). Vera T. Sós asked in 2012 whether two graphons U, W are necessarily weakly isomorphic if the random variables Xk(U) and Xk(W) have the same distribution for every integer k≥2. This question when one of the graphons W is a constant function was answered positively by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós. Here we investigate the question when W is a 2-step graphon and prove that the answer is positive for a 3-dimensional family of such graphons. We also present some related results.}, author = {Cooley, Oliver and Kang, M. and Pikhurko, O.}, issn = {1588-2632}, journal = {Acta Mathematica Hungarica}, keywords = {graphon, k-sample, graphon forcing, graph container}, pages = {1--26}, publisher = {Springer Nature}, title = {{On a question of Vera T. Sós about size forcing of graphons}}, doi = {10.1007/s10474-022-01265-8}, volume = {168}, year = {2022}, } @inproceedings{12167, abstract = {Payment channels effectively move the transaction load off-chain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to “top up” funds on-chain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels off-chain. Protocols for rebalancing so far either introduce local solutions or compromise privacy. In this work, we present an opt-in rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multi-party computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentive-compatible cycles which conserve user balances when executed atomically.}, author = {Avarikioti, Georgia and Pietrzak, Krzysztof Z and Salem, Iosif and Schmid, Stefan and Tiwari, Samarth and Yeo, Michelle X}, booktitle = {Financial Cryptography and Data Security}, isbn = {9783031182822}, issn = {1611-3349}, location = {Grenada}, pages = {358--373}, publisher = {Springer Nature}, title = {{Hide & Seek: Privacy-preserving rebalancing on payment channel networks}}, doi = {10.1007/978-3-031-18283-9_17}, volume = {13411}, year = {2022}, } @inproceedings{12168, abstract = {Advances in blockchains have influenced the State-Machine-Replication (SMR) world and many state-of-the-art blockchain-SMR solutions are based on two pillars: Chaining and Leader-rotation. A predetermined round-robin mechanism used for Leader-rotation, however, has an undesirable behavior: crashed parties become designated leaders infinitely often, slowing down overall system performance. In this paper, we provide a new Leader-Aware SMR framework that, among other desirable properties, formalizes a Leader-utilization requirement that bounds the number of rounds whose leaders are faulty in crash-only executions. We introduce Carousel, a novel, reputation-based Leader-rotation solution to achieve Leader-Aware SMR. The challenge in adaptive Leader-rotation is that it cannot rely on consensus to determine a leader, since consensus itself needs a leader. Carousel uses the available on-chain information to determine a leader locally and achieves Liveness despite this difficulty. A HotStuff implementation fitted with Carousel demonstrates drastic performance improvements: it increases throughput over 2x in faultless settings and provided a 20x throughput increase and 5x latency reduction in the presence of faults.}, author = {Cohen, Shir and Gelashvili, Rati and Kokoris Kogias, Eleftherios and Li, Zekun and Malkhi, Dahlia and Sonnino, Alberto and Spiegelman, Alexander}, booktitle = {International Conference on Financial Cryptography and Data Security}, isbn = {9783031182822}, issn = {1611-3349}, location = {Grenada}, pages = {279--295}, publisher = {Springer Nature}, title = {{Be aware of your leaders}}, doi = {10.1007/978-3-031-18283-9_13}, volume = {13411}, year = {2022}, } @inproceedings{12170, abstract = {We present PET, a specialized and highly optimized framework for partial exploration on probabilistic systems. Over the last decade, several significant advances in the analysis of Markov decision processes employed partial exploration. In a nutshell, this idea allows to focus computation on specific parts of the system, guided by heuristics, while maintaining correctness. In particular, only relevant parts of the system are constructed on demand, which in turn potentially allows to omit constructing large parts of the system. Depending on the model, this leads to dramatic speed-ups, in extreme cases even up to an arbitrary factor. PET unifies several previous implementations and provides a flexible framework to easily implement partial exploration for many further problems. Our experimental evaluation shows significant improvements compared to the previous implementations while vastly reducing the overhead required to add support for additional properties.}, author = {Meggendorfer, Tobias}, booktitle = {20th International Symposium on Automated Technology for Verification and Analysis}, isbn = {9783031199912}, issn = {1611-3349}, location = {Virtual}, pages = {320--326}, publisher = {Springer Nature}, title = {{PET – A partial exploration tool for probabilistic verification}}, doi = {10.1007/978-3-031-19992-9_20}, volume = {13505}, year = {2022}, } @inproceedings{12171, abstract = {We propose an algorithmic approach for synthesizing linear hybrid automata from time-series data. Unlike existing approaches, our approach provides a whole family of models with the same discrete structure but different dynamics. Each model in the family is guaranteed to capture the input data up to a precision error ε, in the following sense: For each time series, the model contains an execution that is ε-close to the data points. Our construction allows to effectively choose a model from this family with minimal precision error ε. We demonstrate the algorithm’s efficiency and its ability to find precise models in two case studies.}, author = {Garcia Soto, Miriam and Henzinger, Thomas A and Schilling, Christian}, booktitle = {20th International Symposium on Automated Technology for Verification and Analysis}, isbn = {9783031199912}, issn = {1611-3349}, location = {Virtual}, pages = {337--353}, publisher = {Springer Nature}, title = {{Synthesis of parametric hybrid automata from time series}}, doi = {10.1007/978-3-031-19992-9_22}, volume = {13505}, year = {2022}, } @inproceedings{12175, abstract = {An automaton is history-deterministic (HD) if one can safely resolve its non-deterministic choices on the fly. In a recent paper, Henzinger, Lehtinen and Totzke studied this in the context of Timed Automata [9], where it was conjectured that the class of timed ω-languages recognised by HD-timed automata strictly extends that of deterministic ones. We provide a proof for this fact.}, author = {Bose, Sougata and Henzinger, Thomas A and Lehtinen, Karoliina and Schewe, Sven and Totzke, Patrick}, booktitle = {16th International Conference on Reachability Problems}, isbn = {9783031191343}, issn = {1611-3349}, location = {Kaiserslautern, Germany}, pages = {67--76}, publisher = {Springer Nature}, title = {{History-deterministic timed automata are not determinizable}}, doi = {10.1007/978-3-031-19135-0_5}, volume = {13608}, year = {2022}, } @inproceedings{12176, abstract = {A proof of exponentiation (PoE) in a group G of unknown order allows a prover to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive has recently found exciting applications in the constructions of verifiable delay functions and succinct arguments of knowledge. The most practical PoEs only achieve soundness either under computational assumptions, i.e., they are arguments (Wesolowski, Journal of Cryptology 2020), or in groups that come with the promise of not having any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in general groups of unknown order is due to Block et al. (CRYPTO 2021), and can be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits of security, say λ=80, the number of repetitions required (and thus the blow-up in communication) is as large as λ. In this work, we propose a statistically-sound PoE for the case where the exponent q is the product of all primes up to some bound B. We show that, in this case, it suffices to run only λ/log(B) parallel instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to Block et al. by an order of magnitude. Furthermore, we show that in the known applications where PoEs are used as a building block such structured exponents are viable. Finally, we also discuss batching of our PoE, showing that many proofs (for the same G and q but different x and T) can be batched by adding only a single element to the proof per additional statement.}, author = {Hoffmann, Charlotte and Hubáček, Pavel and Kamath, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, booktitle = {Advances in Cryptology – CRYPTO 2022}, isbn = {9783031159787}, issn = {1611-3349}, location = {Santa Barbara, CA, United States}, pages = {370--399}, publisher = {Springer Nature}, title = {{Practical statistically-sound proofs of exponentiation in any group}}, doi = {10.1007/978-3-031-15979-4_13}, volume = {13508}, year = {2022}, } @article{12226, abstract = {Background: Biases of DNA repair can shape the nucleotide landscape of genomes at evolutionary timescales. The molecular mechanisms of those biases are still poorly understood because it is difficult to isolate the contributions of DNA repair from those of DNA damage. Results: Here, we develop a genome-wide assay whereby the same DNA lesion is repaired in different genomic contexts. We insert thousands of barcoded transposons carrying a reporter of DNA mismatch repair in the genome of mouse embryonic stem cells. Upon inducing a double-strand break between tandem repeats, a mismatch is generated if the break is repaired through single-strand annealing. The resolution of the mismatch showed a 60–80% bias in favor of the strand with the longest 3′ flap. The location of the lesion in the genome and the type of mismatch had little influence on the bias. Instead, we observe a complete reversal of the bias when the longest 3′ flap is moved to the opposite strand by changing the position of the double-strand break in the reporter. Conclusions: These results suggest that the processing of the double-strand break has a major influence on the repair of mismatches during single-strand annealing.}, author = {Pokusaeva, Victoria and Diez, Aránzazu Rosado and Espinar, Lorena and Pérez, Albert Torelló and Filion, Guillaume J.}, issn = {1474-760X}, journal = {Genome Biology}, publisher = {Springer Nature}, title = {{Strand asymmetry influences mismatch resolution during single-strand annealing}}, doi = {10.1186/s13059-022-02665-3}, volume = {23}, year = {2022}, } @article{12227, abstract = {Polydicyclopentadiene (pDCPD), a thermoset with excellent mechanical properties, has enormous potential as a lightweight, tough, and stable matrix material owing to its highly cross-linked macromolecular network. This work describes generating pDCPD-based foams and hierarchically porous carbons derived therefrom by combining ring-opening metathesis polymerization (ROMP) of DCPD, high internal phase emulsions (HIPEs) as structural templates, and subsequent carbonization. The structure and function of the carbon foams were characterized and discussed in detail using scanning electron, transmission electron, or atomic force microscopy (SEM, TEM, AFM), electron energy-loss spectroscopy (TEM-EELS), N2 sorption, and analyses of electrical conductivity as well as mechanical properties. The resulting materials exhibited uniform, shape-retaining shrinkage of only ∼1/3 after carbonization. No structural failure was observed even when the pDCPD precursor foams were heated to 1400 °C. Instead, the high porosity, void size, and 3D interconnectivity were fully preserved, and the void diameters could be adjusted between 87 and 2.5 μm. Moreover, foams have a carbon content >97%, an electronic conductivity of up to 2800 S·m–1, a Young’s modulus of up to 2.1 GPa, and a specific surface area of up to 1200 m2·g–1. Surprisingly, the pDCPD foams were carbonized into shapes other than monoliths, such as 10’s of micron thick membranes or foamy coatings adhered to a metal foil or grid substrate. The latter coatings even adhere upon bending. Finally, as a use case, carbonized foams were applied as porous cathodes for Li–O2 batteries where the foams show a favorable combination of porosity, active surface area, and pore size for outstanding capacity.}, author = {Kovačič, Sebastijan and Schafzahl, Bettina and Matsko, Nadejda B. and Gruber, Katharina and Schmuck, Martin and Koller, Stefan and Freunberger, Stefan Alexander and Slugovc, Christian}, issn = {2574-0962}, journal = {ACS Applied Energy Materials}, keywords = {Electrical and Electronic Engineering, Materials Chemistry, Electrochemistry, Energy Engineering and Power Technology, Chemical Engineering (miscellaneous)}, number = {11}, pages = {14381--14390}, publisher = {American Chemical Society}, title = {{Carbon foams via ring-opening metathesis polymerization of emulsion templates: A facile method to make carbon current collectors for battery applications}}, doi = {10.1021/acsaem.2c02787}, volume = {5}, year = {2022}, } @article{12233, abstract = {A novel recursive list decoding (RLD) algorithm for Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. A low-complexity SP scheme applied to a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is integrated into an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, efficient latency and complexity reduction schemes are introduced that virtually preserve the error-correction performance of the proposed decoder. Simulation results demonstrate that at the target frame error rate of 10−3 for the RM code of length 256 with 163 information bits, the proposed decoder reduces 6% of the computational complexity and 22% of the decoding latency of the state-of-the-art semi-parallel simplified successive-cancellation decoder with fast Hadamard transform (SSC-FHT) that uses 96 permutations from the full symmetry group of RM codes, while relatively maintaining the error-correction performance and memory consumption of the semi-parallel permuted SSC-FHT decoder.}, author = {Doan, Nghia and Hashemi, Seyyed Ali and Mondelli, Marco and Gross, Warren J.}, issn = {1558-0857}, journal = {IEEE Transactions on Communications}, number = {11}, pages = {7134--7145}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Decoding Reed-Muller codes with successive codeword permutations}}, doi = {10.1109/tcomm.2022.3211101}, volume = {70}, year = {2022}, } @inproceedings{12298, abstract = {Existing committee-based Byzantine state machine replication (SMR) protocols, typically deployed in production blockchains, face a clear trade-off: (1) they either achieve linear communication cost in the steady state, but sacrifice liveness during periods of asynchrony, or (2) they are robust (progress with probability one) but pay quadratic communication cost. We believe this trade-off is unwarranted since existing linear protocols still have asymptotic quadratic cost in the worst case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds: optimal communication on and off the steady state (linear and quadratic, respectively) and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing the view-synchronization of partially synchronous protocols with an asynchronous fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff, a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which leverages a quadratic view-change mechanism to reduce the latency of the standard 3-chain HotStuff. We implement and experimentally evaluate all our systems to prove that breaking the robustness-efficiency trade-off is in the realm of practicality.}, author = {Gelashvili, Rati and Kokoris Kogias, Eleftherios and Sonnino, Alberto and Spiegelman, Alexander and Xiang, Zhuolun}, booktitle = {Financial Cryptography and Data Security}, isbn = {9783031182822}, issn = {1611-3349}, location = {Radisson Grenada Beach Resort, Grenada}, pages = {296--315}, publisher = {Springer Nature}, title = {{Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback}}, doi = {10.1007/978-3-031-18283-9_14}, volume = {13411}, year = {2022}, } @inproceedings{12300, abstract = {Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to t