@inproceedings{3201, abstract = {The problem of cosegmentation consists of segmenting the same object (or objects of the same class) in two or more distinct images. Recently a number of different models have been proposed for this problem. However, no comparison of such models and corresponding optimization techniques has been done so far. We analyze three existing models: the L1 norm model of Rother et al. [1], the L2 norm model of Mukherjee et al. [2] and the "reward" model of Hochbaum and Singh [3]. We also study a new model, which is a straightforward extension of the Boykov-Jolly model for single image segmentation [4]. In terms of optimization, we use a Dual Decomposition (DD) technique in addition to optimization methods in [1,2]. Experiments show a significant improvement of DD over published methods. Our main conclusion, however, is that the new model is the best overall because it: (i) has fewest parameters; (ii) is most robust in practice, and (iii) can be optimized well with an efficient EM-style procedure.}, author = {Vicente, Sara and Vladimir Kolmogorov and Rother, Carsten}, pages = {465 -- 479}, publisher = {Springer}, title = {{Cosegmentation revisited: Models and optimization}}, doi = {10.1007/978-3-642-15552-9_34}, volume = {6312}, year = {2010}, } @article{3202, abstract = {We consider the following problem: given an undirected weighted graph G = (V,E,c) with nonnegative weights, minimize function c(δ(Π))- λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V| 2) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.}, author = {Vladimir Kolmogorov}, journal = {Algorithmica}, number = {4}, pages = {394 -- 412}, publisher = {Springer}, title = {{A faster algorithm for computing the principal sequence of partitions of a graph}}, doi = {10.1007/s00453-008-9177-z}, volume = {56}, year = {2010}, } @inproceedings{3233, abstract = {We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.}, author = {Håstad, Johan and Pass, Rafael and Wikström, Douglas and Krzysztof Pietrzak}, pages = {1 -- 18}, publisher = {Springer}, title = {{An efficient parallel repetition theorem}}, doi = {10.1007/978-3-642-11799-2_1}, volume = {5978}, year = {2010}, } @inproceedings{3234, abstract = {The strongest standard security notion for digital signature schemes is unforgeability under chosen message attacks. In practice, however, this notion can be insufficient due to "side-channel attacks" which exploit leakage of information about the secret internal state. In this work we put forward the notion of "leakage-resilient signatures," which strengthens the standard security notion by giving the adversary the additional power to learn a bounded amount of arbitrary information about the secret state that was accessed during every signature generation. This notion naturally implies security against all side-channel attacks as long as the amount of information leaked on each invocation is bounded and "only computation leaks information." The main result of this paper is a construction which gives a (tree-based, stateful) leakage-resilient signature scheme based on any 3-time signature scheme. The amount of information that our scheme can safely leak per signature generation is 1/3 of the information the underlying 3-time signature scheme can leak in total. Signature schemes that remain secure even if a bounded total amount of information is leaked were recently constructed, hence instantiating our construction with these schemes gives the first constructions of provably secure leakage-resilient signature schemes. The above construction assumes that the signing algorithm can sample truly random bits, and thus an implementation would need some special hardware (randomness gates). Simply generating this randomness using a leakage-resilient stream-cipher will in general not work. Our second contribution is a sound general principle to replace uniform random bits in any leakage-resilient construction with pseudorandom ones: run two leakage-resilient stream-ciphers (with independent keys) in parallel and then apply a two-source extractor to their outputs. }, author = {Faust, Sebastian and Kiltz, Eike and Krzysztof Pietrzak and Rothblum, Guy N}, pages = {343 -- 360}, publisher = {Springer}, title = {{Leakage resilient signatures}}, doi = {10.1007/978-3-642-11799-2_21}, volume = {5978}, year = {2010}, } @inproceedings{3235, abstract = {A cryptographic primitive is leakage-resilient, if it remains secure even if an adversary can learn a bounded amount of arbitrary information about the computation with every invocation. As a consequence, the physical implementation of a leakage-resilient primitive is secure against every side-channel as long as the amount of information leaked per invocation is bounded. In this paper we prove positive and negative results about the feasibility of constructing leakage-resilient pseudorandom functions and permutations (i.e. block-ciphers). Our results are three fold: 1. We construct (from any standard PRF) a PRF which satisfies a relaxed notion of leakage-resilience where (1) the leakage function is fixed (and not adaptively chosen with each query.) and (2) the computation is split into several steps which leak individually (a "step" will be the invocation of the underlying PRF.) 2. We prove that a Feistel network with a super-logarithmic number of rounds, each instantiated with a leakage-resilient PRF, is a leakage resilient PRP. This reduction also holds for the non-adaptive notion just discussed, we thus get a block-cipher which is leakage-resilient (against non-adaptive leakage). 3. We propose generic side-channel attacks against Feistel networks. The attacks are generic in the sense that they work for any round functions (e.g. uniformly random functions) and only require some simple leakage from the inputs to the round functions. For example we show how to invert an r round Feistel network over 2n bits making 4•(n+1) r-2 forward queries, if with each query we are also given as leakage the Hamming weight of the inputs to the r round functions. This complements the result from the previous item showing that a super-constant number of rounds is necessary.}, author = {Dodis, Yevgeniy and Krzysztof Pietrzak}, pages = {21 -- 40}, publisher = {Springer}, title = {{Leakage resilient pseudorandom functions and side channel attacks on feistel networks}}, doi = {10.1007/978-3-642-14623-7_2}, volume = {6223}, year = {2010}, } @inproceedings{3237, abstract = {Blinding is a popular and well-known countermeasure to protect public-key cryptosystems against side-channel attacks. The high level idea is to randomize an exponentiation in order to prevent multiple measurements of the same operation on different data, as such measurements might allow the adversary to learn the secret exponent. Several variants of blinding have been proposed in the literature, using additive or multiplicative secret-sharing to blind either the base or the exponent. These countermeasures usually aim at preventing particular side-channel attacks (mostly power analysis) and come without any formal security guarantee. In this work we investigate to which extend blinding can provide provable security against a general class of side-channel attacks. Surprisingly, it turns out that in the context of public-key encryption some blinding techniques are more suited than others. In particular, we consider a multiplicatively blinded version of ElGamal public-key encryption where - we prove that the scheme, instantiated over bilinear groups of prime order p (where p - 1 is not smooth) is leakage resilient in the generic-group model. Here we consider the model of chosen-ciphertext security in the presence of continuous leakage, i.e., the scheme remains chosen-ciphertext secure even if with every decryption query the adversary can learn a bounded amount (roughly log(p)/2 bits) of arbitrary, adversarially chosen information about the computation. - we conjecture that the scheme, instantiated over arbitrary groups of prime order p (where p - 1 is not smooth) is leakage resilient. Previous to this work no encryption scheme secure against continuous leakage was known. Constructing a scheme that can be proven secure in the standard model remains an interesting open problem. }, author = {Kiltz, Eike and Krzysztof Pietrzak}, pages = {595 -- 612}, publisher = {Springer}, title = {{Leakage resilient ElGamal encryption}}, doi = {10.1007/978-3-642-17373-8_34}, volume = {6477}, year = {2010}, } @article{3294, abstract = {Olfactory responses of Drosophila undergo pronounced changes after eclosion. The flies develop attraction to odors to which they are exposed and aversion to other odors. Behavioral adaptation is correlated with changes in the firing pattern of olfactory receptor neurons (ORNs). In this article, we present an information-theoretic analysis of the firing pattern of ORNs. Flies reared in a synthetic odorless medium were transferred after eclosion to three different media: (i) a synthetic medium relatively devoid of odor cues, (ii) synthetic medium infused with a single odorant, and (iii) complex cornmeal medium rich in odors. Recordings were made from an identified sensillum (type II), and the Jensen-Shannon divergence (D(JS)) was used to assess quantitatively the differences between ensemble spike responses to different odors. Analysis shows that prolonged exposure to ethyl acetate and several related esters increases sensitivity to these esters but does not improve the ability of the fly to distinguish between them. Flies exposed to cornmeal display varied sensitivity to these odorants and at the same time develop greater capacity to distinguish between odors. Deprivation of odor experience on an odorless synthetic medium leads to a loss of both sensitivity and acuity. Rich olfactory experience thus helps to shape the ORNs response and enhances its discriminative power. The experiments presented here demonstrate an experience-dependent adaptation at the level of the receptor neuron.}, author = {Iyengar, Atulya and Chakraborty Tuhin, Subhra and Sarit Goswami and Wu, Chun Fang and Siddiqi, Obaid}, journal = {PNAS}, number = {21}, pages = {9855 -- 60}, publisher = {National Academy of Sciences}, title = {{Post eclosion odor experience modifies olfactory receptor neuron coding in Drosophila}}, doi = {10.1073/pnas.1003856107}, volume = {107}, year = {2010}, } @phdthesis{3296, abstract = {Accurate computational representations of highly deformable surfaces are indispensable in the fields of computer animation, medical simulation, computer vision, digital modeling, and computational physics. The focus of this dissertation is on the animation of physics-based phenomena with highly detailed deformable surfaces represented by triangle meshes. We first present results from an algorithm that generates continuum mechanics animations with intricate surface features. This method combines a finite element method with a tetrahedral mesh generator and a high resolution surface mesh, and it is orders of magnitude more efficient than previous approaches. Next, we present an efficient solution for the challenging problem of computing topological changes in detailed dynamic surface meshes. We then introduce a new physics-inspired surface tracking algorithm that is capable of preserving arbitrarily thin features and reproducing realistic fine-scale topological changes like Rayleigh-Plateau instabilities. This physics-inspired surface tracking technique also opens the door for a unique coupling between surficial finite element methods and volumetric finite difference methods, in order to simulate liquid surface tension phenomena more efficiently than any previous method. Due to its dramatic increase in computational resolution and efficiency, this method yielded the first computer simulations of a fully developed crown splash with droplet pinch off.}, author = {Wojtan, Christopher J}, pages = {1 -- 175}, publisher = {Georgia Institute of Technology}, title = {{Animating physical phenomena with embedded surface meshes}}, year = {2010}, } @article{3303, abstract = {Biological traits result in part from interactions between different genetic loci. This can lead to sign epistasis, in which a beneficial adaptation involves a combination of individually deleterious or neutral mutations; in this case, a population must cross a “fitness valley” to adapt. Recombination can assist this process by combining mutations from different individuals or retard it by breaking up the adaptive combination. Here, we analyze the simplest fitness valley, in which an adaptation requires one mutation at each of two loci to provide a fitness benefit. We present a theoretical analysis of the effect of recombination on the valley-crossing process across the full spectrum of possible parameter regimes. We find that low recombination rates can speed up valley crossing relative to the asexual case, while higher recombination rates slow down valley crossing, with the transition between the two regimes occurring when the recombination rate between the loci is approximately equal to the selective advantage provided by the adaptation. In large populations, if the recombination rate is high and selection against single mutants is substantial, the time to cross the valley grows exponentially with population size, effectively meaning that the population cannot acquire the adaptation. Recombination at the optimal (low) rate can reduce the valley-crossing time by up to several orders of magnitude relative to that in an asexual population. }, author = {Weissman, Daniel and Feldman, Marcus and Fisher, Daniel}, journal = {Genetics}, number = {4}, pages = {1389 -- 1410}, publisher = {Genetics Society of America}, title = {{The rate of fitness-valley crossing in sexual populations}}, doi = {10.1534/genetics.110.123240}, volume = {186}, year = {2010}, } @article{3306, abstract = {We use methods from combinatorics and algebraic statistics to study analogues of birth-and-death processes that have as their state space a finite subset of the m-dimensional lattice and for which the m matrices that record the transition probabilities in each of the lattice directions commute pairwise. One reason such processes are of interest is that the transition matrix is straightforward to diagonalize, and hence it is easy to compute n step transition probabilities. The set of commuting birth-and-death processes decomposes as a union of toric varieties, with the main component being the closure of all processes whose nearest neighbor transition probabilities are positive. We exhibit an explicit monomial parametrization for this main component, and we explore the boundary components using primary decomposition.}, author = {Evans, Steven N and Sturmfels, Bernd and Caroline Uhler}, journal = {The Annals of Applied Probability}, pages = {238 -- 266}, publisher = {Institute of Mathematical Statistics}, title = {{Commuting birth and death processes}}, doi = {10.1214/09-AAP615}, volume = {20}, year = {2010}, } @article{3308, abstract = {We study multivariate normal models that are described by linear constraints on the inverse of the covariance matrix. Maximum likelihood estimation for such models leads to the problem of maximizing the determinant function over a spectrahedron, and to the problem of characterizing the image of the positive definite cone under an arbitrary linear projection. These problems at the interface of statistics and optimization are here examined from the perspective of convex algebraic geometry.}, author = {Sturmfels, Bernd and Caroline Uhler}, journal = {Annals of the Institute of Statistical Mathematics}, number = {4}, pages = {603 -- 638}, publisher = {Springer}, title = {{Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry}}, doi = {10.1007/s10463-010-0295-4}, volume = {62}, year = {2010}, } @article{3402, abstract = {Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, the model checking problem can be reduced to a finite-state problem, and we illustrate the use of the method by proving the correctness of several TMs, including two-phase locking, DSTM, and TL2. The safety properties we consider include strict serializability and opacity; the liveness properties include obstruction freedom, livelock freedom, and wait freedom. Our main contribution lies in the structure of the proofs, which are largely automated and not restricted to the TMs mentioned above. In a first step we show that every TM that enjoys certain structural properties either violates a requirement on some program with two threads and two shared variables, or satisfies the requirement on all programs. In the second step, we use a model checker to prove the requirement for the TM applied to a most general program with two threads and two variables. In the safety case, the model checker checks language inclusion between two finite-state transition systems, a nondeterministic transition system representing the given TM applied to a most general program, and a deterministic transition system representing a most liberal safe TM applied to the same program. The given TM transition system is nondeterministic because a TM can be used with different contention managers, which resolve conflicts differently. In the liveness case, the model checker analyzes fairness conditions on the given TM transition system.}, author = {Guerraoui, Rachid and Thomas Henzinger and Vasu Singh}, journal = {Distributed Computing}, number = {3}, pages = {129 -- 145}, publisher = {Springer}, title = {{Model checking transactional memories}}, doi = {10.1007/s00446-009-0092-6}, volume = {22}, year = {2010}, } @misc{3403, abstract = {Rate remapping is a conjunctive code that potentially enables hippocampal place cells to jointly represent spatial and nonspatial information. In this issue of Neuron, Rennó-Costa et al. introduce a theoretical model wherein the convergence of the medial and lateral entorhinal excitatory inputs, combined with local inhibition, explains hippocampal rate remapping. © 2010 Elsevier Inc.}, author = {Pleydell-Bouverie, Barty and Jozsef Csicsvari}, booktitle = {Neuron}, number = {6}, pages = {1015 -- 1016}, publisher = {Elsevier}, title = {{Rate remapping: When the code goes beyond space (preview)}}, doi = {10.1016/j.neuron.2010.12.011}, volume = {68}, year = {2010}, } @misc{3406, abstract = {The impact of structural biology on the design of ligands (agonists, antagonists and modulators) for ionotropic glutamate receptors is reviewed.}, author = {Stawski, Philipp and Harald Janovjak and Trauner, Dirk}, booktitle = {Bioorganic and Medicinal Chemistry}, number = {22}, pages = {7759 -- 7772}, publisher = {Elsevier}, title = {{Pharmacology of ionotropic glutamate receptors: a structural perspective}}, doi = {10.1016/j.bmc.2010.09.012}, volume = {18}, year = {2010}, } @article{3407, abstract = {Genetically targeted light-activated ion channels and pumps make it possible to determine the role of specific neurons in neuronal circuits, information processing and behavior. We developed a K+-selective ionotropic glutamate receptor that reversibly inhibits neuronal activity in response to light in dissociated neurons and brain slice and also reversibly suppresses behavior in zebrafish. The receptor is a chimera of the pore region of a K+-selective bacterial glutamate receptor and the ligand-binding domain of a light-gated mammalian kainate receptor. This hyperpolarizing light-gated channel, HyLighter, is turned on by a brief light pulse at one wavelength and turned off by a pulse at a second wavelength. The control is obtained at moderate intensity. After optical activation, the photocurrent and optical silencing of activity persists in the dark for extended periods. The low light requirement and bi-stability of HyLighter represent advantages for the dissection of neural circuitry.}, author = {Harald Janovjak and Szobota, Stephanie and Wyart, Claire and Trauner, Dirk and Isacoff, Ehud Y}, journal = {Nature Neuroscience}, pages = {1027 -- 1032}, publisher = {Nature Publishing Group}, title = {{A light-gated, potassium-selective glutamate receptor for the optical inhibition of neuronal firing}}, doi = {10.1038/nn.2589}, volume = {13}, year = {2010}, } @article{13409, abstract = {The immobilization of molecular switches onto inorganic supports has recently become a hot topic as it can give rise to novel hybrid materials in which the properties of the two components are mutually enhanced. Even more attractive is the concept of “transferring” the switchable characteristics of single layers of organic molecules onto the underlying inorganic components, rendering them responsive to external stimuli as well. Of the various molecular switches studied, azobenzene (AB) has arguably attracted most attention due to its simple molecular structure, and because its “trigger” (light) is a noninvasive one, it can be delivered instantaneously, and into a precise location. In order to fully realize its potential, however, it is necessary to immobilize AB onto solid supports. It is the goal of this manuscript to comprehensively yet concisely review such hybrid systems which comprise AB forming well-defined self-assembled monolayers (SAMs) on planar and curved (colloidal and nanoporous) inorganic surfaces. I discuss methods to immobilize AB derivatives onto surfaces, strategies to ensure efficient AB isomerization, ways to monitor the switching process, properties of these switchable hybrid materials, and, last but not least, their emerging applications.}, author = {Klajn, Rafal}, issn = {1365-3075}, journal = {Pure and Applied Chemistry}, keywords = {General Chemical Engineering, General Chemistry}, number = {12}, pages = {2247--2279}, publisher = {De Gruyter}, title = {{Immobilized azobenzenes for the construction of photoresponsive materials}}, doi = {10.1351/pac-con-10-09-04}, volume = {82}, year = {2010}, } @article{13410, abstract = {A range (Au, Pt, Pd) of metal nanoparticles (MNPs) has been prepared and functionalized with (a) redox-active stalks containing tetrathiafulvalene (TTF) units, (b) [2]pseudorotaxanes formed between these stalks and cyclobis(paraquat-p-phenylene) (CBPQT4+) rings, and (c) bistable [2]rotaxane molecules where the dumbbell component contains a 1,5-dioxynaphthalene (DNP) unit, as well as a TTF unit, encircled by a CBPQT4+ ring. It transpires that the molecules present in (a) and (c) and the supermolecules described in (b) retain their switching characteristics, previously observed in solution, when they are immobilized onto MNPs. Moreover, their oxidation potentials depend on the fraction, χ, of the molecules or supermolecules on the surface of the nanoparticles. A variation in χ affects the oxidation potentials of the TTF units to the extent that switching can be subjected to fine tuning as a result. Specifically, increasing χ results in positive shifts (i) in the oxidation potentials of the TTF unit in (a)−(c) and (ii) the reduction potentials of the CBPQT4+ rings in (c). These shifts can be attributed to an increase in the electrostatic potential surrounding the MNPs. Both the magnitude and the direction of these shifts are reproduced by a model, based on the Poisson−Boltzmann equation coupled with charge-regulating boundary conditions. Furthermore, the kinetics of relaxation from the metastable state coconformation (MSCC) to the ground-state coconformation (GSCC) of the bistable [2]rotaxane molecules also depends on χ, as well as on the nanoparticle diameter. Increasing either of these parameters accelerates the rate of relaxation from the MSCC to the GSCC. This rate is a function of (i) the activation energy for the relaxation process associated with the bistable [2]rotaxane molecules in solution and (ii) the electrostatic potential surrounding the MNPs. The electrostatic potential depends on (i) the diameter of the MNPs, (ii) the amount of the bistable [2]rotaxane molecules on the surface of the MNPs, and (iii) the equilibrium distribution of the CBPQT4+ rings between the DNP and TTF recognition sites in the GSCC. This electrostatic potential has also been quantified using the Poisson−Boltzmann equation, leading to faithful estimates of the rate constants.}, author = {Coskun, Ali and Wesson, Paul J. and Klajn, Rafal and Trabolsi, Ali and Fang, Lei and Olson, Mark A. and Dey, Sanjeev K. and Grzybowski, Bartosz A. and Stoddart, J. Fraser}, issn = {1520-5126}, journal = {Journal of the American Chemical Society}, keywords = {Colloid and Surface Chemistry, Biochemistry, General Chemistry, Catalysis}, number = {12}, pages = {4310--4320}, publisher = {American Chemical Society}, title = {{Molecular-mechanical switching at the nanoparticle−solvent interface: Practice and theory}}, doi = {10.1021/ja9102327}, volume = {132}, year = {2010}, } @article{13411, abstract = {Photoresponsive gold nanoparticles dispersed in a solid/frozen matrix provide a basis for sensors that “remember” whether the sample has ever exceeded the melting temperature of the matrix. The operation of these sensors rests on the ability to photoinduce metastable electric dipoles on NP surfaces – upon melting, these dipoles drive NP aggregation, precipitation, and crosslinking. These events are manifested by a pronounced color change.}, author = {Klajn, Rafal and Browne, Kevin P. and Soh, Siowling and Grzybowski, Bartosz A.}, issn = {1613-6829}, journal = {Small}, keywords = {Biomaterials, Biotechnology, General Materials Science, General Chemistry}, number = {13}, pages = {1385--1387}, publisher = {Wiley}, title = {{Nanoparticles that “remember” temperature}}, doi = {10.1002/smll.200902272}, volume = {6}, year = {2010}, } @article{13412, abstract = {Nanoparticles (NPs) and molecular/supramolecular switches have attracted considerable interest during the past decade on account of their unique properties and prominent roles in the fields of organic chemistry and materials science. Materials derived from the combination of these two components are now emerging in the literature. This critical review evaluates materials which comprise NPs functionalised with well-defined self-assembled monolayers of molecular and supramolecular switches. We draw attention to the fact that immobilisation of switches on NPs does not, in general, hamper their switching ability, although it can impart new properties on the supporting particles. This premise leads us to the discussion of systems in which switching on the surfaces of NPs can be used to modulate reversibly a range of NP properties—optical, fluorescent, electrical, magnetic—as well as the controlled release of small molecules. Finally, we discuss examples in which molecular switches direct reversible self-assembly of NPs (308 references).}, author = {Klajn, Rafal and Stoddart, J. Fraser and Grzybowski, Bartosz A.}, issn = {1460-4744}, journal = {Chemical Society Reviews}, keywords = {General Chemistry}, number = {6}, pages = {2203--2237}, publisher = {Royal Society of Chemistry}, title = {{Nanoparticles functionalised with reversible molecular and supramolecular switches}}, doi = {10.1039/b920377j}, volume = {39}, year = {2010}, } @article{1465, abstract = {We prove a generating function formula for the Betti numbers of Nakajima quiver varieties. We prove that it is a q-deformation of the Weyl-Kac character formula. In particular this implies that the constant term of the polynomial counting the number of absolutely indecomposable representations of a quiver equals the multiplicity of a certain weight in the corresponding Kac-Moody algebra, which was conjectured by Kac in 1982.}, author = {Tamas Hausel}, journal = {Inventiones Mathematicae}, number = {1}, pages = {21 -- 37}, publisher = {Springer}, title = {{Kac's conjecture from Nakajima quiver varieties}}, doi = {10.1007/s00222-010-0241-3}, volume = {181}, year = {2010}, }