@article{1491,
abstract = {We study the ground state of a trapped Bose gas, starting from the full many-body Schrödinger Hamiltonian, and derive the non-linear Schrödinger energy functional in the limit of a large particle number, when the interaction potential converges slowly to a Dirac delta function. Our method is based on quantitative estimates on the discrepancy between the full many-body energy and its mean-field approximation using Hartree states. These are proved using finite dimensional localization and a quantitative version of the quantum de Finetti theorem. Our approach covers the case of attractive interactions in the regime of stability. In particular, our main new result is a derivation of the 2D attractive non-linear Schrödinger ground state.},
author = {Lewin, Mathieu and Nam, Phan and Rougerie, Nicolas},
journal = {Transactions of the American Mathematical Society},
number = {9},
pages = {6131 -- 6157},
publisher = {American Mathematical Society},
title = {{The mean-field approximation and the non-linear Schrödinger functional for trapped Bose gases}},
doi = {10.1090/tran/6537},
volume = {368},
year = {2016},
}
@article{1492,
abstract = {To sustain a lifelong ability to initiate organs, plants retain pools of undifferentiated cells with a preserved prolif eration capacity. The root pericycle represents a unique tissue with conditional meristematic activity, and its tight control determines initiation of lateral organs. Here we show that the meristematic activity of the pericycle is constrained by the interaction with the adjacent endodermis. Release of these restraints by elimination of endo dermal cells by single-cell ablation triggers the pericycle to re-enter the cell cycle. We found that endodermis removal substitutes for the phytohormone auxin-dependent initiation of the pericycle meristematic activity. However, auxin is indispensable to steer the cell division plane orientation of new organ-defining divisions. We propose a dual, spatiotemporally distinct role for auxin during lateral root initiation. In the endodermis, auxin releases constraints arising from cell-to-cell interactions that compromise the pericycle meristematic activity, whereas, in the pericycle, auxin defines the orientation of the cell division plane to initiate lateral roots.},
author = {Marhavy, Peter and Montesinos López, Juan C and Abuzeineh, Anas and Van Damme, Daniël and Vermeer, Joop and Duclercq, Jérôme and Rakusova, Hana and Marhavá, Petra and Friml, Jirí and Geldner, Niko and Benková, Eva},
journal = {Genes and Development},
number = {4},
pages = {471 -- 483},
publisher = {Cold Spring Harbor Laboratory Press},
title = {{Targeted cell elimination reveals an auxin-guided biphasic mode of lateral root initiation}},
doi = {10.1101/gad.276964.115},
volume = {30},
year = {2016},
}
@article{1493,
abstract = {We introduce a new method for deriving the time-dependent Hartree or Hartree-Fock equations as an effective mean-field dynamics from the microscopic Schrödinger equation for fermionic many-particle systems in quantum mechanics. The method is an adaption of the method used in Pickl (Lett. Math. Phys. 97 (2) 151–164 2011) for bosonic systems to fermionic systems. It is based on a Gronwall type estimate for a suitable measure of distance between the microscopic solution and an antisymmetrized product state. We use this method to treat a new mean-field limit for fermions with long-range interactions in a large volume. Some of our results hold for singular attractive or repulsive interactions. We can also treat Coulomb interaction assuming either a mild singularity cutoff or certain regularity conditions on the solutions to the Hartree(-Fock) equations. In the considered limit, the kinetic and interaction energy are of the same order, while the average force is subleading. For some interactions, we prove that the Hartree(-Fock) dynamics is a more accurate approximation than a simpler dynamics that one would expect from the subleading force. With our method we also treat the mean-field limit coupled to a semiclassical limit, which was discussed in the literature before, and we recover some of the previous results. All results hold for initial data close (but not necessarily equal) to antisymmetrized product states and we always provide explicit rates of convergence.},
author = {Petrat, Sören P and Pickl, Peter},
journal = {Mathematical Physics, Analysis and Geometry},
number = {1},
publisher = {Springer},
title = {{A new method and a new scaling for deriving fermionic mean-field dynamics}},
doi = {10.1007/s11040-016-9204-2},
volume = {19},
year = {2016},
}
@article{1496,
abstract = {The two-photon 1s2 2s 2p 3P0 1s22s2 1S0 transition in berylliumlike ions is theoretically investigated within a fully relativistic framework and a second-order perturbation theory. We focus our analysis on how electron correlation, as well as the negative-energy spectrum, can affect the forbidden E1M1 decay rate. For this purpose, we include the electronic correlation via an effective local potential and within a single configuration-state model. Due to its experimental interest, evaluations of decay rates are performed for berylliumlike xenon and uranium. We find that the negative-energy contribution can be neglected at the present level of accuracy in the evaluation of the decay rate. On the other hand, if contributions of electronic correlation are not carefully taken into account, it may change the lifetime of the metastable state by up to 20%. By performing a full-relativistic jj-coupling calculation, we found a decrease of the decay rate by two orders of magnitude compared to non-relativistic LS-coupling calculations, for the selected heavy ions.},
author = {Amaro, Pedro and Fratini, Filippo and Safari, Laleh and Machado, Jorge and Guerra, Mauro and Indelicato, Paul and Santos, José},
journal = {Physical Review A - Atomic, Molecular, and Optical Physics},
number = {3},
publisher = {American Physical Society},
title = {{Relativistic evaluation of the two-photon decay of the metastable 1s22s2p3P0 state in berylliumlike ions with an effective-potential model}},
doi = {10.1103/PhysRevA.93.032502},
volume = {93},
year = {2016},
}
@article{1518,
abstract = {The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno.},
author = {Lohse, Konrad and Chmelik, Martin and Martin, Simon and Barton, Nicholas H},
journal = {Genetics},
number = {2},
pages = {775 -- 786},
publisher = {Genetics Society of America},
title = {{Efficient strategies for calculating blockwise likelihoods under the coalescent}},
doi = {10.1534/genetics.115.183814},
volume = {202},
year = {2016},
}
@article{1522,
abstract = {We classify smooth Brunnian (i.e., unknotted on both components) embeddings (S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to an explicitly constructed embedding fk,m,n for some integers k, m, n such that m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2 × S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such that the componentwise embedded connected sum f # g is isotopic to f # g′ but g is not isotopic to g′.},
author = {Avvakumov, Serhii},
journal = {Moscow Mathematical Journal},
number = {1},
pages = {1 -- 25},
publisher = {Independent University of Moscow},
title = {{The classification of certain linked 3-manifolds in 6-space}},
volume = {16},
year = {2016},
}
@article{1523,
abstract = {For random graphs, the containment problem considers the probability that a binomial random graph G(n, p) contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at p = 1/n. We consider a natural analogue of this question for higher-dimensional random complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold for containing a subdivision of any fixed complete 2-complex. For higher dimensions k > 2, we get that p = O(n−1/k) is an upper bound for the threshold probability of containing a subdivision of a fixed k-dimensional complex.},
author = {Gundert, Anna and Wagner, Uli},
journal = {Proceedings of the American Mathematical Society},
number = {4},
pages = {1815 -- 1828},
publisher = {American Mathematical Society},
title = {{On topological minors in random simplicial complexes}},
doi = {10.1090/proc/12824},
volume = {144},
year = {2016},
}
@inproceedings{1524,
abstract = {When designing genetic circuits, the typical primitives used in major existing modelling formalisms are gene interaction graphs, where edges between genes denote either an activation or inhibition relation. However, when designing experiments, it is important to be precise about the low-level mechanistic details as to how each such relation is implemented. The rule-based modelling language Kappa allows to unambiguously specify mechanistic details such as DNA binding sites, dimerisation of transcription factors, or co-operative interactions. Such a detailed description comes with complexity and computationally costly executions. We propose a general method for automatically transforming a rule-based program, by eliminating intermediate species and adjusting the rate constants accordingly. To the best of our knowledge, we show the first automated reduction of rule-based models based on equilibrium approximations.
Our algorithm is an adaptation of an existing algorithm, which was designed for reducing reaction-based programs; our version of the algorithm scans the rule-based Kappa model in search for those interaction patterns known to be amenable to equilibrium approximations (e.g. Michaelis-Menten scheme). Additional checks are then performed in order to verify if the reduction is meaningful in the context of the full model. The reduced model is efficiently obtained by static inspection over the rule-set. The tool is tested on a detailed rule-based model of a λ-phage switch, which lists 92 rules and 13 agents. The reduced model has 11 rules and 5 agents, and provides a dramatic reduction in simulation time of several orders of magnitude.},
author = {Beica, Andreea and Guet, Calin C and Petrov, Tatjana},
location = {Madrid, Spain},
pages = {173 -- 191},
publisher = {Springer},
title = {{Efficient reduction of kappa models by static inspection of the rule-set}},
doi = {10.1007/978-3-319-26916-0_10},
volume = {9271},
year = {2016},
}
@inproceedings{1526,
abstract = {We present the first study of robustness of systems that are both timed as well as reactive (I/O). We study the behavior of such timed I/O systems in the presence of uncertain inputs and formalize their robustness using the analytic notion of Lipschitz continuity: a timed I/O system is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using similarity functions over timed words such as the timed version of the Manhattan distance and the Skorokhod distance. We consider two models of timed I/O systems — timed transducers and asynchronous sequential circuits. We show that K-robustness of timed transducers can be decided in polynomial space under certain conditions. For asynchronous sequential circuits, we reduce K-robustness w.r.t. timed Manhattan distances to K-robustness of discrete letter-to-letter transducers and show PSpace-completeness of the problem.},
author = {Henzinger, Thomas A and Otop, Jan and Samanta, Roopsha},
location = {St. Petersburg, FL, USA},
pages = {250 -- 267},
publisher = {Springer},
title = {{Lipschitz robustness of timed I/O systems}},
doi = {10.1007/978-3-662-49122-5_12},
volume = {9583},
year = {2016},
}
@article{1529,
abstract = {We consider partially observable Markov decision processes (POMDPs) with a set of target states and an integer cost associated with every transition. The optimization objective we study asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush},
journal = {Artificial Intelligence},
pages = {26 -- 48},
publisher = {Elsevier},
title = {{Optimal cost almost-sure reachability in POMDPs}},
doi = {10.1016/j.artint.2016.01.007},
volume = {234},
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{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},
}
@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},
}
@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},
}
@article{1081,
abstract = {The asymmetric localization of proteins in the plasma membrane domains of eukaryotic cells is a fundamental manifestation of cell polarity that is central to multicellular organization and developmental patterning. In plants, the mechanisms underlying the polar localization of cargo proteins are still largely unknown and appear to be fundamentally distinct from those operating in mammals. Here, we present a systematic, quantitative comparative analysis of the polar delivery and subcellular localization of proteins that characterize distinct polar plasma membrane domains in plant cells. The combination of microscopic analyses and computational modeling revealed a mechanistic framework common to diverse polar cargos and underlying the establishment and maintenance of apical, basal, and lateral polar domains in plant cells. This mechanism depends on the polar secretion, constitutive endocytic recycling, and restricted lateral diffusion of cargos within the plasma membrane. Moreover, our observations suggest that polar cargo distribution involves the individual protein potential to form clusters within the plasma membrane and interact with the extracellular matrix. Our observations provide insights into the shared cellular mechanisms of polar cargo delivery and polarity maintenance in plant cells.},
author = {Łangowski, Łukasz and Wabnik, Krzysztof T and Li, Hongjiang and Vanneste, Steffen and Naramoto, Satoshi and Tanaka, Hirokazu and Friml, Jirí},
journal = {Cell Discovery},
publisher = {Nature Publishing Group},
title = {{Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells}},
doi = {10.1038/celldisc.2016.18},
volume = {2},
year = {2016},
}
@inproceedings{1082,
abstract = {In many applications, it is desirable to extract only the relevant aspects of data. A principled way to do this is the information bottleneck (IB) method, where one seeks a code that maximises information about a relevance variable, Y, while constraining the information encoded about the original data, X. Unfortunately however, the IB method is computationally demanding when data are high-dimensional and/or non-gaussian. Here we propose an approximate variational scheme for maximising a lower bound on the IB objective, analogous to variational EM. Using this method, we derive an IB algorithm to recover features that are both relevant and sparse. Finally, we demonstrate how kernelised versions of the algorithm can be used to address a broad range of problems with non-linear relation between X and Y.},
author = {Chalk, Matthew J and Marre, Olivier and Tkacik, Gasper},
location = {Barcelona, Spain},
pages = {1965--1973},
publisher = {Neural Information Processing Systems},
title = {{Relevant sparse codes with variational information bottleneck}},
volume = {29},
year = {2016},
}
@inproceedings{1090,
abstract = { While weighted automata provide a natural framework to express quantitative properties, many basic properties like average response time cannot be expressed with weighted automata. Nested weighted automata extend weighted automata and consist of a master automaton and a set of slave automata that are invoked by the master automaton. Nested weighted automata are strictly more expressive than weighted automata (e.g., average response time can be expressed with nested weighted automata), but the basic decision questions have higher complexity (e.g., for deterministic automata, the emptiness question for nested weighted automata is PSPACE-hard, whereas the corresponding complexity for weighted automata is PTIME). We consider a natural subclass of nested weighted automata where at any point at most a bounded number k of slave automata can be active. We focus on automata whose master value function is the limit average. We show that these nested weighted automata with bounded width are strictly more expressive than weighted automata (e.g., average response time with no overlapping requests can be expressed with bound k=1, but not with non-nested weighted automata). We show that the complexity of the basic decision problems (i.e., emptiness and universality) for the subclass with k constant matches the complexity for weighted automata. Moreover, when k is part of the input given in unary we establish PSPACE-completeness.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
location = {Krakow; Poland},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Nested weighted limit-average automata of bounded width}},
doi = {10.4230/LIPIcs.MFCS.2016.24},
volume = {58},
year = {2016},
}