@article{3256, abstract = {We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n.}, author = {Edelsbrunner, Herbert and Kerber, Michael}, journal = {Discrete & Computational Geometry}, number = {2}, pages = {393 -- 414}, publisher = {Springer}, title = {{Dual complexes of cubical subdivisions of ℝn}}, doi = {10.1007/s00454-011-9382-4}, volume = {47}, year = {2012}, } @article{3257, abstract = {Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms.}, author = {Kolmogorov, Vladimir}, journal = {Discrete Applied Mathematics}, number = {4-5}, pages = {416 -- 426}, publisher = {Elsevier}, title = {{Generalized roof duality and bisubmodular functions}}, doi = {10.1016/j.dam.2011.10.026}, volume = {160}, year = {2012}, } @article{3258, abstract = {CA3 pyramidal neurons are important for memory formation and pattern completion in the hippocampal network. It is generally thought that proximal synapses from the mossy fibers activate these neurons most efficiently, whereas distal inputs from the perforant path have a weaker modulatory influence. We used confocally targeted patch-clamp recording from dendrites and axons to map the activation of rat CA3 pyramidal neurons at the subcellular level. Our results reveal two distinct dendritic domains. In the proximal domain, action potentials initiated in the axon backpropagate actively with large amplitude and fast time course. In the distal domain, Na+ channel–mediated dendritic spikes are efficiently initiated by waveforms mimicking synaptic events. CA3 pyramidal neuron dendrites showed a high Na+-to-K+ conductance density ratio, providing ideal conditions for active backpropagation and dendritic spike initiation. Dendritic spikes may enhance the computational power of CA3 pyramidal neurons in the hippocampal network.}, author = {Kim, Sooyun and Guzmán, José and Hu, Hua and Jonas, Peter M}, issn = {1546-1726}, journal = {Nature Neuroscience}, number = {4}, pages = {600 -- 606}, publisher = {Nature Publishing Group}, title = {{Active dendrites support efficient initiation of dendritic spikes in hippocampal CA3 pyramidal neurons}}, doi = {10.1038/nn.3060}, volume = {15}, year = {2012}, } @inproceedings{3265, abstract = {We propose a mid-level statistical model for image segmentation that composes multiple figure-ground hypotheses (FG) obtained by applying constraints at different locations and scales, into larger interpretations (tilings) of the entire image. Inference is cast as optimization over sets of maximal cliques sampled from a graph connecting all non-overlapping figure-ground segment hypotheses. Potential functions over cliques combine unary, Gestalt-based figure qualities, and pairwise compatibilities among spatially neighboring segments, constrained by T-junctions and the boundary interface statistics of real scenes. Learning the model parameters is based on maximum likelihood, alternating between sampling image tilings and optimizing their potential function parameters. State of the art results are reported on the Berkeley and Stanford segmentation datasets, as well as VOC2009, where a 28% improvement was achieved.}, author = {Ion, Adrian and Carreira, Joao and Sminchisescu, Cristian}, location = {Barcelona, Spain}, publisher = {IEEE}, title = {{Image segmentation by figure-ground composition into maximal cliques}}, doi = {10.1109/ICCV.2011.6126486}, year = {2012}, } @inbook{3277, abstract = {The problem of the origin of metazoa is becoming more urgent in the context of astrobiology. By now it is clear that clues to the understanding of this crucial transition in the evolution of life can arise in a fourth pathway besides the three possibilities in the quest for simplicity outlined by Bonner in his classical book. In other words, solar system exploration seems to be one way in the long-term to elucidate the simplicity of evolutionary development. We place these ideas in the context of different inheritance systems, namely the genotypic and phenotypic replicators with limited or unlimited heredity, and ask which of these can support multicellular development, and to which degree of complexity. However, the quest for evidence on the evolution of biotas from planets around other stars does not seem to be feasible with present technology with direct visualization of living organisms on exoplanets. But this may be attempted on the Galilean moons of Jupiter where there is a possibility of detecting reliable biomarkers in the next decade with the Europa Jupiter System Mission, in view of recent progress by landing micropenetrators on planetary, or satellite surfaces. Mars is a second possibility in the inner Solar System, in spite of the multiple difficulties faced by the fleet of past, present and future missions. We discuss a series of preliminary ideas for elucidating the origin of metazoan analogues with available instrumentation in potential payloads of feasible space missions to the Galilean moons.}, author = {de Vladar, Harold and Chela Flores, Julian}, booktitle = {Life on Earth and other planetary bodies}, pages = {387 -- 405}, publisher = {Springer}, title = {{Can the evolution of multicellularity be anticipated in the exploration of the solar system?}}, doi = {10.1007/978-94-007-4966-5_22}, volume = {24}, year = {2012}, } @inproceedings{3279, abstract = {We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound q on the number of queries to the PRF. Our construction requires only O(logq) invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG. For example, starting from an exponentially secure PRG {0,1} n → {0,1} 2n, we get a PRF which is exponentially secure if queried at most q = exp(√n)times and where each invocation of the PRF requires Θ(√n) queries to the underlying PRG. This is much less than the Θ(n) required by known constructions. }, author = {Jain, Abhishek and Pietrzak, Krzysztof Z and Tentes, Aris}, location = {Taormina, Sicily, Italy}, pages = {369 -- 382}, publisher = {Springer}, title = {{Hardness preserving constructions of pseudorandom functions}}, doi = {10.1007/978-3-642-28914-9_21}, volume = {7194}, year = {2012}, } @inproceedings{3280, abstract = {The (decisional) learning with errors problem (LWE) asks to distinguish "noisy" inner products of a secret vector with random vectors from uniform. The learning parities with noise problem (LPN) is the special case where the elements of the vectors are bits. In recent years, the LWE and LPN problems have found many applications in cryptography. In this paper we introduce a (seemingly) much stronger adaptive assumption, called "subspace LWE" (SLWE), where the adversary can learn the inner product of the secret and random vectors after they were projected into an adaptively and adversarially chosen subspace. We prove that, surprisingly, the SLWE problem mapping into subspaces of dimension d is almost as hard as LWE using secrets of length d (the other direction is trivial.) This result immediately implies that several existing cryptosystems whose security is based on the hardness of the LWE/LPN problems are provably secure in a much stronger sense than anticipated. As an illustrative example we show that the standard way of using LPN for symmetric CPA secure encryption is even secure against a very powerful class of related key attacks. }, author = {Pietrzak, Krzysztof Z}, location = {Taormina, Sicily, Italy}, pages = {548 -- 563}, publisher = {Springer}, title = {{Subspace LWE}}, doi = {10.1007/978-3-642-28914-9_31}, volume = {7194}, year = {2012}, } @inproceedings{3281, abstract = {We consider the problem of amplifying the "lossiness" of functions. We say that an oracle circuit C*: {0,1} m → {0,1}* amplifies relative lossiness from ℓ/n to L/m if for every function f:{0,1} n → {0,1} n it holds that 1 If f is injective then so is C f. 2 If f has image size of at most 2 n-ℓ, then C f has image size at most 2 m-L. The question is whether such C* exists for L/m ≫ ℓ/n. This problem arises naturally in the context of cryptographic "lossy functions," where the relative lossiness is the key parameter. We show that for every circuit C* that makes at most t queries to f, the relative lossiness of C f is at most L/m ≤ ℓ/n + O(log t)/n. In particular, no black-box method making a polynomial t = poly(n) number of queries can amplify relative lossiness by more than an O(logn)/n additive term. We show that this is tight by giving a simple construction (cascading with some randomization) that achieves such amplification.}, author = {Pietrzak, Krzysztof Z and Rosen, Alon and Segev, Gil}, location = {Taormina, Sicily, Italy}, pages = {458 -- 475}, publisher = {Springer}, title = {{Lossy functions do not amplify well}}, doi = {10.1007/978-3-642-28914-9_26}, volume = {7194}, year = {2012}, } @inproceedings{3282, abstract = {Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma ) alone does not imply security if the adversary can additionally make verification queries (uf-cmva ). We give an efficient generic transformation from any uf-cma secure MAC which is "message-hiding" into a uf-cmva secure MAC. This resolves the main open problem of Kiltz et al. from Eurocrypt'11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF. © 2012 International Association for Cryptologic Research.}, author = {Dodis, Yevgeniy and Pietrzak, Krzysztof Z and Kiltz, Eike and Wichs, Daniel}, location = {Cambridge, UK}, pages = {355 -- 374}, publisher = {Springer}, title = {{Message authentication, revisited}}, doi = {10.1007/978-3-642-29011-4_22}, volume = {7237}, year = {2012}, } @article{3289, abstract = {Viral manipulation of transduction pathways associated with key cellular functions such as survival, response to microbial infection, and cytoskeleton reorganization can provide the supportive milieu for a productive infection. Here, we demonstrate that vaccinia virus (VACV) infection leads to activation of the stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK) 4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the stimulation of this pathway requires postpenetration, prereplicative events in the viral replication cycle. Although the formation of intracellular mature virus (IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an accentuated deregulation of microtubule and actin network organization in infected JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery and enhanced enveloped particle release. Furthermore, VACV infection induced alterations in the cell contractility and morphology, and cell migration was reduced in the JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell contractility and cell migration, such as microtubule-associated protein 1B and paxillin, respectively, was not detected in the VACV-infected KO cells. In sum, our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in cytoskeleton reorganization during VACV infection. }, author = {Pereira, Anna and Leite, Flávia and Brasil, Bruno and Soares Martins, Jamaria and Torres, Alice and Pimenta, Paulo and Souto Padrón, Thais and Tranktman, Paula and Ferreira, Paulo and Kroon, Erna and Bonjardim, Cláudio}, journal = {Journal of Virology}, number = {1}, pages = {172 -- 184}, publisher = {ASM}, title = {{A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization}}, doi = {10.1128/JVI.05638-11}, volume = {86}, year = {2012}, } @article{3310, abstract = {The theory of persistent homology opens up the possibility to reason about topological features of a space or a function quantitatively and in combinatorial terms. We refer to this new angle at a classical subject within algebraic topology as a point calculus, which we present for the family of interlevel sets of a real-valued function. Our account of the subject is expository, devoid of proofs, and written for non-experts in algebraic topology.}, author = {Bendich, Paul and Cabello, Sergio and Edelsbrunner, Herbert}, journal = {Pattern Recognition Letters}, number = {11}, pages = {1436 -- 1444}, publisher = {Elsevier}, title = {{A point calculus for interlevel set homology}}, doi = {10.1016/j.patrec.2011.10.007}, volume = {33}, year = {2012}, } @article{3314, abstract = {We introduce two-level discounted and mean-payoff games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted or mean-payoff game and the lower level game is a (undiscounted) reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. For both discounted and mean-payoff two-level games, we show the existence of pure memoryless optimal strategies for both players and an ordered field property. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP. We also give an alternate strategy improvement algorithm to compute the value. © 2012 World Scientific Publishing Company.}, author = {Chatterjee, Krishnendu and Majumdar, Ritankar}, journal = {International Journal of Foundations of Computer Science}, number = {3}, pages = {609 -- 625}, publisher = {World Scientific Publishing}, title = {{Discounting and averaging in games across time scales}}, doi = {10.1142/S0129054112400308}, volume = {23}, year = {2012}, } @article{3317, abstract = {The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant of the signalling properties of synapses in the nervous system. Recent functional analysis indicates that in some fast central synapses, transmitter release is triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors at the nanometre scale. Molecular analysis suggests that this tight coupling is generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors and various other synaptic proteins. Nanodomain coupling has several functional advantages, as it increases the efficacy, speed and energy efficiency of synaptic transmission.}, author = {Eggermann, Emmanuel and Bucurenciu, Iancu and Goswami, Sarit and Jonas, Peter M}, journal = {Nature Reviews Neuroscience}, number = {1}, pages = {7 -- 21}, publisher = {Nature Publishing Group}, title = {{Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses}}, doi = {10.1038/nrn3125}, volume = {13}, year = {2012}, } @inproceedings{3341, abstract = {We consider two-player stochastic games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with \omega-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity gameswith respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition function is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).}, author = {Chatterjee, Krishnendu}, location = {Tallinn, Estonia}, pages = {270 -- 285}, publisher = {Springer}, title = {{Robustness of structurally equivalent concurrent parity games}}, doi = {10.1007/978-3-642-28729-9_18}, volume = {7213}, year = {2012}, } @article{3836, abstract = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.}, author = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto}, journal = {Science of Computer Programming}, number = {2}, pages = {96 -- 112}, publisher = {Elsevier}, title = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}}, doi = {10.1016/j.scico.2010.06.004}, volume = {77}, year = {2012}, } @article{3846, abstract = {We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A}, journal = {Journal of Computer and System Sciences}, number = {2}, pages = {394 -- 413}, publisher = {Elsevier}, title = {{A survey of stochastic ω regular games}}, doi = {10.1016/j.jcss.2011.05.002}, volume = {78}, year = {2012}, } @article{2318, abstract = {We show that bosons interacting via pair potentials with negative scattering length form bound states for a suitable number of particles. In other words, the absence of many-particle bound states of any kind implies the non-negativity of the scattering length of the interaction potential. }, author = {Seiringer, Robert}, journal = {Journal of Spectral Theory}, number = {3}, pages = {321--328}, publisher = {EMS Press}, title = {{Absence of bound states implies non-negativity of the scattering length}}, doi = {10.4171/JST/31}, volume = {2}, year = {2012}, } @article{2954, abstract = {Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.}, author = {Pernia-Andrade, Alejandro and Goswami, Sarit and Stickler, Yvonne and Fröbe, Ulrich and Schlögl, Alois and Jonas, Peter M}, journal = {Biophysical Journal}, number = {7}, pages = {1429 -- 1439}, publisher = {Biophysical Society}, title = {{A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo}}, doi = {10.1016/j.bpj.2012.08.039}, volume = {103}, year = {2012}, } @article{3160, abstract = {There is a long-running controversy about how early cell fate decisions are made in the developing mammalian embryo. 1,2 In particular, it is controversial when the first events that can predict the establishment of the pluripotent and extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur. It has long been proposed that the position and polarity of cells at the 16- to 32-cell stage embryo influence their decision to either give rise to the pluripotent cell lineage that eventually contributes to the inner cell mass (ICM), comprising the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm (TE) surrounding the blastocoel. The positioning of cells in the embryo at this developmental stage could largely be the result of random events, making this a stochastic model of cell lineage allocation. Contrary to such a stochastic model, some studies have detected putative differences in the lineage potential of individual blastomeres before compaction, indicating that the first cell fate decisions may occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a key transcription factor (TF) controlling pre-implantation development in the mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications of such molecular heterogeneities in early development and offer potential avenues toward a mechanistic understanding of these observations, contributing to the resolution of the controversy of developmental cell lineage allocation.}, author = {Pantazis, Periklis and Bollenbach, Tobias}, journal = {Cell Cycle}, number = {11}, pages = {2055 -- 2058}, publisher = {Taylor & Francis}, title = {{Transcription factor kinetics and the emerging asymmetry in the early mammalian embryo}}, doi = {10.4161/cc.20118}, volume = {11}, year = {2012}, } @inproceedings{2048, abstract = {Leakage resilient cryptography attempts to incorporate side-channel leakage into the black-box security model and designs cryptographic schemes that are provably secure within it. Informally, a scheme is leakage-resilient if it remains secure even if an adversary learns a bounded amount of arbitrary information about the schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily complicated in order to achieve strong provable security guarantees. As advocated by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in practice much simpler construction may already suffice to protect against realistic side-channel attacks. In this paper, we show that indeed for simpler constructions leakage-resilience can be obtained when we aim for relaxed security notions where the leakage-functions and/or the inputs to the primitive are chosen non-adaptively. For example, we show that a three round Feistel network instantiated with a leakage resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively (This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.) We also show that a minor variation of the classical GGM construction gives a leakage resilient PRF if both, the leakage-function and the inputs, are chosen non-adaptively.}, author = {Faust, Sebastian and Pietrzak, Krzysztof Z and Schipper, Joachim}, booktitle = {Conference proceedings CHES 2012}, location = {Leuven, Belgium}, pages = {213 -- 232}, publisher = {Springer}, title = {{Practical leakage-resilient symmetric cryptography}}, doi = {10.1007/978-3-642-33027-8_13}, volume = {7428}, year = {2012}, }