TY - JOUR
AB - The relative motion of three impenetrable particles on a ring, in our case two identical fermions and one impurity, is isomorphic to a triangular quantum billiard. Depending on the ratio κ of the impurity and fermion masses, the billiards can be integrable or non-integrable (also referred to in the main text as chaotic). To set the stage, we first investigate the energy level distributions of the billiards as a function of 1/κ ∈ [0, 1] and find no evidence of integrable cases beyond the limiting values 1/κ = 1 and 1/κ = 0. Then, we use machine learning tools to analyze properties of probability distributions of individual quantum states. We find that convolutional neural networks can correctly classify integrable and non-integrable states. The decisive features of the wave functions are the normalization and a large number of zero elements, corresponding to the existence of a nodal line. The network achieves typical accuracies of 97%, suggesting that machine learning tools can be used to analyze and classify the morphology of probability densities obtained in theory or experiment.
AU - Huber, David
AU - Marchukov, Oleksandr V.
AU - Hammer, Hans Werner
AU - Volosniev, Artem
ID - 9679
IS - 6
JF - New Journal of Physics
TI - Morphology of three-body quantum states from machine learning
VL - 23
ER -
TY - JOUR
AB - To overcome nitrogen deficiency, legume roots establish symbiotic interactions with nitrogen-fixing rhizobia that is fostered in specialized organs (nodules). Similar to other organs, nodule formation is determined by a local maximum of the phytohormone auxin at the primordium site. However, how auxin regulates nodule development remains poorly understood. Here, we found that in soybean, (Glycine max), dynamic auxin transport driven by PIN-FORMED (PIN) transporter GmPIN1 is involved in nodule primordium formation. GmPIN1 was specifically expressed in nodule primordium cells and GmPIN1 was polarly localized in these cells. Two nodulation regulators, (iso)flavonoids trigger expanded distribution of GmPIN1b to root cortical cells, and cytokinin rearranges GmPIN1b polarity. Gmpin1abc triple mutants generated with CRISPR-Cas9 showed impaired establishment of auxin maxima in nodule meristems and aberrant divisions in the nodule primordium cells. Moreover, overexpression of GmPIN1 suppressed nodule primordium initiation. GmPIN9d, an ortholog of Arabidopsis thaliana PIN2, acts together with GmPIN1 later in nodule development to acropetally transport auxin in vascular bundles, fine-tuning the auxin supply for nodule enlargement. Our findings reveal how PIN-dependent auxin transport modulates different aspects of soybean nodule development and suggest that establishment of auxin gradient is a prerequisite for the proper interaction between legumes and rhizobia.
AU - Gao, Z
AU - Chen, Z
AU - Cui, Y
AU - Ke, M
AU - Xu, H
AU - Xu, Q
AU - Chen, J
AU - Li, Y
AU - Huang, L
AU - Zhao, H
AU - Huang, D
AU - Mai, S
AU - Xu, T
AU - Liu, X
AU - Li, S
AU - Guan, Y
AU - Yang, W
AU - Friml, Jiří
AU - Petrášek, J
AU - Zhang, J
AU - Chen, X
ID - 9657
JF - Plant Cell
SN - 1040-4651
TI - GmPIN-dependent polar auxin transport is involved in soybean nodule development
ER -
TY - JOUR
AB - Tropisms, growth responses to environmental stimuli such as light or gravity, are spectacular examples of adaptive plant development. The plant hormone auxin serves as a major coordinative signal. The PIN auxin exporters, through their dynamic polar subcellular localizations, redirect auxin fluxes in response to environmental stimuli and the resulting auxin gradients across organs underly differential cell elongation and bending. In this review, we discuss recent advances concerning regulations of PIN polarity during tropisms, focusing on PIN phosphorylation and trafficking. We also cover how environmental cues regulate PIN actions during tropisms, and a crucial role of auxin feedback on PIN polarity during bending termination. Finally, the interactions between different tropisms are reviewed to understand plant adaptive growth in the natural environment.
AU - Han, Huibin
AU - Adamowski, Maciek
AU - Qi, Linlin
AU - Alotaibi, SS
AU - Friml, Jiří
ID - 9656
JF - New Phytologist
SN - 0028-646x
TI - PIN-mediated polar auxin transport regulations in plant tropic responses
ER -
TY - GEN
AB - Real-world data typically contain a large number of features that are often heterogeneous in nature, relevance, and also units of measure. When assessing the similarity between data points, one can build various distance measures using subsets of these features. Using the fewest features but still retaining sufficient information about the system is crucial in many statistical learning approaches, particularly when data are sparse. We introduce a statistical test that can assess the relative information retained when using two different distance measures, and determine if they are equivalent, independent, or if one is more informative than the other. This in turn allows finding the most informative distance measure out of a pool of candidates. The approach is applied to find the most relevant policy variables for controlling the Covid-19 epidemic and to find compact yet informative representations of atomic structures, but its potential applications are wide ranging in many branches of science.
AU - Glielmo, Aldo
AU - Zeni, Claudio
AU - Cheng, Bingqing
AU - Csanyi, Gabor
AU - Laio, Alessandro
ID - 9695
T2 - arXiv
TI - Ranking the information content of distance measures
ER -
TY - JOUR
AB - We compute the deficiency spaces of operators of the form 𝐻𝐴⊗̂ 𝐼+𝐼⊗̂ 𝐻𝐵, for symmetric 𝐻𝐴 and self-adjoint 𝐻𝐵. This enables us to construct self-adjoint extensions (if they exist) by means of von Neumann's theory. The structure of the deficiency spaces for this case was asserted already in Ibort et al. [Boundary dynamics driven entanglement, J. Phys. A: Math. Theor. 47(38) (2014) 385301], but only proven under the restriction of 𝐻𝐵 having discrete, non-degenerate spectrum.
AU - Lenz, Daniel
AU - Weinmann, Timon
AU - Wirth, Melchior
ID - 9627
JF - Proceedings of the Edinburgh Mathematical Society
SN - 00130915
TI - Self-adjoint extensions of bipartite Hamiltonians
ER -
TY - GEN
AB - Most water in the universe may be superionic, and its thermodynamic and transport properties are crucial for planetary science but difficult to probe experimentally or theoretically. We use machine learning and free energy methods to overcome the limitations of quantum mechanical simulations, and characterize hydrogen diffusion, superionic transitions, and phase behaviors of water at extreme conditions. We predict that a close-packed superionic phase with mixed stacking is stable over a wide temperature and pressure range, while a body-centered cubic phase is only thermodynamically stable in a small window but is kinetically favored. Our phase boundaries, which are consistent with the existing-albeit scarce-experimental observations, help resolve the fractions of insulating ice, different superionic phases, and liquid water inside of ice giants.
AU - Cheng, Bingqing
AU - Bethkenhagen, Mandy
AU - Pickard, Chris J.
AU - Hamel, Sebastien
ID - 9696
T2 - arXiv
TI - Predicting the phase behaviors of superionic water at planetary conditions
ER -
TY - JOUR
AB - Gene expression is regulated by the set of transcription factors (TFs) that bind to the promoter. The ensuing regulating function is often represented as a combinational logic circuit, where output (gene expression) is determined by current input values (promoter bound TFs) only. However, the simultaneous arrival of TFs is a strong assumption, since transcription and translation of genes introduce intrinsic time delays and there is no global synchronisation among the arrival times of different molecular species at their targets. We present an experimentally implementable genetic circuit with two inputs and one output, which in the presence of small delays in input arrival, exhibits qualitatively distinct population-level phenotypes, over timescales that are longer than typical cell doubling times. From a dynamical systems point of view, these phenotypes represent long-lived transients: although they converge to the same value eventually, they do so after a very long time span. The key feature of this toy model genetic circuit is that, despite having only two inputs and one output, it is regulated by twenty-three distinct DNA-TF configurations, two of which are more stable than others (DNA looped states), one promoting and another blocking the expression of the output gene. Small delays in input arrival time result in a majority of cells in the population quickly reaching the stable state associated with the first input, while exiting of this stable state occurs at a slow timescale. In order to mechanistically model the behaviour of this genetic circuit, we used a rule-based modelling language, and implemented a grid-search to find parameter combinations giving rise to long-lived transients. Our analysis shows that in the absence of feedback, there exist path-dependent gene regulatory mechanisms based on the long timescale of transients. The behaviour of this toy model circuit suggests that gene regulatory networks can exploit event timing to create phenotypes, and it opens the possibility that they could use event timing to memorise events, without regulatory feedback. The model reveals the importance of (i) mechanistically modelling the transitions between the different DNA-TF states, and (ii) employing transient analysis thereof.
AU - Petrov, Tatjana
AU - Igler, Claudia
AU - Sezgin, Ali
AU - Henzinger, Thomas A
AU - Guet, Calin C
ID - 9647
JF - Theoretical Computer Science
SN - 03043975
TI - Long lived transients in gene regulation
ER -
TY - CONF
AB - We consider the fundamental problem of deriving quantitative bounds on the probability that a given assertion is violated in a probabilistic program. We provide automated algorithms that obtain both lower and upper bounds on the assertion violation probability. The main novelty of our approach is that we prove new and dedicated fixed-point theorems which serve as the theoretical basis of our algorithms and enable us to reason about assertion violation bounds in terms of pre and post fixed-point functions. To synthesize such fixed-points, we devise algorithms that utilize a wide range of mathematical tools, including repulsing ranking supermartingales, Hoeffding's lemma, Minkowski decompositions, Jensen's inequality, and convex optimization. On the theoretical side, we provide (i) the first automated algorithm for lower-bounds on assertion violation probabilities, (ii) the first complete algorithm for upper-bounds of exponential form in affine programs, and (iii) provably and significantly tighter upper-bounds than the previous approaches. On the practical side, we show our algorithms can handle a wide variety of programs from the literature and synthesize bounds that are remarkably tighter than previous results, in some cases by thousands of orders of magnitude.
AU - Wang, Jinyi
AU - Sun, Yican
AU - Fu, Hongfei
AU - Chatterjee, Krishnendu
AU - Goharshady, Amir Kafshdar
ID - 9646
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Quantitative analysis of assertion violations in probabilistic programs
ER -
TY - CONF
AB - We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.
We first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semi-complete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods.
AU - Asadi, Ali
AU - Chatterjee, Krishnendu
AU - Fu, Hongfei
AU - Goharshady, Amir Kafshdar
AU - Mahdavi, Mohammad
ID - 9645
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Polynomial reachability witnesses via Stellensätze
ER -
TY - CONF
AB - We present a new approach to proving non-termination of non-deterministic integer programs. Our technique is rather simple but efficient. It relies on a purely syntactic reversal of the program's transition system followed by a constraint-based invariant synthesis with constraints coming from both the original and the reversed transition system. The latter task is performed by a simple call to an off-the-shelf SMT-solver, which allows us to leverage the latest advances in SMT-solving. Moreover, our method offers a combination of features not present (as a whole) in previous approaches: it handles programs with non-determinism, provides relative completeness guarantees and supports programs with polynomial arithmetic. The experiments performed with our prototype tool RevTerm show that our approach, despite its simplicity and stronger theoretical guarantees, is at least on par with the state-of-the-art tools, often achieving a non-trivial improvement under a proper configuration of its parameters.
AU - Chatterjee, Krishnendu
AU - Goharshady, Ehsan Kafshdar
AU - Novotný, Petr
AU - Zikelic, Dorde
ID - 9644
SN - 9781450383912
T2 - Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
TI - Proving non-termination by program reversal
ER -
TY - JOUR
AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently
fine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.
AU - Boissonnat, Jean-Daniel
AU - Wintraecken, Mathijs
ID - 9649
JF - Foundations of Computational Mathematics
TI - The topological correctness of PL approximations of isomanifolds
ER -
TY - GEN
AB - Machine learning models are poised to make a transformative impact on chemical sciences by dramatically accelerating computational algorithms and amplifying insights available from computational chemistry methods. However, achieving this requires a confluence and coaction of expertise in computer science and physical sciences. This review is written for new and experienced researchers working at the intersection of both fields. We first provide concise tutorials of computational chemistry and machine learning methods, showing how insights involving both can be achieved. We then follow with a critical review of noteworthy applications that demonstrate how computational chemistry and machine learning can be used together to provide insightful (and useful) predictions in molecular and materials modeling, retrosyntheses, catalysis, and drug design.
AU - Keith, John A.
AU - Valentin Vassilev-Galindo, Valentin
AU - Cheng, Bingqing
AU - Chmiela, Stefan
AU - Gastegger, Michael
AU - Müller, Klaus-Robert
AU - Tkatchenko, Alexandre
ID - 9698
T2 - arXiv
TI - Combining machine learning and computational chemistry for predictive insights into chemical systems
ER -
TY - CONF
AB - We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
AU - Brandt, Sebastian
AU - Keller, Barbara
AU - Rybicki, Joel
AU - Suomela, Jukka
AU - Uitto, Jara
ID - 9678
SN - 9781450380706
T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficient load-balancing through distributed token dropping
ER -
TY - CONF
AB - Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art.
AU - Boissonnat, Jean-Daniel
AU - Kachanovich, Siargey
AU - Wintraecken, Mathijs
ID - 9441
SN - 1868-8969
T2 - 37th International Symposium on Computational Geometry (SoCG 2021)
TI - Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations
VL - 189
ER -
TY - CONF
AB - In this note, we introduce a distributed twist on the classic coupon collector problem: a set of m collectors wish to each obtain a set of n coupons; for this, they can each sample coupons uniformly at random, but can also meet in pairwise interactions, during which they can exchange coupons. By doing so, they hope to reduce the number of coupons that must be sampled by each collector in order to obtain a full set. This extension is natural when considering real-world manifestations of the coupon collector phenomenon, and has been remarked upon and studied empirically (Hayes and Hannigan 2006, Ahmad et al. 2014, Delmarcelle 2019).
We provide the first theoretical analysis for such a scenario. We find that “coupon collecting with friends” can indeed significantly reduce the number of coupons each collector must sample, and raises interesting connections to the more traditional variants of the problem. While our analysis is in most cases asymptotically tight, there are several open questions raised, regarding finer-grained analysis of both “coupon collecting with friends,” and of a long-studied variant of the original problem in which a collector requires multiple full sets of coupons.
AU - Alistarh, Dan-Adrian
AU - Davies, Peter
ID - 9620
SN - 0302-9743
T2 - Structural Information and Communication Complexity
TI - Collecting coupons is faster with friends
VL - 12810
ER -
TY - CONF
AB - Formal design of embedded and cyber-physical systems relies on mathematical modeling. In this paper, we consider the model class of hybrid automata whose dynamics are defined by affine differential equations. Given a set of time-series data, we present an algorithmic approach to synthesize a hybrid automaton exhibiting behavior that is close to the data, up to a specified precision, and changes in synchrony with the data. A fundamental problem in our synthesis algorithm is to check membership of a time series in a hybrid automaton. Our solution integrates reachability and optimization techniques for affine dynamical systems to obtain both a sufficient and a necessary condition for membership, combined in a refinement framework. The algorithm processes one time series at a time and hence can be interrupted, provide an intermediate result, and be resumed. We report experimental results demonstrating the applicability of our synthesis approach.
AU - Garcia Soto, Miriam
AU - Henzinger, Thomas A
AU - Schilling, Christian
ID - 9200
KW - hybrid automaton
KW - membership
KW - system identification
SN - 9781450383394
T2 - HSCC '21: Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control
TI - Synthesis of hybrid automata with affine dynamics from time-series data
ER -
TY - CONF
AB - Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.
AU - Edelsbrunner, Herbert
AU - Heiss, Teresa
AU - Kurlin , Vitaliy
AU - Smith, Philip
AU - Wintraecken, Mathijs
ID - 9345
SN - 1868-8969
T2 - 37th International Symposium on Computational Geometry (SoCG 2021)
TI - The density fingerprint of a periodic point set
VL - 189
ER -
TY - CONF
AB - matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.
AU - Aichholzer, Oswin
AU - Arroyo Guevara, Alan M
AU - Masárová, Zuzana
AU - Parada, Irene
AU - Perz, Daniel
AU - Pilz, Alexander
AU - Tkadlec, Josef
AU - Vogtenhuber, Birgit
ID - 9296
SN - 03029743
T2 - 15th International Conference on Algorithms and Computation
TI - On compatible matchings
VL - 12635
ER -
TY - CONF
AB - In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.
AU - Walter, Michael
ID - 9466
SN - 03029743
T2 - Public-Key Cryptography – PKC 2021
TI - The convergence of slide-type reductions
VL - 12710
ER -
TY - CONF
AB - Modern neural networks can easily fit their training set perfectly. Surprisingly, despite being “overfit” in this way, they tend to generalize well to future data, thereby defying the classic bias–variance trade-off of machine learning theory. Of the many possible explanations, a prevalent one is that training by stochastic gradient descent (SGD) imposes an implicit bias that leads it to learn simple functions, and these simple functions generalize well. However, the specifics of this implicit bias are not well understood.
In this work, we explore the smoothness conjecture which states that SGD is implicitly biased towards learning functions that are smooth. We propose several measures to formalize the intuitive notion of smoothness, and we conduct experiments to determine whether SGD indeed implicitly optimizes for these measures. Our findings rule out the possibility that smoothness measures based on first-order derivatives are being implicitly enforced. They are supportive, though, of the smoothness conjecture for measures based on second-order derivatives.
AU - Volhejn, Vaclav
AU - Lampert, Christoph
ID - 9210
SN - 03029743
T2 - 42nd German Conference on Pattern Recognition
TI - Does SGD implicitly optimize for smoothness?
VL - 12544 LNCS
ER -