TY - CONF
AB - Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 10004
KW - Computer science
KW - Heuristic algorithms
KW - Memory management
KW - Automata
KW - Markov processes
KW - Probability distribution
KW - Complexity theory
SN - 1043-6871
T2 - Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Stochastic processes with expected stopping time
ER -
TY - CONF
AB - In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.
AU - Henzinger, Thomas A
AU - Sarac, Naci E
ID - 10003
KW - Computer science
KW - Runtime
KW - Registers
KW - Time factors
KW - Monitoring
SN - 1043-6871
T2 - Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Quantitative and approximate monitoring
ER -
TY - JOUR
AB - In this paper, we introduce a random environment for the exclusion process in obtained by assigning a maximal occupancy to each site. This maximal occupancy is allowed to randomly vary among sites, and partial exclusion occurs. Under the assumption of ergodicity under translation and uniform ellipticity of the environment, we derive a quenched hydrodynamic limit in path space by strengthening the mild solution approach initiated in Nagy (2002) and Faggionato (2007). To this purpose, we prove, employing the technology developed for the random conductance model, a homogenization result in the form of an arbitrary starting point quenched invariance principle for a single particle in the same environment, which is a result of independent interest. The self-duality property of the partial exclusion process allows us to transfer this homogenization result to the particle system and, then, apply the tightness criterion in Redig et al. (2020).
AU - Floreani, Simone
AU - Redig, Frank
AU - Sau, Federico
ID - 10024
JF - Stochastic Processes and their Applications
KW - hydrodynamic limit
KW - random environment
KW - random conductance model
KW - arbitrary starting point quenched invariance principle
KW - duality
KW - mild solution
SN - 0304-4149
TI - Hydrodynamics for the partial exclusion process in random environment
VL - 142
ER -
TY - THES
AB - This thesis is the result of the research carried out by the author during his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich polaron model, specifically to its regime of strong coupling. This model, which is rigorously introduced and discussed in the introduction, has been of great interest in condensed matter physics and field theory for more than eighty years. It is used to describe an electron interacting with the atoms of a solid material (the strength of this interaction is modeled by the presence of a coupling constant α in the Hamiltonian of the system). The particular regime examined here, which is mathematically described by considering the limit α →∞, displays many interesting features related to the emergence of classical behavior, which allows for a simplified effective description of the system under analysis. The properties, the range of validity and a quantitative analysis of the precision of such classical approximations are the main object of the present work. We specify our investigation to the study of the ground state energy of the system, its dynamics and its effective mass. For each of these problems, we provide in the introduction an overview of the previously known results and a detailed account of the original contributions by the author.
AU - Feliciangeli, Dario
ID - 9733
SN - 2663-337X
TI - The polaron at strong coupling
ER -
TY - JOUR
AB - The developmental strategies used by progenitor cells to endure a safe journey from their induction place towards the site of terminal differentiation are still poorly understood. Here we uncovered a progenitor cell allocation mechanism that stems from an incomplete process of epithelial delamination that allows progenitors to coordinate their movement with adjacent extra-embryonic tissues. Progenitors of the zebrafish laterality organ originate from the surface epithelial enveloping layer by an apical constriction process of cell delamination. During this process, progenitors retain long-term apical contacts that enable the epithelial layer to pull a subset of progenitors along their way towards the vegetal pole. The remaining delaminated progenitors follow apically-attached progenitors’ movement by a co-attraction mechanism, avoiding sequestration by the adjacent endoderm, ensuring their fate and collective allocation at the differentiation site. Thus, we reveal that incomplete delamination serves as a cellular platform for coordinated tissue movements during development. Impact Statement: Incomplete delamination serves as a cellular platform for coordinated tissue movements during development, guiding newly formed progenitor cell groups to the differentiation site.
AU - Pulgar, Eduardo
AU - Schwayer, Cornelia
AU - Guerrero, Néstor
AU - López, Loreto
AU - Márquez, Susana
AU - Härtel, Steffen
AU - Soto, Rodrigo
AU - Heisenberg, Carl Philipp
AU - Concha, Miguel L.
ID - 9999
JF - eLife
KW - cell delamination
KW - apical constriction
KW - dragging
KW - mechanical forces
KW - collective 18 locomotion
KW - dorsal forerunner cells
KW - zebrafish
TI - Apical contacts stemming from incomplete delamination guide progenitor cell allocation through a dragging mechanism
VL - 10
ER -
TY - JOUR
AB - We study the temporal dissipation of variance and relative entropy for ergodic Markov Chains in continuous time, and compute explicitly the corresponding dissipation rates. These are identified, as is well known, in the case of the variance in terms of an appropriate Hilbertian norm; and in the case of the relative entropy, in terms of a Dirichlet form which morphs into a version of the familiar Fisher information under conditions of detailed balance. Here we obtain trajectorial versions of these results, valid along almost every path of the random motion and most transparent in the backwards direction of time. Martingale arguments and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer and Tschiderer for conservative diffusions. Extensions are developed to general “convex divergences” and to countable state-spaces. The steepest descent and gradient flow properties for the variance, the relative entropy, and appropriate generalizations, are studied along with their respective geometries under conditions of detailed balance, leading to a very direct proof for the HWI inequality of Otto and Villani in the present context.
AU - Karatzas, Ioannis
AU - Maas, Jan
AU - Schachermayer, Walter
ID - 10023
IS - 4
JF - Communications in Information and Systems
KW - Markov Chain
KW - relative entropy
KW - time reversal
KW - steepest descent
KW - gradient flow
SN - 1526-7555
TI - Trajectorial dissipation and gradient flow for the relative entropy in Markov chains
VL - 21
ER -
TY - JOUR
AB - The ⊗*-monoidal structure on the category of sheaves on the Ran space is not pro-nilpotent in the sense of [3]. However, under some connectivity assumptions, we prove that Koszul duality induces an equivalence of categories and that this equivalence behaves nicely with respect to Verdier duality on the Ran space and integrating along the Ran space, i.e. taking factorization homology. Based on ideas sketched in [4], we show that these results also offer a simpler alternative to one of the two main steps in the proof of the Atiyah-Bott formula given in [7] and [5].
AU - Ho, Quoc P
ID - 10033
JF - Advances in Mathematics
KW - Chiral algebras
KW - Chiral homology
KW - Factorization algebras
KW - Koszul duality
KW - Ran space
SN - 0001-8708
TI - The Atiyah-Bott formula and connectivity in chiral Koszul duality
VL - 392
ER -
TY - JOUR
AB - The control of nonequilibrium quantum dynamics in many-body systems is challenging because interactions typically lead to thermalization and a chaotic spreading throughout Hilbert space. We investigate nonequilibrium dynamics after rapid quenches in a many-body system composed of 3 to 200 strongly interacting qubits in one and two spatial dimensions. Using a programmable quantum simulator based on Rydberg atom arrays, we show that coherent revivals associated with so-called quantum many-body scars can be stabilized by periodic driving, which generates a robust subharmonic response akin to discrete time-crystalline order. We map Hilbert space dynamics, geometry dependence, phase diagrams, and system-size dependence of this emergent phenomenon, demonstrating new ways to steer complex dynamics in many-body systems and enabling potential applications in quantum information science.
AU - Bluvstein, D.
AU - Omran, A.
AU - Levine, H.
AU - Keesling, A.
AU - Semeghini, G.
AU - Ebadi, S.
AU - Wang, T. T.
AU - Michailidis, Alexios
AU - Maskara, N.
AU - Ho, W. W.
AU - Choi, S.
AU - Serbyn, Maksym
AU - Greiner, M.
AU - Vuletić, V.
AU - Lukin, M. D.
ID - 9618
IS - 6536
JF - Science
KW - Multidisciplinary
SN - 0036-8075
TI - Controlling quantum many-body dynamics in driven Rydberg atom arrays
VL - 371
ER -
TY - JOUR
AB - SnSe has emerged as one of the most promising materials for thermoelectric energy conversion due to its extraordinary performance in its single-crystal form and its low-cost constituent elements. However, to achieve an economic impact, the polycrystalline counterpart needs to replicate the performance of the single crystal. Herein, we optimize the thermoelectric performance of polycrystalline SnSe produced by consolidating solution-processed and surface-engineered SnSe particles. In particular, the SnSe particles are coated with CdSe molecular complexes that crystallize during the sintering process, forming CdSe nanoparticles. The presence of CdSe nanoparticles inhibits SnSe grain growth during the consolidation step due to Zener pinning, yielding a material with a high density of grain boundaries. Moreover, the resulting SnSe–CdSe nanocomposites present a large number of defects at different length scales, which significantly reduce the thermal conductivity. The produced SnSe–CdSe nanocomposites exhibit thermoelectric figures of merit up to 2.2 at 786 K, which is among the highest reported for solution-processed SnSe.
AU - Liu, Yu
AU - Calcabrini, Mariano
AU - Yu, Yuan
AU - LEE, Seungho
AU - Chang, Cheng
AU - David, Jérémy
AU - Ghosh, Tanmoy
AU - Spadaro, Maria Chiara
AU - Xie, Chenyang
AU - Cojocaru-Mirédin, Oana
AU - Arbiol, Jordi
AU - Ibáñez, Maria
ID - 10042
JF - ACS Nano
KW - tin selenide
KW - nanocomposite
KW - grain growth
KW - Zener pinning
KW - thermoelectricity
KW - annealing
KW - solution processing
SN - 1936-0851
TI - Defect engineering in solution-processed polycrystalline SnSe leads to high thermoelectric performance
ER -
TY - THES
AB - This PhD thesis is primarily focused on the study of discrete transport problems, introduced for the first time in the seminal works of Maas [Maa11] and Mielke [Mie11] on finite state Markov chains and reaction-diffusion equations, respectively. More in detail, my research focuses on the study of transport costs on graphs, in particular the convergence and the stability of such problems in the discrete-to-continuum limit. This thesis also includes some results concerning
non-commutative optimal transport. The first chapter of this thesis consists of a general introduction to the optimal transport problems, both in the discrete, the continuous, and the non-commutative setting. Chapters 2 and 3 present the content of two works, obtained in collaboration with Peter Gladbach, Eva Kopfer, and Jan Maas, where we have been able to show the convergence of discrete transport costs on periodic graphs to suitable continuous ones, which can be described by means of a homogenisation result. We first focus on the particular case of quadratic costs on the real line and then extending the result to more general costs in arbitrary dimension. Our results are the first complete characterisation of limits of transport costs on periodic graphs in arbitrary dimension which do not rely on any additional symmetry. In Chapter 4 we turn our attention to one of the intriguing connection between evolution equations and optimal transport, represented by the theory of gradient flows. We show that discrete gradient flow structures associated to a finite volume approximation of a certain class of diffusive equations (Fokker–Planck) is stable in the limit of vanishing meshes, reproving the convergence of the scheme via the method of evolutionary Γ-convergence and exploiting a more variational point of view on the problem. This is based on a collaboration with Dominik Forkert and Jan Maas. Chapter 5 represents a change of perspective, moving away from the discrete world and reaching the non-commutative one. As in the discrete case, we discuss how classical tools coming from the commutative optimal transport can be translated into the setting of density matrices. In particular, in this final chapter we present a non-commutative version of the Schrödinger problem (or entropic regularised optimal transport problem) and discuss existence and characterisation of minimisers, a duality result, and present a non-commutative version of the well-known Sinkhorn algorithm to compute the above mentioned optimisers. This is based on a joint work with Dario Feliciangeli and Augusto Gerolin. Finally, Appendix A and B contain some additional material and discussions, with particular attention to Harnack inequalities and the regularity of flows on discrete spaces.
AU - Portinale, Lorenzo
ID - 10030
SN - 2663-337X
TI - Discrete-to-continuum limits of transport problems and gradient flows in the space of measures
ER -
TY - GEN
AB - Given a fixed finite metric space (V,μ), the {\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.
AU - Dvorak, Martin
AU - Kolmogorov, Vladimir
ID - 10045
KW - minimum 0-extension problem
KW - metric labeling problem
KW - discrete metric spaces
KW - metric extensions
KW - computational complexity
KW - valued constraint satisfaction problems
KW - discrete convex analysis
KW - L-convex functions
T2 - arXiv
TI - Generalized minimum 0-extension problem and discrete convexity
ER -
TY - GEN
AB - This paper establishes new connections between many-body quantum systems, One-body Reduced Density Matrices Functional Theory (1RDMFT) and Optimal Transport (OT), by interpreting the problem of computing the ground-state energy of a finite dimensional composite quantum system at positive temperature as a non-commutative entropy regularized Optimal Transport problem. We develop a new approach to fully characterize the dual-primal solutions in such non-commutative setting. The mathematical formalism is particularly relevant in quantum chemistry: numerical realizations of the many-electron ground state energy can be computed via a non-commutative version of Sinkhorn algorithm. Our approach allows to prove convergence and robustness of this algorithm, which, to our best knowledge, were unknown even in the two marginal case. Our methods are based on careful a priori estimates in the dual problem, which we believe to be of independent interest. Finally, the above results are extended in 1RDMFT setting, where bosonic or fermionic symmetry conditions are enforced on the problem.
AU - Feliciangeli, Dario
AU - Gerolin, Augusto
AU - Portinale, Lorenzo
ID - 9792
T2 - arXiv
TI - A non-commutative entropic optimal transport approach to quantum composite systems at positive temperature
ER -
TY - CONF
AB - Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth δ , the loss in security is at most exponential in δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ID - 10041
SN - 0302-9743
T2 - 41st Annual International Cryptology Conference, Part II
TI - Limits on the Adaptive Security of Yao’s Garbling
VL - 12826
ER -
TY - JOUR
AB - Aprotic alkali metal–O2 batteries face two major obstacles to their chemistry occurring efficiently, the insulating nature of the formed alkali superoxides/peroxides and parasitic reactions that are caused by the highly reactive singlet oxygen (1O2). Redox mediators are recognized to be key for improving rechargeability. However, it is unclear how they affect 1O2 formation, which hinders strategies for their improvement. Here we clarify the mechanism of mediated peroxide and superoxide oxidation and thus explain how redox mediators either enhance or suppress 1O2 formation. We show that charging commences with peroxide oxidation to a superoxide intermediate and that redox potentials above ~3.5 V versus Li/Li+ drive 1O2 evolution from superoxide oxidation, while disproportionation always generates some 1O2. We find that 1O2 suppression requires oxidation to be faster than the generation of 1O2 from disproportionation. Oxidation rates decrease with growing driving force following Marcus inverted-region behaviour, establishing a region of maximum rate.
AU - Petit, Yann K.
AU - Mourad, Eléonore
AU - Prehal, Christian
AU - Leypold, Christian
AU - Windischbacher, Andreas
AU - Mijailovic, Daniel
AU - Slugovc, Christian
AU - Borisov, Sergey M.
AU - Zojer, Egbert
AU - Brutti, Sergio
AU - Fontaine, Olivier
AU - Freunberger, Stefan Alexander
ID - 9250
IS - 5
JF - Nature Chemistry
KW - General Chemistry
KW - General Chemical Engineering
SN - 1755-4330
TI - Mechanism of mediated alkali peroxide oxidation and triplet versus singlet oxygen formation
VL - 13
ER -
TY - THES
AB - Blood – this is what animals use to heal wounds fast and efficient. Plants do not have blood circulation and their cells cannot move. However, plants have evolved remarkable capacities to regenerate tissues and organs preventing further damage. In my PhD research, I studied the wound healing in the Arabidopsis root. I used a UV laser to ablate single cells in the root tip and observed the consequent wound healing. Interestingly, the inner adjacent cells induced a
division plane switch and subsequently adopted the cell type of the killed cell to replace it. We termed this form of wound healing “restorative divisions”. This initial observation triggered the questions of my PhD studies: How and why do cells orient their division planes, how do they feel the wound and why does this happen only in inner adjacent cells.
For answering these questions, I used a quite simple experimental setup: 5 day - old seedlings were stained with propidium iodide to visualize cell walls and dead cells; ablation was carried out using a special laser cutter and a confocal microscope. Adaptation of the novel vertical microscope system made it possible to observe wounds in real time. This revealed that restorative divisions occur at increased frequency compared to normal divisions. Additionally,
the major plant hormone auxin accumulates in wound adjacent cells and drives the expression of the wound-stress responsive transcription factor ERF115. Using this as a marker gene for wound responses, we found that an important part of wound signalling is the sensing of the collapse of the ablated cell. The collapse causes a radical pressure drop, which results in strong tissue deformations. These deformations manifest in an invasion of the now free spot specifically by the inner adjacent cells within seconds, probably because of higher pressure of the inner tissues. Long-term imaging revealed that those deformed cells continuously expand towards the wound hole and that this is crucial for the restorative division. These wound-expanding cells exhibit an abnormal, biphasic polarity of microtubule arrays
before the division. Experiments inhibiting cell expansion suggest that it is the biphasic stretching that induces those MT arrays. Adapting the micromanipulator aspiration system from animal scientists at our institute confirmed the hypothesis that stretching influences microtubule stability. In conclusion, this shows that microtubules react to tissue deformation
and this facilitates the observed division plane switch. This puts mechanical cues and tensions at the most prominent position for explaining the growth and wound healing properties of plants. Hence, it shines light onto the importance of understanding mechanical signal transduction.
AU - Hörmayer, Lukas
ID - 9992
SN - 2663-337X
TI - Wound healing in the Arabidopsis root meristem
ER -
TY - CONF
AB - While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.
AU - Klein, Karen
AU - Pascual Perez, Guillermo
AU - Walter, Michael
AU - Kamath Hosdurg, Chethan
AU - Capretto, Margarita
AU - Cueto Noval, Miguel
AU - Markov, Ilia
AU - Yeo, Michelle X
AU - Alwen, Joel F
AU - Pietrzak, Krzysztof Z
ID - 10049
T2 - 2021 IEEE Symposium on Security and Privacy
TI - Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement
ER -
TY - CONF
AB - The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical
framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower
bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and
broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
AU - Walter, Michael
ID - 10048
T2 - 19th Theory of Cryptography Conference 2021
TI - The cost of adaptivity in security games on graphs
ER -
TY - CONF
AB - We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
ID - 10044
T2 - 19th Theory of Cryptography Conference 2021
TI - On treewidth, separators and Yao's garbling
ER -
TY - JOUR
AB - When short-range attractions are combined with long-range repulsions in colloidal particle systems, complex microphases can emerge. Here, we study a system of isotropic particles, which can form lamellar structures or a disordered fluid phase when temperature is varied. We show that, at equilibrium, the lamellar structure crystallizes, while out of equilibrium, the system forms a variety of structures at different shear rates and temperatures above melting. The shear-induced ordering is analyzed by means of principal component analysis and artificial neural networks, which are applied to data of reduced dimensionality. Our results reveal the possibility of inducing ordering by shear, potentially providing a feasible route to the fabrication of ordered lamellar structures from isotropic particles.
AU - Pȩkalski, J.
AU - Rzadkowski, Wojciech
AU - Panagiotopoulos, A. Z.
ID - 7956
IS - 20
JF - The Journal of chemical physics
TI - Shear-induced ordering in systems with competing interactions: A machine learning study
VL - 152
ER -
TY - JOUR
AB - Neurodevelopmental disorders (NDDs) are a class of disorders affecting brain development and function and are characterized by wide genetic and clinical variability. In this review, we discuss the multiple factors that influence the clinical presentation of NDDs, with particular attention to gene vulnerability, mutational load, and the two-hit model. Despite the complex architecture of
mutational events associated with NDDs, the various proteins involved appear to converge on common pathways, such as synaptic plasticity/function, chromatin remodelers and the mammalian target of rapamycin (mTOR) pathway. A thorough understanding of the mechanisms behind these pathways will hopefully lead to the identification of candidates that could be targeted for treatment approaches.
AU - Parenti, Ilaria
AU - Garcia Rabaneda, Luis E
AU - Schön, Hanna
AU - Novarino, Gaia
ID - 7957
IS - 8
JF - Trends in Neurosciences
SN - 01662236
TI - Neurodevelopmental disorders: From genetics to functional pathways
VL - 43
ER -
TY - JOUR
AB - Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces.
AU - Kalai, Gil
AU - Patakova, Zuzana
ID - 7960
JF - Discrete and Computational Geometry
SN - 01795376
TI - Intersection patterns of planar sets
VL - 64
ER -
TY - JOUR
AB - A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge (n→∞). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.
AU - Pach, János
AU - Reed, Bruce
AU - Yuditsky, Yelena
ID - 7962
IS - 4
JF - Discrete and Computational Geometry
SN - 01795376
TI - Almost all string graphs are intersection graphs of plane convex sets
VL - 63
ER -
TY - CONF
AB - For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, SF, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).
For Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor SF=m; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor SF=√m. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.
As our main technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n Gap Computational Diffie-Hellman problem over groups of prime order p, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem.
AU - Auerbach, Benedikt
AU - Giacon, Federico
AU - Kiltz, Eike
ID - 7966
SN - 0302-9743
T2 - Advances in Cryptology – EUROCRYPT 2020
TI - Everybody’s a target: Scalability in public-key encryption
VL - 12107
ER -
TY - JOUR
AB - Organic materials are known to feature long spin-diffusion times, originating in a generally small spin–orbit coupling observed in these systems. From that perspective, chiral molecules acting as efficient spin selectors pose a puzzle that attracted a lot of attention in recent years. Here, we revisit the physical origins of chiral-induced spin selectivity (CISS) and propose a simple analytic minimal model to describe it. The model treats a chiral molecule as an anisotropic wire with molecular dipole moments aligned arbitrarily with respect to the wire’s axes and is therefore quite general. Importantly, it shows that the helical structure of the molecule is not necessary to observe CISS and other chiral nonhelical molecules can also be considered as potential candidates for the CISS effect. We also show that the suggested simple model captures the main characteristics of CISS observed in the experiment, without the need for additional constraints employed in the previous studies. The results pave the way for understanding other related physical phenomena where the CISS effect plays an essential role.
AU - Ghazaryan, Areg
AU - Paltiel, Yossi
AU - Lemeshko, Mikhail
ID - 7968
IS - 21
JF - The Journal of Physical Chemistry C
SN - 1932-7447
TI - Analytic model of chiral-induced spin selectivity
VL - 124
ER -
TY - JOUR
AB - Multilayer graphene lattices allow for an additional tunability of the band structure by the strong perpendicular electric field. In particular, the emergence of the new multiple Dirac points in ABA stacked trilayer graphene subject to strong transverse electric fields was proposed theoretically and confirmed experimentally. These new Dirac points dubbed “gullies” emerge from the interplay between strong electric field and trigonal warping. In this work, we first characterize the properties of new emergent Dirac points and show that the electric field can be used to tune the distance between gullies in the momentum space. We demonstrate that the band structure has multiple Lifshitz transitions and higher-order singularity of “monkey saddle” type. Following the characterization of the band structure, we consider the spectrum of Landau levels and structure of their wave functions. In the limit of strong electric fields when gullies are well separated in momentum space, they give rise to triply degenerate Landau levels. In the second part of this work, we investigate how degeneracy between three gully Landau levels is lifted in the presence of interactions. Within the Hartree-Fock approximation we show that the symmetry breaking state interpolates between the fully gully polarized state that breaks C3 symmetry at high displacement field and the gully symmetric state when the electric field is decreased. The discontinuous transition between these two states is driven by enhanced intergully tunneling and exchange. We conclude by outlining specific experimental predictions for the existence of such a symmetry-breaking state.
AU - Rao, Peng
AU - Serbyn, Maksym
ID - 7971
IS - 24
JF - Physical Review B
SN - 2469-9950
TI - Gully quantum Hall ferromagnetism in biased trilayer graphene
VL - 101
ER -
TY - JOUR
AB - The goal of limiting global warming to 1.5 °C requires a drastic reduction in CO2 emissions across many sectors of the world economy. Batteries are vital to this endeavor, whether used in electric vehicles, to store renewable electricity, or in aviation. Present lithium-ion technologies are preparing the public for this inevitable change, but their maximum theoretical specific capacity presents a limitation. Their high cost is another concern for commercial viability. Metal–air batteries have the highest theoretical energy density of all possible secondary battery technologies and could yield step changes in energy storage, if their practical difficulties could be overcome. The scope of this review is to provide an objective, comprehensive, and authoritative assessment of the intensive work invested in nonaqueous rechargeable metal–air batteries over the past few years, which identified the key problems and guides directions to solve them. We focus primarily on the challenges and outlook for Li–O2 cells but include Na–O2, K–O2, and Mg–O2 cells for comparison. Our review highlights the interdisciplinary nature of this field that involves a combination of materials chemistry, electrochemistry, computation, microscopy, spectroscopy, and surface science. The mechanisms of O2 reduction and evolution are considered in the light of recent findings, along with developments in positive and negative electrodes, electrolytes, electrocatalysis on surfaces and in solution, and the degradative effect of singlet oxygen, which is typically formed in Li–O2 cells.
AU - Kwak, WJ
AU - Sharon, D
AU - Xia, C
AU - Kim, H
AU - Johnson, LR
AU - Bruce, PG
AU - Nazar, LF
AU - Sun, YK
AU - Frimer, AA
AU - Noked, M
AU - Freunberger, Stefan Alexander
AU - Aurbach, D
ID - 7985
IS - 14
JF - Chemical Reviews
SN - 0009-2665
TI - Lithium-oxygen batteries and related systems: Potential, status, and future
VL - 120
ER -
TY - CONF
AB - We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface.
AU - Patakova, Zuzana
ID - 7989
SN - 18688969
T2 - 36th International Symposium on Computational Geometry
TI - Bounding radon number via Betti numbers
VL - 164
ER -
TY - CONF
AB - Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).
AU - Wagner, Uli
AU - Welzl, Emo
ID - 7990
SN - 18688969
T2 - 36th International Symposium on Computational Geometry
TI - Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)
VL - 164
ER -
TY - CONF
AB - We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
AU - Avvakumov, Sergey
AU - Nivasch, Gabriel
ID - 7991
SN - 18688969
T2 - 36th International Symposium on Computational Geometry
TI - Homotopic curve shortening and the affine curve-shortening flow
VL - 164
ER -
TY - CONF
AB - Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 7992
SN - 18688969
T2 - 36th International Symposium on Computational Geometry
TI - Barycentric cuts through a convex body
VL - 164
ER -
TY - CONF
AB - In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.
AU - Arroyo Guevara, Alan M
AU - Bensmail, Julien
AU - Bruce Richter, R.
ID - 7994
SN - 18688969
T2 - 36th International Symposium on Computational Geometry
TI - Extending drawings of graphs to arrangements of pseudolines
VL - 164
ER -
TY - JOUR
AB - When divergent populations are connected by gene flow, the establishment of complete reproductive isolation usually requires the joint action of multiple barrier effects. One example where multiple barrier effects are coupled consists of a single trait that is under divergent natural selection and also mediates assortative mating. Such multiple‐effect traits can strongly reduce gene flow. However, there are few cases where patterns of assortative mating have been described quantitatively and their impact on gene flow has been determined. Two ecotypes of the coastal marine snail, Littorina saxatilis , occur in North Atlantic rocky‐shore habitats dominated by either crab predation or wave action. There is evidence for divergent natural selection acting on size, and size‐assortative mating has previously been documented. Here, we analyze the mating pattern in L. saxatilis with respect to size in intensively sampled transects across boundaries between the habitats. We show that the mating pattern is mostly conserved between ecotypes and that it generates both assortment and directional sexual selection for small male size. Using simulations, we show that the mating pattern can contribute to reproductive isolation between ecotypes but the barrier to gene flow is likely strengthened more by sexual selection than by assortment.
AU - Perini, Samuel
AU - Rafajlović, Marina
AU - Westram, Anja M
AU - Johannesson, Kerstin
AU - Butlin, Roger K.
ID - 7995
IS - 7
JF - Evolution
SN - 00143820
TI - Assortative mating, sexual selection, and their consequences for gene flow in Littorina
VL - 74
ER -
TY - THES
AB - Quantum computation enables the execution of algorithms that have exponential complexity. This might open the path towards the synthesis of new materials or medical drugs, optimization of transport or financial strategies etc., intractable on even the fastest classical computers. A quantum computer consists of interconnected two level quantum systems, called qubits, that satisfy DiVincezo’s criteria. Worldwide, there are ongoing efforts to find the qubit architecture which will unite quantum error correction compatible single and two qubit fidelities, long distance qubit to qubit coupling and
calability. Superconducting qubits have gone the furthest in this race, demonstrating an algorithm running on 53 coupled qubits, but still the fidelities are not even close to those required for realizing a single logical qubit. emiconductor qubits offer extremely good characteristics, but they are currently investigated across different platforms. Uniting those good characteristics into a single platform might be a big step towards the quantum computer realization.
Here we describe the implementation of a hole spin qubit hosted in a Ge hut wire double quantum dot. The high and tunable spin-orbit coupling together with a heavy hole state character is expected to allow fast spin manipulation and long coherence times. Furthermore large lever arms, for hut wire devices, should allow good coupling to superconducting resonators enabling efficient long distance spin to spin coupling and a sensitive gate reflectometry spin readout. The developed cryogenic setup (printed circuit board sample holders, filtering, high-frequency wiring) enabled us to perform low temperature spin dynamics experiments. Indeed, we measured the fastest single spin qubit Rabi frequencies reported so far, reaching 140 MHz, while the dephasing times of 130 ns oppose the long decoherence predictions. In order to further investigate this, a double quantum dot gate was connected directly to a lumped element
resonator which enabled gate reflectometry readout. The vanishing inter-dot transition signal, for increasing external magnetic field, revealed the spin nature of the measured quantity.
AU - Kukucka, Josip
ID - 7996
TI - Implementation of a hole spin qubit in Ge hut wires and dispersive spin sensing
ER -
TY - JOUR
AB - Linking epigenetic marks to clinical outcomes improves insight into molecular processes, disease prediction, and therapeutic target identification. Here, a statistical approach is presented to infer the epigenetic architecture of complex disease, determine the variation captured by epigenetic effects, and estimate phenotype-epigenetic probe associations jointly. Implicitly adjusting for probe correlations, data structure (cell-count or relatedness), and single-nucleotide polymorphism (SNP) marker effects, improves association estimates and in 9,448 individuals, 75.7% (95% CI 71.70–79.3) of body mass index (BMI) variation and 45.6% (95% CI 37.3–51.9) of cigarette consumption variation was captured by whole blood methylation array data. Pathway-linked probes of blood cholesterol, lipid transport and sterol metabolism for BMI, and xenobiotic stimuli response for smoking, showed >1.5 times larger associations with >95% posterior inclusion probability. Prediction accuracy improved by 28.7% for BMI and 10.2% for smoking over a LASSO model, with age-, and tissue-specificity, implying associations are a phenotypic consequence rather than causal.
AU - Trejo Banos, D
AU - McCartney, DL
AU - Patxot, M
AU - Anchieri, L
AU - Battram, T
AU - Christiansen, C
AU - Costeira, R
AU - Walker, RM
AU - Morris, SW
AU - Campbell, A
AU - Zhang, Q
AU - Porteous, DJ
AU - McRae, AF
AU - Wray, NR
AU - Visscher, PM
AU - Haley, CS
AU - Evans, KL
AU - Deary, IJ
AU - McIntosh, AM
AU - Hemani, G
AU - Bell, JT
AU - Marioni, RE
AU - Robinson, Matthew Richard
ID - 7999
JF - Nature Communications
SN - 2041-1723
TI - Bayesian reassessment of the epigenetic architecture of complex traits
VL - 11
ER -
TY - JOUR
AB - Post-tetanic potentiation (PTP) is an attractive candidate mechanism for hippocampus-dependent short-term memory. Although PTP has a uniquely large magnitude at hippocampal mossy fiber-CA3 pyramidal neuron synapses, it is unclear whether it can be induced by natural activity and whether its lifetime is sufficient to support short-term memory. We combined in vivo recordings from granule cells (GCs), in vitro paired recordings from mossy fiber terminals and postsynaptic CA3 neurons, and “flash and freeze” electron microscopy. PTP was induced at single synapses and showed a low induction threshold adapted to sparse GC activity in vivo. PTP was mainly generated by enlargement of the readily releasable pool of synaptic vesicles, allowing multiplicative interaction with other plasticity forms. PTP was associated with an increase in the docked vesicle pool, suggesting formation of structural “pool engrams.” Absence of presynaptic activity extended the lifetime of the potentiation, enabling prolonged information storage in the hippocampal network.
AU - Vandael, David H
AU - Borges Merjane, Carolina
AU - Zhang, Xiaomin
AU - Jonas, Peter M
ID - 8001
IS - 3
JF - Neuron
SN - 0896-6273
TI - Short-term plasticity at hippocampal mossy fiber synapses is induced by natural activity patterns and associated with vesicle pool engram formation
VL - 107
ER -
TY - JOUR
AB - Relaxation to a thermal state is the inevitable fate of nonequilibrium interacting quantum systems without special conservation laws. While thermalization in one-dimensional systems can often be suppressed by integrability mechanisms, in two spatial dimensions thermalization is expected to be far more effective due to the increased phase space. In this work we propose a general framework for escaping or delaying the emergence of the thermal state in two-dimensional arrays of Rydberg atoms via the mechanism of quantum scars, i.e., initial states that fail to thermalize. The suppression of thermalization is achieved in two complementary ways: by adding local perturbations or by adjusting the driving Rabi frequency according to the local connectivity of the lattice. We demonstrate that these mechanisms allow us to realize robust quantum scars in various two-dimensional lattices, including decorated lattices with nonconstant connectivity. In particular, we show that a small decrease of the Rabi frequency at the corners of the lattice is crucial for mitigating the strong boundary effects in two-dimensional systems. Our results identify synchronization as an important tool for future experiments on two-dimensional quantum scars.
AU - Michailidis, Alexios
AU - Turner, C. J.
AU - Papić, Z.
AU - Abanin, D. A.
AU - Serbyn, Maksym
ID - 8011
IS - 2
JF - Physical Review Research
SN - 2643-1564
TI - Stabilizing two-dimensional quantum scars by deformation and synchronization
VL - 2
ER -
TY - CONF
AB - Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce inductive sequentialization, a new proof rule that sidesteps this complexity via a sequential reduction, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos.
AU - Kragl, Bernhard
AU - Enea, Constantin
AU - Henzinger, Thomas A
AU - Mutluergil, Suha Orhun
AU - Qadeer, Shaz
ID - 8012
SN - 9781450376136
T2 - Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation
TI - Inductive sequentialization of asynchronous programs
ER -
TY - THES
AB - Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”
In this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus.
AU - Huszár, Kristóf
ID - 8032
SN - 2663-337X
TI - Combinatorial width parameters for 3-dimensional manifolds
ER -
TY - JOUR
AB - When tiny soft ferromagnetic particles are placed along a liquid interface and exposed to a vertical magnetic field, the balance between capillary attraction and magnetic repulsion leads to self-organization into well-defined patterns. Here, we demonstrate experimentally that precessing magnetic fields induce metachronal waves on the periphery of these assemblies, similar to the ones observed in ciliates and some arthropods. The outermost layer of particles behaves like an array of cilia or legs whose sequential movement causes a net and controllable locomotion. This bioinspired many-particle swimming strategy is effective even at low Reynolds number, using only spatially uniform fields to generate the waves.
AU - Collard, Ylona
AU - Grosjean, Galien M
AU - Vandewalle, Nicolas
ID - 8036
JF - Communications Physics
TI - Magnetically powered metachronal waves induce locomotion in self-assemblies
VL - 3
ER -
TY - JOUR
AB - Genetic perturbations that affect bacterial resistance to antibiotics have been characterized genome-wide, but how do such perturbations interact with subsequent evolutionary adaptation to the drug? Here, we show that strong epistasis between resistance mutations and systematically identified genes can be exploited to control spontaneous resistance evolution. We evolved hundreds of Escherichia coli K-12 mutant populations in parallel, using a robotic platform that tightly controls population size and selection pressure. We find a global diminishing-returns epistasis pattern: strains that are initially more sensitive generally undergo larger resistance gains. However, some gene deletion strains deviate from this general trend and curtail the evolvability of resistance, including deletions of genes for membrane transport, LPS biosynthesis, and chaperones. Deletions of efflux pump genes force evolution on inferior mutational paths, not explored in the wild type, and some of these essentially block resistance evolution. This effect is due to strong negative epistasis with resistance mutations. The identified genes and cellular functions provide potential targets for development of adjuvants that may block spontaneous resistance evolution when combined with antibiotics.
AU - Lukacisinova, Marta
AU - Fernando, Booshini
AU - Bollenbach, Mark Tobias
ID - 8037
JF - Nature Communications
TI - Highly parallel lab evolution reveals that epistasis can curb the evolution of antibiotic resistance
VL - 11
ER -
TY - JOUR
AB - Microelectromechanical systems and integrated photonics provide the basis for many reliable and compact circuit elements in modern communication systems. Electro-opto-mechanical devices are currently one of the leading approaches to realize ultra-sensitive, low-loss transducers for an emerging quantum information technology. Here we present an on-chip microwave frequency converter based on a planar aluminum on silicon nitride platform that is compatible with slot-mode coupled photonic crystal cavities. We show efficient frequency conversion between two propagating microwave modes mediated by the radiation pressure interaction with a metalized dielectric nanobeam oscillator. We achieve bidirectional coherent conversion with a total device efficiency of up to ~60%, a dynamic range of 2 × 10^9 photons/s and an instantaneous bandwidth of up to 1.7 kHz. A high fidelity quantum state transfer would be possible if the drive dependent output noise of currently ~14 photons s^−1 Hz^−1 is further reduced. Such a silicon nitride based transducer is in situ reconfigurable and could be used for on-chip classical and quantum signal routing and filtering, both for microwave and hybrid microwave-optical applications.
AU - Fink, Johannes M
AU - Kalaee, M.
AU - Norte, R.
AU - Pitanti, A.
AU - Painter, O.
ID - 8038
IS - 3
JF - Quantum Science and Technology
TI - Efficient microwave frequency conversion mediated by a photonics compatible silicon nitride nanobeam oscillator
VL - 5
ER -
TY - JOUR
AB - In the present work, we report a solution-based strategy to produce crystallographically textured SnSe bulk nanomaterials and printed layers with optimized thermoelectric performance in the direction normal to the substrate. Our strategy is based on the formulation of a molecular precursor that can be continuously decomposed to produce a SnSe powder or printed into predefined patterns. The precursor formulation and decomposition conditions are optimized to produce pure phase 2D SnSe nanoplates. The printed layer and the bulk material obtained after hot press displays a clear preferential orientation of the crystallographic domains, resulting in an ultralow thermal conductivity of 0.55 W m–1 K–1 in the direction normal to the substrate. Such textured nanomaterials present highly anisotropic properties with the best thermoelectric performance in plane, i.e., in the directions parallel to the substrate, which coincide with the crystallographic bc plane of SnSe. This is an unfortunate characteristic because thermoelectric devices are designed to create/harvest temperature gradients in the direction normal to the substrate. We further demonstrate that this limitation can be overcome with the introduction of small amounts of tellurium in the precursor. The presence of tellurium allows one to reduce the band gap and increase both the charge carrier concentration and the mobility, especially the cross plane, with a minimal decrease of the Seebeck coefficient. These effects translate into record out of plane ZT values at 800 K.
AU - Zhang, Yu
AU - Liu, Yu
AU - Xing, Congcong
AU - Zhang, Ting
AU - Li, Mengyao
AU - Pacios, Mercè
AU - Yu, Xiaoting
AU - Arbiol, Jordi
AU - Llorca, Jordi
AU - Cadavid, Doris
AU - Ibáñez, Maria
AU - Cabot, Andreu
ID - 8039
IS - 24
JF - ACS Applied Materials and Interfaces
TI - Tin selenide molecular precursor for the solution processing of thermoelectric materials and devices
VL - 12
ER -
TY - JOUR
AB - We consider systems of N bosons in a box of volume one, interacting through a repulsive two-body potential of the form κN3β−1V(Nβx). For all 0<β<1, and for sufficiently small coupling constant κ>0, we establish the validity of Bogolyubov theory, identifying the ground state energy and the low-lying excitation spectrum up to errors that vanish in the limit of large N.
AU - Boccato, Chiara
AU - Brennecke, Christian
AU - Cenatiempo, Serena
AU - Schlein, Benjamin
ID - 8042
IS - 7
JF - Journal of the European Mathematical Society
SN - 14359855
TI - The excitation spectrum of Bose gases interacting through singular potentials
VL - 22
ER -
TY - JOUR
AB - With decreasing Reynolds number, Re, turbulence in channel flow becomes spatio-temporally intermittent and self-organises into solitary stripes oblique to the mean flow direction. We report here the existence of localised nonlinear travelling wave solutions of the Navier–Stokes equations possessing this obliqueness property. Such solutions are identified numerically using edge tracking coupled with arclength continuation. All solutions emerge in saddle-node bifurcations at values of Re lower than the non-localised solutions. Relative periodic orbit solutions bifurcating from branches of travelling waves have also been computed. A complete parametric study is performed, including their stability, the investigation of their large-scale flow, and the robustness to changes of the numerical domain.
AU - Paranjape, Chaitanya S
AU - Duguet, Yohann
AU - Hof, Björn
ID - 8043
JF - Journal of Fluid Mechanics
SN - 00221120
TI - Oblique stripe solutions of channel flow
VL - 897
ER -
TY - JOUR
AB - Water-in-salt electrolytes based on highly concentrated bis(trifluoromethyl)sulfonimide (TFSI) promise aqueous electrolytes with stabilities approaching 3 V. However, especially with an electrode approaching the cathodic (reductive) stability, cycling stability is insufficient. While stability critically relies on a solid electrolyte interphase (SEI), the mechanism behind the cathodic stability limit remains unclear. Here, we reveal two distinct reduction potentials for the chemical environments of ‘free’ and ‘bound’ water and that both contribute to SEI formation. Free-water is reduced ~1V above bound water in a hydrogen evolution reaction (HER) and responsible for SEI formation via reactive intermediates of the HER; concurrent LiTFSI precipitation/dissolution establishes a dynamic interface. The free-water population emerges, therefore, as the handle to extend the cathodic limit of aqueous electrolytes and the battery cycling stability.
AU - Bouchal, Roza
AU - Li, Zhujie
AU - Bongu, Chandra
AU - Le Vot, Steven
AU - Berthelot, Romain
AU - Rotenberg, Benjamin
AU - Favier, Frederic
AU - Freunberger, Stefan Alexander
AU - Salanne, Mathieu
AU - Fontaine, Olivier
ID - 8057
IS - 37
JF - Angewandte Chemie
SN - 0044-8249
TI - Competitive salt precipitation/dissolution during free‐water reduction in water‐in‐salt electrolyte
VL - 132
ER -
TY - GEN
AB - We present a generative model of images that explicitly reasons over the set
of objects they show. Our model learns a structured latent representation that
separates objects from each other and from the background; unlike prior works,
it explicitly represents the 2D position and depth of each object, as well as
an embedding of its segmentation mask and appearance. The model can be trained
from images alone in a purely unsupervised fashion without the need for object
masks or depth information. Moreover, it always generates complete objects,
even though a significant fraction of training images contain occlusions.
Finally, we show that our model can infer decompositions of novel images into
their constituent objects, including accurate prediction of depth ordering and
segmentation of occluded parts.
AU - Anciukevicius, Titas
AU - Lampert, Christoph
AU - Henderson, Paul M
ID - 8063
T2 - arXiv
TI - Object-centric image generation with factored depths, locations, and appearances
ER -
TY - JOUR
AB - The projection methods with vanilla inertial extrapolation step for variational inequalities have been of interest to many authors recently due to the improved convergence speed contributed by the presence of inertial extrapolation step. However, it is discovered that these projection methods with inertial steps lose the Fejér monotonicity of the iterates with respect to the solution, which is being enjoyed by their corresponding non-inertial projection methods for variational inequalities. This lack of Fejér monotonicity makes projection methods with vanilla inertial extrapolation step for variational inequalities not to converge faster than their corresponding non-inertial projection methods at times. Also, it has recently been proved that the projection methods with vanilla inertial extrapolation step may provide convergence rates that are worse than the classical projected gradient methods for strongly convex functions. In this paper, we introduce projection methods with alternated inertial extrapolation step for solving variational inequalities. We show that the sequence of iterates generated by our methods converges weakly to a solution of the variational inequality under some appropriate conditions. The Fejér monotonicity of even subsequence is recovered in these methods and linear rate of convergence is obtained. The numerical implementations of our methods compared with some other inertial projection methods show that our method is more efficient and outperforms some of these inertial projection methods.
AU - Shehu, Yekini
AU - Iyiola, Olaniyi S.
ID - 8077
JF - Applied Numerical Mathematics
SN - 0168-9274
TI - Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence
VL - 157
ER -
TY - GEN
AB - Here, we employ micro- and nanosized cellulose particles, namely paper fines and cellulose
nanocrystals, to induce hierarchical organization over a wide length scale. After processing
them into carbonaceous materials, we demonstrate that these hierarchically organized materials
outperform the best materials for supercapacitors operating with organic electrolytes reported
in literature in terms of specific energy/power (Ragone plot) while showing hardly any capacity
fade over 4,000 cycles. The highly porous materials feature a specific surface area as high as
2500 m2ˑg-1 and exhibit pore sizes in the range of 0.5 to 200 nm as proven by scanning electron
microscopy and N2 physisorption. The carbonaceous materials have been further investigated
by X-ray photoelectron spectroscopy and RAMAN spectroscopy. Since paper fines are an
underutilized side stream in any paper production process, they are a cheap and highly available
feedstock to prepare carbonaceous materials with outstanding performance in electrochemical
applications.
AU - Hobisch, Mathias A.
AU - Mourad, Eléonore
AU - Fischer, Wolfgang J.
AU - Prehal, Christian
AU - Eyley, Samuel
AU - Childress, Anthony
AU - Zankel, Armin
AU - Mautner, Andreas
AU - Breitenbach, Stefan
AU - Rao, Apparao M.
AU - Thielemans, Wim
AU - Freunberger, Stefan Alexander
AU - Eckhart, Rene
AU - Bauer, Wolfgang
AU - Spirk, Stefan
ID - 8081
TI - High specific capacitance supercapacitors from hierarchically organized all-cellulose composites
ER -
TY - JOUR
AB - Origin and functions of intermittent transitions among sleep stages, including brief awakenings and arousals, constitute a challenge to the current homeostatic framework for sleep regulation, focusing on factors modulating sleep over large time scales. Here we propose that the complex micro-architecture characterizing sleep on scales of seconds and minutes results from intrinsic non-equilibrium critical dynamics. We investigate θ- and δ-wave dynamics in control rats and in rats where the sleep-promoting ventrolateral preoptic nucleus (VLPO) is lesioned (male Sprague-Dawley rats). We demonstrate that bursts in θ and δ cortical rhythms exhibit complex temporal organization, with long-range correlations and robust duality of power-law (θ-bursts, active phase) and exponential-like (δ-bursts, quiescent phase) duration distributions, features typical of non-equilibrium systems self-organizing at criticality. We show that such non-equilibrium behavior relates to anti-correlated coupling between θ- and δ-bursts, persists across a range of time scales, and is independent of the dominant physiologic state; indications of a basic principle in sleep regulation. Further, we find that VLPO lesions lead to a modulation of cortical dynamics resulting in altered dynamical parameters of θ- and δ-bursts and significant reduction in θ–δ coupling. Our empirical findings and model simulations demonstrate that θ–δ coupling is essential for the emerging non-equilibrium critical dynamics observed across the sleep–wake cycle, and indicate that VLPO neurons may have dual role for both sleep and arousal/brief wake activation. The uncovered critical behavior in sleep- and wake-related cortical rhythms indicates a mechanism essential for the micro-architecture of spontaneous sleep-stage and arousal transitions within a novel, non-homeostatic paradigm of sleep regulation.
AU - Lombardi, Fabrizio
AU - Gómez-Extremera, Manuel
AU - Bernaola-Galván, Pedro
AU - Vetrivelan, Ramalingam
AU - Saper, Clifford B.
AU - Scammell, Thomas E.
AU - Ivanov, Plamen Ch.
ID - 8084
IS - 1
JF - Journal of Neuroscience
SN - 0270-6474
TI - Critical dynamics and coupling in bursts of cortical rhythms indicate non-homeostatic mechanism for sleep-stage transitions and dual role of VLPO neurons in both sleep and wake
VL - 40
ER -
TY - JOUR
AB - In the setting of the fractional quantum Hall effect we study the effects of strong, repulsive two-body interaction potentials of short range. We prove that Haldane’s pseudo-potential operators, including their pre-factors, emerge as mathematically rigorous limits of such interactions when the range of the potential tends to zero while its strength tends to infinity. In a common approach the interaction potential is expanded in angular momentum eigenstates in the lowest Landau level, which amounts to taking the pre-factors to be the moments of the potential. Such a procedure is not appropriate for very strong interactions, however, in particular not in the case of hard spheres. We derive the formulas valid in the short-range case, which involve the scattering lengths of the interaction potential in different angular momentum channels rather than its moments. Our results hold for bosons and fermions alike and generalize previous results in [6], which apply to bosons in the lowest angular momentum channel. Our main theorem asserts the convergence in a norm-resolvent sense of the Hamiltonian on the whole Hilbert space, after appropriate energy scalings, to Hamiltonians with contact interactions in the lowest Landau level.
AU - Seiringer, Robert
AU - Yngvason, Jakob
ID - 8091
JF - Journal of Statistical Physics
SN - 00224715
TI - Emergence of Haldane pseudo-potentials in systems with short-range interactions
VL - 181
ER -