@inproceedings{6733, abstract = {The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N -δ , for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.}, author = {Kudekar, Shrinivas and Kumar, Santhosh and Mondelli, Marco and Pfister, Henry D. and Urbankez, Rudiger}, booktitle = {2016 IEEE International Symposium on Information Theory }, location = {Barcelona, Spain}, pages = {1755--1759}, publisher = {IEEE}, title = {{Comparing the bit-MAP and block-MAP decoding thresholds of Reed-Muller codes on BMS channels}}, doi = {10.1109/isit.2016.7541600}, year = {2016}, } @inproceedings{6770, abstract = {We describe a new method to compare the bit-MAP and block-MAP decoding thresholds of Reed-Muller (RM) codes for transmission over a binary memoryless symmetric channel. The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory and it has recently been answered in the affirmative for transmission over erasure channels. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. A natural question is what happens under block-MAP decoding. If the minimum distance of the code family is close to linear (e.g., of order N/ log(N)), then one can combine an upper bound on the bit-MAP error probability with a lower bound on the minimum distance to show that the code family is also capacity-achieving under block-MAP decoding. This strategy is successful for BCH codes. Unfortunately, the minimum distance of RM codes scales only as √N, which does not suffice to obtain the desired result. Then, one can exploit further symmetries of RM codes to show that the bit-MAP threshold is sharp enough so that the block erasure probability also tends to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to the transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.}, author = {Mondelli, Marco and Kudekar, Shrinivas and Kumar, Santosh and Pfister, Henry D. and Şaşoğlu, Eren and Urbanke, Rüdiger}, booktitle = {24th International Zurich Seminar on Communications}, location = {Zurich, Switzerland}, pages = {50}, publisher = {ETH Zürich}, title = {{Reed-Muller codes: Thresholds and weight distribution}}, doi = {10.3929/ETHZ-A-010646484}, year = {2016}, } @article{100, abstract = {We introduce a scheme for preparation, manipulation, and read out of Majorana zero modes in semiconducting wires with mesoscopic superconducting islands. Our approach synthesizes recent advances in materials growth with tools commonly used in quantum-dot experiments, including gate control of tunnel barriers and Coulomb effects, charge sensing, and charge pumping. We outline a sequence of milestones interpolating between zero-mode detection and quantum computing that includes (1) detection of fusion rules for non-Abelian anyons using either proximal charge sensors or pumped current, (2) validation of a prototype topological qubit, and (3) demonstration of non-Abelian statistics by braiding in a branched geometry. The first two milestones require only a single wire with two islands, and additionally enable sensitive measurements of the system\'s excitation gap, quasiparticle poisoning rates, residual Majorana zero-mode splittings, and topological-qubit coherence times. These pre-braiding experiments can be adapted to other manipulation and read out schemes as well.}, author = {Aasen, David and Hell, Michael and Mishmash, Ryan and Higginbotham, Andrew P and Danon, Jeroen and Leijnse, Martin and Jespersen, Thomas and Folk, Joshua and Marcs, Charles and Flensberg, Karsten and Alicea, Jason}, journal = {Physical Review X}, number = {3}, publisher = {American Physical Society}, title = {{Milestones toward Majorana-based quantum computing}}, doi = {10.1103/PhysRevX.6.031016}, volume = {6}, year = {2016}, } @article{1008, abstract = {Feedback loops in biological networks, among others, enable differentiation and cell cycle progression, and increase robustness in signal transduction. In natural networks, feedback loops are often complex and intertwined, making it challenging to identify which loops are mainly responsible for an observed behavior. However, minimal synthetic replicas could allow for such identification. Here, we engineered a synthetic permease-inducer-repressor system in Saccharomyces cerevisiae to analyze if a transport-mediated positive feedback loop could be a core mechanism for the switch-like behavior in the regulation of metabolic gene networks such as the S. cerevisiae GAL system or the Escherichia coli lac operon. We characterized the synthetic circuit using deterministic and stochastic mathematical models. Similar to its natural counterparts, our synthetic system shows bistable and hysteretic behavior, and the inducer concentration range for bistability as well as the switching rates between the two stable states depend on the repressor concentration. Our results indicate that a generic permease–inducer–repressor circuit with a single feedback loop is sufficient to explain the experimentally observed bistable behavior of the natural systems. We anticipate that the approach of reimplementing natural systems with orthogonal parts to identify crucial network components is applicable to other natural systems such as signaling pathways.}, author = {Gnügge, Robert and Dharmarajan, Lekshmi and Lang, Moritz and Stelling, Jörg}, journal = {ACS Synthetic Biology}, number = {10}, pages = {1098 -- 1107}, publisher = {American Chemical Society}, title = {{An orthogonal permease–inducer–repressor feedback loop shows bistability}}, doi = {10.1021/acssynbio.6b00013}, volume = {5}, year = {2016}, } @article{101, abstract = {Majorana zero modes are quasiparticle excitations in condensed matter systems that have been proposed as building blocks of fault-tolerant quantum computers. They are expected to exhibit non-Abelian particle statistics, in contrast to the usual statistics of fermions and bosons, enabling quantum operations to be performed by braiding isolated modes around one another. Quantum braiding operations are topologically protected insofar as these modes are pinned near zero energy, with the departure from zero expected to be exponentially small as the modes become spatially separated. Following theoretical proposals, several experiments have identified signatures of Majorana modes in nanowires with proximity-induced superconductivity and atomic chains, with small amounts of mode splitting potentially explained by hybridization of Majorana modes. Here, we use Coulomb-blockade spectroscopy in an InAs nanowire segment with epitaxial aluminium, which forms a proximity-induced superconducting Coulomb island (a â ∼ Majorana islandâ (tm)) that is isolated from normal-metal leads by tunnel barriers, to measure the splitting of near-zero-energy Majorana modes. We observe exponential suppression of energy splitting with increasing wire length. For short devices of a few hundred nanometres, sub-gap state energies oscillate as the magnetic field is varied, as is expected for hybridized Majorana modes. Splitting decreases by a factor of about ten for each half a micrometre of increased wire length. For devices longer than about one micrometre, transport in strong magnetic fields occurs through a zero-energy state that is energetically isolated from a continuum, yielding uniformly spaced Coulomb-blockade conductance peaks, consistent with teleportation via Majorana modes. Our results help to explain the trivial-to-topological transition in finite systems and to quantify the scaling of topological protection with end-mode separation.}, author = {Albrecht, S M and Higginbotham, Andrew P and Jespersen, Thomas and Madsen, Morten and Kuemmeth, Ferdinand and Nygård, Jesper and Krogstrup, Peter and Marcus, Charles}, journal = {Nature}, number = {7593}, pages = {206 -- 209}, publisher = {Nature Publishing Group}, title = {{Exponential protection of zero modes in Majorana islands}}, doi = {10.1038/nature17162}, volume = {531}, year = {2016}, } @article{102, abstract = {Recent experiments have produced mounting evidence of Majorana zero modes in nanowire-superconductor hybrids. Signatures of an expected topological phase transition accompanying the onset of these modes nevertheless remain elusive. We investigate a fundamental question concerning this issue: Do well-formed Majorana modes necessarily entail a sharp phase transition in these setups? Assuming reasonable parameters, we argue that finite-size effects can dramatically smooth this putative transition into a crossover, even in systems large enough to support well-localized Majorana modes. We propose overcoming such finite-size effects by examining the behavior of low-lying excited states through tunneling spectroscopy. In particular, the excited-state energies exhibit characteristic field and density dependence, and scaling with system size, that expose an approaching topological phase transition. We suggest several experiments for extracting the predicted behavior. As a useful byproduct, the protocols also allow one to measure the wire's spin-orbit coupling directly in its superconducting environment.}, author = {Mishmash, Ryan and Aasen, David and Higginbotham, Andrew P and Alicea, Jason}, journal = {Physical Review B}, number = {24}, publisher = {American Physical Society}, title = {{Approaching a topological phase transition in Majorana nanowires}}, doi = {10.1103/PhysRevB.93.245404}, volume = {93}, year = {2016}, } @article{10376, abstract = {Nucleation processes are at the heart of a large number of phenomena, from cloud formation to protein crystallization. A recently emerging area where nucleation is highly relevant is the initiation of filamentous protein self-assembly, a process that has broad implications in many research areas ranging from medicine to nanotechnology. As such, spontaneous nucleation of protein fibrils has received much attention in recent years with many theoretical and experimental studies focusing on the underlying physical principles. In this paper we make a step forward in this direction and explore the early time behaviour of filamentous protein growth in the context of nucleation theory. We first provide an overview of the thermodynamics and kinetics of spontaneous nucleation of protein filaments in the presence of one relevant degree of freedom, namely the cluster size. In this case, we review how key kinetic observables, such as the reaction order of spontaneous nucleation, are directly related to the physical size of the critical nucleus. We then focus on the increasingly prominent case of filament nucleation that includes a conformational conversion of the nucleating building-block as an additional slow step in the nucleation process. Using computer simulations, we study the concentration dependence of the nucleation rate. We find that, under these circumstances, the reaction order of spontaneous nucleation with respect to the free monomer does no longer relate to the overall physical size of the nucleating aggregate but rather to the portion of the aggregate that actively participates in the conformational conversion. Our results thus provide a novel interpretation of the common kinetic descriptors of protein filament formation, including the reaction order of the nucleation step or the scaling exponent of lag times, and put into perspective current theoretical descriptions of protein aggregation.}, author = {Šarić, Anđela and Michaels, Thomas C. T. and Zaccone, Alessio and Knowles, Tuomas P. J. and Frenkel, Daan}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, keywords = {physical and theoretical chemistry, general physics and astronomy}, number = {21}, publisher = {American Institute of Physics}, title = {{Kinetics of spontaneous filament nucleation via oligomers: Insights from theory and simulation}}, doi = {10.1063/1.4965040}, volume = {145}, year = {2016}, } @article{10377, abstract = {The interplay of membrane proteins is vital for many biological processes, such as cellular transport, cell division, and signal transduction between nerve cells. Theoretical considerations have led to the idea that the membrane itself mediates protein self-organization in these processes through minimization of membrane curvature energy. Here, we present a combined experimental and numerical study in which we quantify these interactions directly for the first time. In our experimental model system we control the deformation of a lipid membrane by adhering colloidal particles. Using confocal microscopy, we establish that these membrane deformations cause an attractive interaction force leading to reversible binding. The attraction extends over 2.5 times the particle diameter and has a strength of three times the thermal energy (−3.3 kBT). Coarse-grained Monte-Carlo simulations of the system are in excellent agreement with the experimental results and prove that the measured interaction is independent of length scale. Our combined experimental and numerical results reveal membrane curvature as a common physical origin for interactions between any membrane-deforming objects, from nanometre-sized proteins to micrometre-sized particles.}, author = {van der Wel, Casper and Vahid, Afshin and Šarić, Anđela and Idema, Timon and Heinrich, Doris and Kraft, Daniela J.}, issn = {2045-2322}, journal = {Scientific Reports}, keywords = {multidisciplinary}, number = {1}, publisher = {Springer Nature}, title = {{Lipid membrane-mediated attraction between curvature inducing objects}}, doi = {10.1038/srep32825}, volume = {6}, year = {2016}, } @article{10378, abstract = {The ability of biological molecules to replicate themselves is the foundation of life, requiring a complex cellular machinery. However, a range of aberrant processes involve the self-replication of pathological protein structures without any additional assistance. One example is the autocatalytic generation of pathological protein aggregates, including amyloid fibrils, involved in neurodegenerative disorders. Here, we use computer simulations to identify the necessary requirements for the self-replication of fibrillar assemblies of proteins. We establish that a key physical determinant for this process is the affinity of proteins for the surfaces of fibrils. We find that self-replication can take place only in a very narrow regime of inter-protein interactions, implying a high level of sensitivity to system parameters and experimental conditions. We then compare our theoretical predictions with kinetic and biosensor measurements of fibrils formed from the Aβ peptide associated with Alzheimer’s disease. Our results show a quantitative connection between the kinetics of self-replication and the surface coverage of fibrils by monomeric proteins. These findings reveal the fundamental physical requirements for the formation of supra-molecular structures able to replicate themselves, and shed light on mechanisms in play in the proliferation of protein aggregates in nature.}, author = {Šarić, Anđela and Buell, Alexander K. and Meisl, Georg and Michaels, Thomas C. T. and Dobson, Christopher M. and Linse, Sara and Knowles, Tuomas P. J. and Frenkel, Daan}, issn = {1745-2481}, journal = {Nature Physics}, keywords = {general physics and astronomy}, number = {9}, pages = {874--880}, publisher = {Springer Nature}, title = {{Physical determinants of the self-replication of protein fibrils}}, doi = {10.1038/nphys3828}, volume = {12}, year = {2016}, } @article{10380, abstract = {Using non-equilibrium molecular dynamics simulations, it has been recently demonstrated that water molecules align in response to an imposed temperature gradient, resulting in an effective electric field. Here, we investigate how thermally induced fields depend on the underlying treatment of long-ranged interactions. For the short-ranged Wolf method and Ewald summation, we find the peak strength of the field to range between 2 × 107 and 5 × 107 V/m for a temperature gradient of 5.2 K/Å. Our value for the Wolf method is therefore an order of magnitude lower than the literature value [J. A. Armstrong and F. Bresme, J. Chem. Phys. 139, 014504 (2013); J. Armstrong et al., J. Chem. Phys. 143, 036101 (2015)]. We show that this discrepancy can be traced back to the use of an incorrect kernel in the calculation of the electrostatic field. More seriously, we find that the Wolf method fails to predict correct molecular orientations, resulting in dipole densities with opposite sign to those computed using Ewald summation. By considering two different multipole expansions, we show that, for inhomogeneous polarisations, the quadrupole contribution can be significant and even outweigh the dipole contribution to the field. Finally, we propose a more accurate way of calculating the electrostatic potential and the field. In particular, we show that averaging the microscopic field analytically to obtain the macroscopic Maxwell field reduces the error bars by up to an order of magnitude. As a consequence, the simulation times required to reach a given statistical accuracy decrease by up to two orders of magnitude.}, author = {Wirnsberger, P. and Fijan, D. and Šarić, Anđela and Neumann, M. and Dellago, C. and Frenkel, D.}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, keywords = {physical and theoretical chemistry, general physics and astronomy}, number = {22}, publisher = {American Institute of Physics}, title = {{Non-equilibrium simulations of thermally induced electric fields in water}}, doi = {10.1063/1.4953036}, volume = {144}, year = {2016}, } @article{10381, abstract = {We study phase behaviour of lipid-bilayer vesicles functionalised by ligand–receptor complexes made of synthetic DNA by introducing a modelling framework and a dedicated experimental platform. In particular, we perform Monte Carlo simulations that combine a coarse grained description of the lipid bilayer with state of art analytical models for multivalent ligand–receptor interactions. Using density of state calculations, we derive the partition function in pairs of vesicles and compute the number of ligand–receptor bonds as a function of temperature. Numerical results are compared to microscopy and fluorimetry experiments on large unilamellar vesicles decorated by DNA linkers carrying complementary overhangs. We find that vesicle aggregation is suppressed when the total number of linkers falls below a threshold value. Within the model proposed here, this is due to the higher configurational costs required to form inter-vesicle bridges as compared to intra-vesicle loops, which are in turn related to membrane deformability. Our findings and our numerical/experimental methodologies are applicable to the rational design of liposomes used as functional materials and drug delivery applications, as well as to study inter-membrane interactions in living systems, such as cell adhesion.}, author = {Bachmann, Stephan Jan and Kotar, Jurij and Parolini, Lucia and Šarić, Anđela and Cicuta, Pietro and Di Michele, Lorenzo and Mognetti, Bortolo Matteo}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {37}, pages = {7804--7817}, publisher = {Royal Society of Chemistry}, title = {{Melting transition in lipid vesicles functionalised by mobile DNA linkers}}, doi = {10.1039/c6sm01515h}, volume = {12}, year = {2016}, } @article{1057, abstract = {Far-field super-resolution fluorescence microscopy discerns fluorophores residing closer than the diffraction barrier by briefly transferring them in different (typically ON and OFF) states before detection. In coordinate-targeted super-resolution variants, such as stimulated emission depletion (STED) microscopy, this state difference is created by the intensity minima and maxima of an optical pattern, causing all fluorophores to assume the off state, for instance, except at the minima. Although strong spatial confinement of the on state enables high resolution, it also subjects the fluorophores to excess intensities and state cycles at the maxima. Here, we address these issues by driving the fluorophores into a second off state that is inert to the excess light. By using reversibly switchable fluorescent proteins as labels, our approach reduces bleaching and enhances resolution and contrast in live-cell STED microscopy. Using two or more transitions to off states is a useful strategy for augmenting the power of coordinate-targeted super-resolution microscopy.}, author = {Danzl, Johann G and Sidenstein, Sven and Gregor, Carola and Urban, Nicolai and Ilgen, Peter and Jakobs, Stefan and Hell, Stefan}, journal = {Nature Photonics}, number = {2}, pages = {122 -- 128}, publisher = {Nature Publishing Group}, title = {{Coordinate-targeted fluorescence nanoscopy with multiple off states}}, doi = {10.1038/nphoton.2015.266}, volume = {10}, year = {2016}, } @article{1059, abstract = {A range of bright and photostable rhodamines and carbopyronines with absorption maxima in the range of λ=500-630 nm were prepared, and enabled the specific labeling of cytoskeletal filaments using HaloTag technology followed by staining with 1 μm solutions of the dye-ligand conjugates. The synthesis, photophysical parameters, fluorogenic behavior, and structure-property relationships of the new dyes are discussed. Light microscopy with stimulated emission depletion (STED) provided one- and two-color images of living cells with an optical resolution of 40-60 nm.}, author = {Butkevich, Alexey and Mitronova, Gyuzel and Sidenstein, Sven and Klocke, Jessica and Kamin, Dirk and Meineke, Dirk and D'Este, Elisa and Kraemer, Philip and Danzl, Johann G and Belov, Vladimir and Hell, Stefan}, journal = {Angewandte Chemie - International Edition}, number = {10}, pages = {3290 -- 3294}, publisher = {Wiley-Blackwell}, title = {{Fluorescent rhodamines and fluorogenic carbopyronines for super-resolution STED microscopy in living cells}}, doi = {10.1002/anie.201511018}, volume = {55}, year = {2016}, } @article{1060, abstract = {Superresolution fluorescence microscopy of multiple fluorophores still requires development. Here we present simultaneous three-colour stimulated emission depletion (STED) nanoscopy relying on a single STED beam at 620 nm. Toggling the STED beam between two or more power levels ("multilevelSTEDv) optimizes resolution and contrast in all colour channels, which are intrinsically co-aligned and well separated. Three-colour recording is demonstrated by imaging the nanoscale cytoskeletal organization in cultured hippocampal neurons. The down to ∼35 nm resolution identified periodic actin/betaII spectrin lattices along dendrites and spines; however, at presynaptic and postsynaptic sites, these patterns were found to be absent. Both our multicolour scheme and the 620 nm STED line should be attractive for routine STED microscopy applications.}, author = {Sidenstein, Sven and D'Este, Elisa and Böhm, Marvin and Danzl, Johann G and Belov, Vladimir and Hell, Stefan}, journal = {Scientific Reports}, pages = {1 -- 8}, publisher = {Nature Publishing Group}, title = {{Multicolour multilevel STED nanoscopy of actin/spectrin organization at synapses}}, doi = {10.1038/srep26725}, volume = {6}, year = {2016}, } @inproceedings{1068, abstract = {Games on graphs provide the appropriate framework to study several central problems in computer science, such as verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with n vertices, m edges, and generalized Büchi objectives with k conjunctions. First, we present an algorithm with running time O(k*n^2), improving the previously known O(k*n*m) and O(k^2*n^2) worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with k_1 conjunctions in the antecedent and k_2 conjunctions in the consequent, and present an O(k_1 k_2 n^{2.5})-time algorithm, improving the previously known O(k_1*k_2*n*m)-time algorithm for m > n^{1.5}. }, author = {Chatterjee, Krishnendu and Dvorák, Wolfgang and Henzinger, Monika H and Loitzenbauer, Veronika}, location = {Krakow, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Conditionally optimal algorithms for generalized Büchi Games}}, doi = {10.4230/LIPIcs.MFCS.2016.25}, volume = {58}, year = {2016}, } @inproceedings{1069, abstract = {The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differen- tial equation has a zero in a given interval of real numbers. This is a fundamental reachability problem for continuous linear dynamical systems, such as linear hybrid automata and continuous- time Markov chains. Decidability of the problem is currently open – indeed decidability is open even for the sub-problem in which a zero is sought in a bounded interval. In this paper we show decidability of the bounded problem subject to Schanuel’s Conjecture, a unifying conjecture in transcendental number theory. We furthermore analyse the unbounded problem in terms of the frequencies of the differential equation, that is, the imaginary parts of the characteristic roots. We show that the unbounded problem can be reduced to the bounded problem if there is at most one rationally linearly independent frequency, or if there are two rationally linearly independent frequencies and all characteristic roots are simple. We complete the picture by showing that de- cidability of the unbounded problem in the case of two (or more) rationally linearly independent frequencies would entail a major new effectiveness result in Diophantine approximation, namely computability of the Diophantine-approximation types of all real algebraic numbers.}, author = {Chonev, Ventsislav K and Ouaknine, Joël and Worrell, James}, location = {Rome, Italy}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{On the skolem problem for continuous linear dynamical systems}}, doi = {10.4230/LIPIcs.ICALP.2016.100}, volume = {55}, year = {2016}, } @inproceedings{1070, abstract = {We present a logic that extends CTL (Computation Tree Logic) with operators that express synchronization properties. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. We show that our variant of CTL is decidable and that the model-checking problem is in Delta_3^P = P^{NP^NP}, and is DP-hard. We analogously consider quantifier exchange in extensions of CTL, and we present operators defined using basic operators of CTL* that express the occurrence of infinitely many synchronization points. We show that the model-checking problem remains in Delta_3^P. The distinguishing power of CTL and of our new logic coincide if the Next operator is allowed in the logics, thus the classical bisimulation quotient can be used for state-space reduction before model checking. }, author = {Chatterjee, Krishnendu and Doyen, Laurent}, location = {Rome, Italy}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{Computation tree logic for synchronization properties}}, doi = {10.4230/LIPIcs.ICALP.2016.98}, volume = {55}, year = {2016}, } @inproceedings{1071, abstract = {We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity. }, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, location = {Aarhus, Denmark}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik}, title = {{Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs}}, doi = {10.4230/LIPIcs.ESA.2016.28}, volume = {57}, year = {2016}, } @inproceedings{10746, abstract = {Vortex states in superconducting (SC) structures, their dynamics and ways to manipulate them are topics of great interest. We report a new method of magnetic force microscopy (MFM) that allows the study of vortex states in mesoscopic SC samples. For the case of a SC ring, which is biased to a half-integer flux quantum, the flux modulation through the ring caused by the motion of the magnetic tip drives the ring between two consecutive fluxoid states. The corresponding current switching in the ring produces strong position-dependent forces on the cantilever. In the regime where the frequency of the thermally activated jumps between fluxoid states is close to the frequency of the cantilever, large changes in the cantilever frequency and dissipation are observed. This effect may be understood as a stochastic resonance (SR) process. These changes in the cantilever’s mechanical properties are used to “image” the barrier energies between fluxoid states. Additionally, SR imaging of the barrier energies are used to study the effect of the locally applied magnetic field from the MFM tip on the barrier heights. We report the results of measurements for Al rings. Further, the same imaging technique can be applied to more sophisticated SC structures such as arrays of Josephson junctions.}, author = {Polshyn, Hryhoriy and Naibert, Tyler and Chua, Victor and Budakian, Raffi}, booktitle = {APS March Meeting 2016}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {2}, publisher = {American Physical Society}, title = {{Study of vortex states and dynamics in mesoscopic superconducting samples with MFM}}, volume = {61}, year = {2016}, } @inproceedings{10747, abstract = {Vortex interactions are key to explaining the behavior of many two dimensional superconducting systems. We report on the development of a technique to locally probe vortex interactions in a 2D array of Josephson junctions. Scanning a magnetic tip attached to an ultra-soft cantilever over the array produces changes in the frequency of the cantilever along certain lines, forming geometric patterns in the scans. Different tip-surface separations and external magnetic fields produce a number of different patterns. These patterns correspond to tip locations in which two configurations of vortices in the lattice have degenerate energies. By imaging the locations of these degeneracies, information on the local vortex interactions may be obtained.}, author = {Naibert, Tyler and Polshyn, Hryhoriy and Wolin, Brian and Durkin, Malcolm and Garrido Menacho, Rita and Shem, Ian Mondragon and Chua, Victor and Hughes, Taylor and Mason, Nadya and Budakian, Raffi}, booktitle = {APS March Meeting 2016}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {2}, publisher = {American Physical Society}, title = {{Stochastic resonance magnetic force microscopy imaging of Josephson arrays}}, volume = {61}, year = {2016}, }