On the treewidth of triangulated 3-manifolds - Huszár, Kristóf; Spreer, Jonathan; Wagner, Uli
In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).

Electromagnetic fields and optomechanics In cancer diagnostics and treatment - Salari, Vahid; Barzanjeh, Shabir; Cifra, Michal; Simon, Christoph; Scholkmann, Felix; Alirezaei, Zahra; Tuszynski, Jack (Frontiers in Bioscience - Landmark)
In this paper, we discuss biological effects of electromagnetic (EM) fields in the context of cancer biology. In particular, we review the nanomechanical properties of microtubules (MTs), the latter being one of the most successful targets for cancer therapy. We propose an investigation on the coupling of electromagnetic radiation to mechanical vibrations of MTs as an important basis for biological and medical applications. In our opinion, optomechanical methods can accurately monitor and control the mechanical properties of isolated MTs in a liquid environment. Consequently, studying nanomechanical properties of MTs may give useful information for future applications to diagnostic and therapeutic technologies involving non-invasive externally applied physical fields. For example, electromagnetic fields or high intensity ultrasound can be used therapeutically avoiding harmful side effects of chemotherapeutic agents or classical radiation therapy.

Clonal analysis of Notch1-expressing cells reveals the existence of unipotent stem cells that retain long-term plasticity in the embryonic mammary gland - Lilja, Anna; Rodilla, Veronica; Huyghe, Mathilde; Hannezo, Edouard B; Landragin, Camille; Renaud, Olivier; Leroy, Olivier; Rulands, Steffen; Simons, Benjamin; Fré, Silvia (Nature Cell Biology)
Recent lineage tracing studies have revealed that mammary gland homeostasis relies on unipotent stem cells. However, whether and when lineage restriction occurs during embryonic mammary development, and which signals orchestrate cell fate specification, remain unknown. Using a combination of in vivo clonal analysis with whole mount immunofluorescence and mathematical modelling of clonal dynamics, we found that embryonic multipotent mammary cells become lineage-restricted surprisingly early in development, with evidence for unipotency as early as E12.5 and no statistically discernable bipotency after E15.5. To gain insights into the mechanisms governing the switch from multipotency to unipotency, we used gain-of-function Notch1 mice and demonstrated that Notch activation cell autonomously dictates luminal cell fate specification to both embryonic and basally committed mammary cells. These functional studies have important implications for understanding the signals underlying cell plasticity and serve to clarify how reactivation of embryonic programs in adult cells can lead to cancer.

Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene - Zibrov, Alexander; Peng, Rao; Kometter, Carlos; Li, Jia; Dean, Cory; Taniguchi, Takashi; Watanabe, Kenji; Serbyn, Maksym; Young, Andrea (Physical Review Letters)
We report on quantum capacitance measurements of high quality, graphite- and hexagonal boron nitride encapsulated Bernal stacked trilayer graphene devices. At zero applied magnetic field, we observe a number of electron density- and electrical displacement-tuned features in the electronic compressibility associated with changes in Fermi surface topology. At high displacement field and low density, strong trigonal warping gives rise to emergent Dirac gullies centered near the corners of the hexagonal Brillouin and related by three fold rotation symmetry. At low magnetic fields of B=1.25~T, the gullies manifest as a change in the degeneracy of the Landau levels from two to three. Weak incompressible states are also observed at integer filling within these triplets Landau levels, which a Hartree-Fock analysis indicates are associated with Coulomb-driven nematic phases that spontaneously break rotation symmetry.

Social environment affects the transcriptomic response to bacteria in ant queens - Viljakainen, Lumi; Jurvansuu, Jaana; Holmberg, Ida; Pamminger, Tobias; Erler, Silvio; Cremer, Sylvia (Ecology and Evolution)
Social insects have evolved enormous capacities to collectively build nests and defend their colonies against both predators and pathogens. The latter is achieved by a combination of individual immune responses and sophisticated collective behavioral and organizational disease defenses, that is, social immunity. We investigated how the presence or absence of these social defense lines affects individual-level immunity in ant queens after bacterial infection. To this end, we injected queens of the ant Linepithema humile with a mix of gram+ and gram− bacteria or a control solution, reared them either with workers or alone and analyzed their gene expression patterns at 2, 4, 8, and 12 hr post-injection, using RNA-seq. This allowed us to test for the effect of bacterial infection, social context, as well as the interaction between the two over the course of infection and raising of an immune response. We found that social isolation per se affected queen gene expression for metabolism genes, but not for immune genes. When infected, queens reared with and without workers up-regulated similar numbers of innate immune genes revealing activation of Toll and Imd signaling pathways and melanization. Interestingly, however, they mostly regulated different genes along the pathways and showed a different pattern of overall gene up-regulation or down-regulation. Hence, we can conclude that the absence of workers does not compromise the onset of an individual immune response by the queens, but that the social environment impacts the route of the individual innate immune responses.

Complexity of the laminar-turbulent boundary in pipe flow - Budanur, Nazmi B; Hof, Björn (Physical Review Fluids)
Over the past decade, the edge of chaos has proven to be a fruitful starting point for investigations of shear flows when the laminar base flow is linearly stable. Numerous computational studies of shear flows demonstrated the existence of states that separate laminar and turbulent regions of the state space. In addition, some studies determined invariant solutions that reside on this edge. In this paper, we study the unstable manifold of one such solution with the aid of continuous symmetry reduction, which we formulate here for the simultaneous quotiening of axial and azimuthal symmetries. Upon our investigation of the unstable manifold, we discover a previously unknown traveling-wave solution on the laminar-turbulent boundary with a relatively complex structure. By means of low-dimensional projections, we visualize different dynamical paths that connect these solutions to the turbulence. Our numerical experiments demonstrate that the laminar-turbulent boundary exhibits qualitatively different regions whose properties are influenced by the nearby invariant solutions.

Nonlinear decoding of a complex movie from the mammalian retina - Botella Soler, Vicent; Deny, Stephane; Martius, Georg S; Marre, Olivier; Tkacik, Gasper (PLoS Computational Biology)
Retina is a paradigmatic system for studying sensory encoding: the transformation of light into spiking activity of ganglion cells. The inverse problem, where stimulus is reconstructed from spikes, has received less attention, especially for complex stimuli that should be reconstructed “pixel-by-pixel”. We recorded around a hundred neurons from a dense patch in a rat retina and decoded movies of multiple small randomly-moving discs. We constructed nonlinear (kernelized and neural network) decoders that improved significantly over linear results. An important contribution to this was the ability of nonlinear decoders to reliably separate between neural responses driven by locally fluctuating light signals, and responses at locally constant light driven by spontaneous-like activity. This improvement crucially depended on the precise, non-Poisson temporal structure of individual spike trains, which originated in the spike-history dependence of neural responses. We propose a general principle by which downstream circuitry could discriminate between spontaneous and stimulus-driven activity based solely on higher-order statistical structure in the incoming spike trains.

The signal-burying game can explain why we obscure positive traits and good deeds - Hoffman, Moshe; Hilbe, Christian; Nowak, Martin (Nature Human Behaviour)
People sometimes make their admirable deeds and accomplishments hard to spot, such as by giving anonymously or avoiding bragging. Such ‘buried’ signals are hard to reconcile with standard models of signalling or indirect reciprocity, which motivate costly pro-social behaviour by reputational gains. To explain these phenomena, we design a simple game theory model, which we call the signal-burying game. This game has the feature that senders can bury their signal by deliberately reducing the probability of the signal being observed. If the signal is observed, however, it is identified as having been buried. We show under which conditions buried signals can be maintained, using static equilibrium concepts and calculations of the evolutionary dynamics. We apply our analysis to shed light on a number of otherwise puzzling social phenomena, including modesty, anonymous donations, subtlety in art and fashion, and overeagerness.

Two-photon processes based on quantum commutators - Fratini, Filippo; Safari, Laleh; Amaro, Pedro; Santos, José (Physical Review A - Atomic, Molecular, and Optical Physics)
We developed a method to calculate two-photon processes in quantum mechanics that replaces the infinite summation over the intermediate states by a perturbation expansion. This latter consists of a series of commutators that involve position, momentum, and Hamiltonian quantum operators. We analyzed several single- and many-particle cases for which a closed-form solution to the perturbation expansion exists, as well as more complicated cases for which a solution is found by convergence. Throughout the article, Rayleigh and Raman scattering are taken as examples of two-photon processes. The present method provides a clear distinction between the Thomson scattering, regarded as classical scattering, and quantum contributions. Such a distinction lets us derive general results concerning light scattering. Finally, possible extensions to the developed formalism are discussed.

Fermionic behavior of ideal anyons - Lundholm, Douglas; Seiringer, Robert (Letters in Mathematical Physics)
We prove upper and lower bounds on the ground-state energy of the ideal two-dimensional anyon gas. Our bounds are extensive in the particle number, as for fermions, and linear in the statistics parameter (Formula presented.). The lower bounds extend to Lieb–Thirring inequalities for all anyons except bosons.

Weak ergodicity breaking from quantum many-body scars - Turner, Christopher; Michailidis, Alexios; Abanin, Dmitry; Serbyn, Maksym; Papić, Zlatko (Nature Physics)
The thermodynamic description of many-particle systems rests on the assumption of ergodicity, the ability of a system to explore all allowed configurations in the phase space. Recent studies on many-body localization have revealed the existence of systems that strongly violate ergodicity in the presence of quenched disorder. Here, we demonstrate that ergodicity can be weakly broken by a different mechanism, arising from the presence of special eigenstates in the many-body spectrum that are reminiscent of quantum scars in chaotic non-interacting systems. In the single-particle case, quantum scars correspond to wavefunctions that concentrate in the vicinity of unstable periodic classical trajectories. We show that many-body scars appear in the Fibonacci chain, a model with a constrained local Hilbert space that has recently been experimentally realized in a Rydberg-atom quantum simulator. The quantum scarred eigenstates are embedded throughout the otherwise thermalizing many-body spectrum but lead to direct experimental signatures, as we show for periodic recurrences that reproduce those observed in the experiment. Our results suggest that scarred many-body bands give rise to a new universality class of quantum dynamics, opening up opportunities for the creation of novel states with long-lived coherence in systems that are now experimentally realizable.

Strategy representation by decision trees in reactive synthesis - Brázdil, Tomáš; Chatterjee, Krishnendu; Kretinsky, Jan; Toman, Viktor
Graph games played by two players over finite-state graphs are central in many problems in computer science. In particular, graph games with ω -regular winning conditions, specified as parity objectives, which can express properties such as safety, liveness, fairness, are the basic framework for verification and synthesis of reactive systems. The decisions for a player at various states of the graph game are represented as strategies. While the algorithmic problem for solving graph games with parity objectives has been widely studied, the most prominent data-structure for strategy representation in graph games has been binary decision diagrams (BDDs). However, due to the bit-level representation, BDDs do not retain the inherent flavor of the decisions of strategies, and are notoriously hard to minimize to obtain succinct representation. In this work we propose decision trees for strategy representation in graph games. Decision trees retain the flavor of decisions of strategies and allow entropy-based minimization to obtain succinct trees. However, decision trees work in settings (e.g., probabilistic models) where errors are allowed, and overfitting of data is typically avoided. In contrast, for strategies in graph games no error is allowed, and the decision tree must represent the entire strategy. We develop new techniques to extend decision trees to overcome the above obstacles, while retaining the entropy-based techniques to obtain succinct trees. We have implemented our techniques to extend the existing decision tree solvers. We present experimental results for problems in reactive synthesis to show that decision trees provide a much more efficient data-structure for strategy representation as compared to BDDs.

Sustained space complexity - Alwen, Joel F; Blocki, Jeremiah; Pietrzak, Krzysztof Z
Memory-hard functions (MHF) are functions whose evaluation cost is dominated by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware (like x86 CPUs). MHFs have interesting cryptographic applications, most notably to password hashing and securing blockchains. Alwen and Serbinenko [STOC’15] define the cumulative memory complexity (cmc) of a function as the sum (over all time-steps) of the amount of memory required to compute the function. They advocate that a good MHF must have high cmc. Unlike previous notions, cmc takes into account that dedicated hardware might exploit amortization and parallelism. Still, cmc has been critizised as insufficient, as it fails to capture possible time-memory trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc could still have very different actual hardware cost. In this work we address this problem, and introduce the notion of sustained-memory complexity, which requires that any algorithm evaluating the function must use a large amount of memory for many steps. We construct functions (in the parallel random oracle model) whose sustained-memory complexity is almost optimal: our function can be evaluated using n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input length) random oracle, while any algorithm that can make arbitrary many parallel queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps. As has been done for various notions (including cmc) before, we reduce the task of constructing an MHFs with high sustained-memory complexity to proving pebbling lower bounds on DAGs. Our main technical contribution is the construction is a family of DAGs on n nodes with constant indegree with high “sustained-space complexity”, meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles for at least Ω(n) steps. Along the way we construct a family of maximally “depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅

AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic - Nickovic, Dejan; Lebeltel, Olivier; Maler, Oded; Ferrere, Thomas; Ulus, Dogan
We introduce in this paper AMT 2.0 , a tool for qualitative and quantitative analysis of hybrid continuous and Boolean signals that combine numerical values and discrete events. The evaluation of the signals is based on rich temporal specifications expressed in extended Signal Temporal Logic (xSTL), which integrates Timed Regular Expressions (TRE) within Signal Temporal Logic (STL). The tool features qualitative monitoring (property satisfaction checking), trace diagnostics for explaining and justifying property violations and specification-driven measurement of quantitative features of the signal.

On the bit security of cryptographic primitives - Micciancio, Daniele; Walter, Michael
We introduce a formal quantitative notion of “bit security” for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with k-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a k-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems.

Simple proofs of sequential work - Cohen, Bram; Pietrzak, Krzysztof Z
At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies. The construction proposed by [MMV13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work. In a proof of sequential work, a prover gets a “statement” χ, a time parameter N and access to a hash-function H, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only N queries to H, while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to H. Thus a solution constitutes a proof that N time passed since χ was received. Solutions must be publicly verifiable in time at most polylogarithmic in N. The construction of [MMV13] is based on “depth-robust” graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just N time, but also N space to compute a proof. In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as log (N) (but we get better soundness using slightly more memory than that). An open problem stated by [MMV13] that our construction does not solve either is achieving a “unique” proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains.

Introduction to tropical series and wave dynamic on them - Kalinin, Nikita; Shkolnikov, Mikhail (Discrete and Continuous Dynamical Systems- Series A)
The theory of tropical series, that we develop here, firstly appeared in the study of the growth of pluriharmonic functions. Motivated by waves in sandpile models we introduce a dynamic on the set of tropical series, and it is experimentally observed that this dynamic obeys a power law. So, this paper serves as a compilation of results we need for other articles and also introduces several objects interesting by themselves.

Computational design of nanostructural color for additive manufacturing - Auzinger, Thomas; Heidrich, Wolfgang; Bickel, Bernd (ACM Transactions on Graphics)
Additive manufacturing has recently seen drastic improvements in resolution, making it now possible to fabricate features at scales of hundreds or even dozens of nanometers, which previously required very expensive lithographic methods. As a result, additive manufacturing now seems poised for optical applications, including those relevant to computer graphics, such as material design, as well as display and imaging applications. In this work, we explore the use of additive manufacturing for generating structural colors, where the structures are designed using a fabrication-aware optimization process. This requires a combination of full-wave simulation, a feasible parameterization of the design space, and a tailored optimization procedure. Many of these components should be re-usable for the design of other optical structures at this scale. We show initial results of material samples fabricated based on our designs. While these suffer from the prototype character of state-of-the-art fabrication hardware, we believe they clearly demonstrate the potential of additive nanofabrication for structural colors and other graphics applications.

An introduction to the maximum entropy approach and its application to inference problems in biology - De Martino, Andrea; De Martino, Daniele (Heliyon)
A cornerstone of statistical inference, the maximum entropy framework is being increasingly applied to construct descriptive and predictive models of biological systems, especially complex biological networks, from large experimental data sets. Both its broad applicability and the success it obtained in different contexts hinge upon its conceptual simplicity and mathematical soundness. Here we try to concisely review the basic elements of the maximum entropy principle, starting from the notion of ‘entropy’, and describe its usefulness for the analysis of biological systems. As examples, we focus specifically on the problem of reconstructing gene interaction networks from expression data and on recent work attempting to expand our system-level understanding of bacterial metabolism. Finally, we highlight some extensions and potential limitations of the maximum entropy approach, and point to more recent developments that are likely to play a key role in the upcoming challenges of extracting structures and information from increasingly rich, high-throughput biological data.

Nanoscopy of pairs of atoms by fluorescence in a magnetic field - Redchenko, Elena; Makarov, Alexander; Yudson, Vladimir (Physical Review A - Atomic, Molecular, and Optical Physics)
Spontaneous emission spectra of two initially excited closely spaced identical atoms are very sensitive to the strength and the direction of the applied magnetic field. We consider the relevant schemes that ensure the determination of the mutual spatial orientation of the atoms and the distance between them by entirely optical means. A corresponding theoretical description is given accounting for the dipole-dipole interaction between the two atoms in the presence of a magnetic field and for polarizations of the quantum field interacting with magnetic sublevels of the two-atom system.