@inproceedings{1653,
abstract = {A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO).
The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.},
author = {Okamoto, Tatsuaki and Pietrzak, Krzysztof Z and Waters, Brent and Wichs, Daniel},
location = {Auckland, New Zealand},
pages = {121 -- 145},
publisher = {Springer},
title = {{New realizations of somewhere statistically binding hashing and positional accumulators}},
doi = {10.1007/978-3-662-48797-6_6},
volume = {9452},
year = {2016},
}
@article{1662,
abstract = {We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.},
author = {Edelsbrunner, Herbert and Pausinger, Florian},
journal = {Advances in Mathematics},
pages = {674 -- 703},
publisher = {Academic Press},
title = {{Approximation and convergence of the intrinsic volume}},
doi = {10.1016/j.aim.2015.10.004},
volume = {287},
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{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 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},
}