TY - GEN
AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 5426
SN - 2664-1690
TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications
ER -
TY - GEN
AB - We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 5427
SN - 2664-1690
TI - Optimal tree-decomposition balancing and reachability on low treewidth graphs
ER -
TY - GEN
AB - Simulation is an attractive alternative for language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. For non-deterministic automata, while language inclusion is PSPACE-complete, simulation can be computed in polynomial time. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. Again, while fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable for mean-payoff automata and the decidability is open for discounted-sum automata, whereas the (quantitative) simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial time algorithms.
In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games. For example, whereas for mean-payoff and discounted-sum games, the players do not need memory to play optimally; we show in contrast that for simulation games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal strategies for both players require infinite memory in general, and (ii) for discounted-sum objectives, optimal strategies need not exist for both players. While the simulation games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory requirements for mean-payoff objectives) as compared to their counterpart without Büchi acceptance conditions, we still present pseudo-polynomial time algorithms to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff and weighted discounted-sum automata.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Velner, Yaron
ID - 5428
SN - 2664-1690
TI - Quantitative fair simulation games
ER -
TY - JOUR
AB - We consider homogeneous Bose gas in a large cubic box with periodic boundary conditions, at zero temperature. We analyze its excitation spectrum in a certain kind of a mean-field infinite-volume limit. We prove that under appropriate conditions the excitation spectrum has the form predicted by the Bogoliubov approximation. Our result can be viewed as an extension of the result of Seiringer (Commun. Math. Phys.306:565–578, 2011) to large volumes.
AU - Dereziński, Jan
AU - Napiórkowski, Marcin M
ID - 5813
IS - 12
JF - Annales Henri Poincaré
SN - 1424-0637
TI - Excitation spectrum of interacting bosons in the Mean-Field Infinite-Volume limit
VL - 15
ER -
TY - JOUR
AB - We demonstrate a many-atom-cavity system with a high-finesse dual-wavelength standing wave cavity in which all participating rubidium atoms are nearly identically coupled to a 780-nm cavity mode. This homogeneous coupling is enforced by a one-dimensional optical lattice formed by the field of a 1560-nm cavity mode.
AU - Lee, Jongmin
AU - Vrijsen, Geert
AU - Teper, Igor
AU - Onur Hosten
AU - Kasevich, Mark A
ID - 589
IS - 13
JF - Optics Letters
TI - Many-atom-cavity QED system with homogeneous atom-cavity coupling
VL - 39
ER -
TY - JOUR
AU - Linneweber, Gerit A.
AU - Jacobson, Jake
AU - Busch, Karl Emanuel
AU - Hudry, Bruno
AU - Christov, Christo P.
AU - Dormann, Dirk
AU - Yuan, Michaela
AU - Otani, Tomoki
AU - Knust, Elisabeth
AU - de Bono, Mario
AU - Miguel-Aliaga, Irene
ID - 6122
IS - 1-2
JF - Cell
SN - 0092-8674
TI - Neuronal control of metabolism through nutrient-dependent modulation of tracheal branching
VL - 156
ER -
TY - JOUR
AB - Despite the importance of G-protein coupled receptors (GPCRs) their biogenesis is poorly understood. Like vertebrates, C. elegans uses a large family of GPCRs as chemoreceptors. A subset of these receptors, such as ODR-10, requires the odr-4 and odr-8 genes to be appropriately localized to sensory cilia. The odr-4 gene encodes a conserved tail-anchored transmembrane protein; the molecular identity of odr-8 is unknown. Here, we show that odr-8 encodes the C. elegans ortholog of Ufm1-specific protease 2 (UfSP2). UfSPs are cysteine proteases identified biochemically by their ability to liberate the ubiquitin-like modifier Ufm1 from its pro-form and protein conjugates. ODR-8/UfSP2 and ODR-4 are expressed in the same set of twelve chemosensory neurons, and physically interact at the ER membrane. ODR-4 also binds ODR-10, suggesting that an ODR-4/ODR-8 complex promotes GPCR folding, maturation, or export from the ER. The physical interaction between human ODR4 and UfSP2 suggests that this complex's role in GPCR biogenesis may be evolutionarily conserved. Unexpectedly, mutant versions of ODR-8/UfSP2 lacking catalytic residues required for protease activity can rescue all odr-8 mutant phenotypes tested. Moreover, deleting C. elegans ufm-1 does not alter chemoreceptor traffic to cilia, either in wild type or in odr-8 mutants. Thus, UfSP2 proteins have protease- and Ufm1-independent functions in GPCR biogenesis.
AU - Chen, Changchun
AU - Itakura, Eisuke
AU - Weber, Katherine P.
AU - Hegde, Ramanujan S.
AU - de Bono, Mario
ID - 6124
IS - 3
JF - PLoS Genetics
SN - 1553-7404
TI - An ER complex of ODR-4 and ODR-8/Ufm1 specific protease 2 promotes GPCR maturation by a Ufm1-independent mechanism
VL - 10
ER -
TY - JOUR
AB - Aerobic animals constantly monitor and adapt to changes in O2 levels. The molecular mechanisms involved in sensing O2 are, however, incompletely understood. Previous studies showed that a hexacoordinated globin called GLB-5 tunes the dynamic range of O2-sensing neurons in natural C. elegans isolates, but is defective in the N2 lab reference strain (McGrath et al., 2009; Persson et al., 2009). GLB-5 enables a sharp behavioral switch when O2 changes between 21 and 17%. Here, we show that GLB-5 also confers rapid behavioral and cellular recovery from exposure to hypoxia. Hypoxia reconfigures O2-evoked Ca2+ responses in the URX O2 sensors, and GLB-5 enables rapid recovery of these responses upon re-oxygenation. Forward genetic screens indicate that GLB-5's effects on O2 sensing require PDL-1, the C. elegans ortholog of mammalian PrBP/PDE6δ protein. In mammals, PDE6δ regulates the traffic and activity of prenylated proteins (Zhang et al., 2004; Norton et al., 2005). PDL-1 promotes localization of GCY-33 and GCY-35, atypical soluble guanylate cyclases that act as O2 sensors, to the dendritic endings of URX and BAG neurons, where they colocalize with GLB-5. Both GCY-33 and GCY-35 are predicted to be prenylated. Dendritic localization is not essential for GCY-35 to function as an O2 sensor, but disrupting pdl-1 alters the URX neuron's O2 response properties. Functional GLB-5 can restore dendritic localization of GCY-33 in pdl-1 mutants, suggesting GCY-33 and GLB-5 are in a complex. Our data suggest GLB-5 and the soluble guanylate cyclases operate in close proximity to sculpt O2 responses.
AU - Gross, E.
AU - Soltesz, Z.
AU - Oda, S.
AU - Zelmanovich, V.
AU - Abergel, Z.
AU - de Bono, Mario
ID - 6126
IS - 50
JF - Journal of Neuroscience
SN - 0270-6474
TI - GLOBIN-5-dependent O2 responses are regulated by PDL-1/PrBP that targets prenylated soluble guanylate cyclases to dendritic endings
VL - 34
ER -
TY - JOUR
AB - Nous étudions le comportement asymptotique du nombre de variétés dans une certaine classe ne satisfaisant pas le principe de Hasse. Cette étude repose sur des résultats récemmentobtenus par Colliot-Thélène.
AU - Bretèche, Régis de la
AU - Browning, Timothy D
ID - 6319
IS - 1
JF - Journal de Théorie des Nombres de Bordeaux
SN - 1246-7405
TI - Contre-exemples au principe de Hasse pour certains tores coflasques
VL - 26
ER -
TY - JOUR
AB - We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family C inter = {C α : α ∈ [0, 1j}, where C α|α=1 is the original polar code, and C α|α=0 is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Urbanke, Rudiger
ID - 6739
IS - 9
JF - IEEE Transactions on Communications
SN - 0090-6778
TI - From polar to Reed-Muller codes: A technique to improve the finite-length performance
VL - 62
ER -
TY - CONF
AB - We describe coding techniques that achieve the capacity of a discrete memoryless asymmetric channel. To do so, we discuss how recent advances in coding for symmetric channels yield more efficient solutions also for the asymmetric case. In more detail, we consider three basic approaches. The first one is Gallager's scheme that concatenates a linear code with a non-linear mapper, in order to bias the input distribution. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Further, we derive a scaling law between the gap to capacity, the cardinality of channel input and output alphabets, and the required size of the mapper. The second one is an integrated approach in which the coding scheme is used both for source coding, in order to create codewords with the capacity-achieving distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third approach is based on an idea due to Böcherer and Mathar and separates completely the two tasks of source coding and channel coding by “chaining” together several codewords. We prove that we can combine any suitable source code with any suitable channel code in order to provide optimal schemes for asymmetric channels. In particular, polar codes and spatially coupled codes fulfill the required conditions.
AU - Mondelli, Marco
AU - Urbanke, Rudiger
AU - Hassani, Hamed
ID - 6740
T2 - 52nd Annual Allerton Conference on Communication, Control, and Computing
TI - How to achieve the capacity of asymmetric channels
ER -
TY - GEN
AU - Huszár, Kristóf
AU - Rolinek, Michal
ID - 7038
TI - Playful Math - An introduction to mathematical games
ER -
TY - JOUR
AB - Spin and orbital quantum numbers play a key role in the physics of Mott insulators, but in most systems they are connected only indirectly—via the Pauli exclusion principle and the Coulomb interaction. Iridium-based oxides (iridates) introduce strong spin–orbit coupling directly, such that these numbers become entwined together and the Mott physics attains a strong orbital character. In the layered honeycomb iridates this is thought to generate highly spin–anisotropic magnetic interactions, coupling the spin to a given spatial direction of exchange and leading to strongly frustrated magnetism. Here we report a new iridate structure that has the same local connectivity as the layered honeycomb and exhibits striking evidence for highly spin–anisotropic exchange. The basic structural units of this material suggest that a new family of three-dimensional structures could exist, the ‘harmonic honeycomb’ iridates, of which the present compound is the first example.
AU - Modic, Kimberly A
AU - Smidt, Tess E.
AU - Kimchi, Itamar
AU - Breznay, Nicholas P.
AU - Biffin, Alun
AU - Choi, Sungkyun
AU - Johnson, Roger D.
AU - Coldea, Radu
AU - Watkins-Curry, Pilanda
AU - McCandless, Gregory T.
AU - Chan, Julia Y.
AU - Gandara, Felipe
AU - Islam, Z.
AU - Vishwanath, Ashvin
AU - Shekhter, Arkady
AU - McDonald, Ross D.
AU - Analytis, James G.
ID - 7071
JF - Nature Communications
SN - 2041-1723
TI - Realization of a three-dimensional spin–anisotropic harmonic honeycomb iridate
VL - 5
ER -
TY - JOUR
AB - We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
AU - Krinninger, Sebastian
AU - Loitzenbauer, Veronika
AU - Raskin, Michael
ID - 1375
IS - C
JF - Theoretical Computer Science
TI - Approximating the minimum cycle mean
VL - 547
ER -
TY - CONF
AB - Fault-tolerant distributed algorithms play an important role in ensuring the reliability of many software applications. In this paper we consider distributed algorithms whose computations are organized in rounds. To verify the correctness of such algorithms, we reason about (i) properties (such as invariants) of the state, (ii) the transitions controlled by the algorithm, and (iii) the communication graph. We introduce a logic that addresses these points, and contains set comprehensions with cardinality constraints, function symbols to describe the local states of each process, and a limited form of quantifier alternation to express the verification conditions. We show its use in automating the verification of consensus algorithms. In particular, we give a semi-decision procedure for the unsatisfiability problem of the logic and identify a decidable fragment. We successfully applied our framework to verify the correctness of a variety of consensus algorithms tolerant to both benign faults (message loss, process crashes) and value faults (message corruption).
AU - Dragoi, Cezara
AU - Henzinger, Thomas A
AU - Veith, Helmut
AU - Widder, Josef
AU - Zufferey, Damien
ID - 1392
TI - A logic-based framework for verifying consensus algorithms
VL - 8318
ER -
TY - CONF
AB - Probabilistic programs are usual functional or imperative programs with two added constructs: (1) the ability to draw values at random from distributions, and (2) the ability to condition values of variables in a program via observations. Models from diverse application areas such as computer vision, coding theory, cryptographic protocols, biology and reliability analysis can be written as probabilistic programs. Probabilistic inference is the problem of computing an explicit representation of the probability distribution implicitly specified by a probabilistic program. Depending on the application, the desired output from inference may vary-we may want to estimate the expected value of some function f with respect to the distribution, or the mode of the distribution, or simply a set of samples drawn from the distribution. In this paper, we describe connections this research area called \Probabilistic Programming" has with programming languages and software engineering, and this includes language design, and the static and dynamic analysis of programs. We survey current state of the art and speculate on promising directions for future research.
AU - Gordon, Andrew
AU - Henzinger, Thomas A
AU - Nori, Aditya
AU - Rajamani, Sriram
ID - 1393
T2 - Proceedings of the on Future of Software Engineering
TI - Probabilistic programming
ER -
TY - CONF
AB - The Wigner-Dyson-Gaudin-Mehta conjecture asserts that the local eigenvalue statistics of large real and complex Hermitian matrices with independent, identically distributed entries are universal in a sense that they depend only on the symmetry class of the matrix and otherwise are independent of the details of the distribution. We present the recent solution to this half-century old conjecture. We explain how stochastic tools, such as the Dyson Brownian motion, and PDE ideas, such as De Giorgi-Nash-Moser regularity theory, were combined in the solution. We also show related results for log-gases that represent a universal model for strongly correlated systems. Finally, in the spirit of Wigner’s original vision, we discuss the extensions of these universality results to more realistic physical systems such as random band matrices.
AU - Erdös, László
ID - 1507
TI - Random matrices, log-gases and Hölder regularity
VL - 3
ER -
TY - CONF
AB - We present a rigorous derivation of the BCS gap equation for superfluid fermionic gases with point interactions. Our starting point is the BCS energy functional, whose minimizer we investigate in the limit when the range of the interaction potential goes to zero.
AU - Bräunlich, Gerhard
AU - Hainzl, Christian
AU - Seiringer, Robert
ID - 1516
T2 - Proceedings of the QMath12 Conference
TI - On the BCS gap equation for superfluid fermionic gases
ER -
TY - JOUR
AB - We propose a method for propagating edit operations in 2D vector graphics, based on geometric relationship functions. These functions quantify the geometric relationship of a point to a polygon, such as the distance to the boundary or the direction to the closest corner vertex. The level sets of the relationship functions describe points with the same relationship to a polygon. For a given query point, we first determine a set of relationships to local features, construct all level sets for these relationships, and accumulate them. The maxima of the resulting distribution are points with similar geometric relationships. We show extensions to handle mirror symmetries, and discuss the use of relationship functions as local coordinate systems. Our method can be applied, for example, to interactive floorplan editing, and it is especially useful for large layouts, where individual edits would be cumbersome. We demonstrate populating 2D layouts with tens to hundreds of objects by propagating relatively few edit operations.
AU - Guerrero, Paul
AU - Jeschke, Stefan
AU - Wimmer, Michael
AU - Wonka, Peter
ID - 1629
IS - 2
JF - ACM Transactions on Graphics
TI - Edit propagation using geometric relationship functions
VL - 33
ER -
TY - CONF
AB - We extend the notion of verifiable random functions (VRF) to constrained VRFs, which generalize the concept of constrained pseudorandom functions, put forward by Boneh and Waters (Asiacrypt’13), and independently by Kiayias et al. (CCS’13) and Boyle et al. (PKC’14), who call them delegatable PRFs and functional PRFs, respectively. In a standard VRF the secret key sk allows one to evaluate a pseudorandom function at any point of its domain; in addition, it enables computation of a non-interactive proof that the function value was computed correctly. In a constrained VRF from the key sk one can derive constrained keys skS for subsets S of the domain, which allow computation of function values and proofs only at points in S. After formally defining constrained VRFs, we derive instantiations from the multilinear-maps-based constrained PRFs by Boneh and Waters, yielding a VRF with constrained keys for any set that can be decided by a polynomial-size circuit. Our VRFs have the same function values as the Boneh-Waters PRFs and are proved secure under the same hardness assumption, showing that verifiability comes at no cost. Constrained (functional) VRFs were stated as an open problem by Boyle et al.
AU - Fuchsbauer, Georg
ED - Abdalla, Michel
ED - De Prisco, Roberto
ID - 1643
T2 - SCN 2014
TI - Constrained Verifiable Random Functions
VL - 8642
ER -