TY - GEN
AU - Huszár, Kristóf
AU - Rolinek, Michal
ID - 7038
TI - Playful Math - An introduction to mathematical games
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 -
TY - CONF
AB - In this paper we present INTERHORN, a solver for recursion-free Horn clauses. The main application domain of INTERHORN lies in solving interpolation problems arising in software verification. We show how a range of interpolation problems, including path, transition, nested, state/transition and well-founded interpolation can be handled directly by INTERHORN. By detailing these interpolation problems and their Horn clause representations, we hope to encourage the emergence of a common back-end interpolation interface useful for diverse verification tools.
AU - Gupta, Ashutosh
AU - Popeea, Corneliu
AU - Rybalchenko, Andrey
ID - 1702
T2 - Electronic Proceedings in Theoretical Computer Science, EPTCS
TI - Generalised interpolation by solving recursion free-horn clauses
VL - 169
ER -
TY - CONF
AB - It has been long argued that, because of inherent ambiguity and noise, the brain needs to represent uncertainty in the form of probability distributions. The neural encoding of such distributions remains however highly controversial. Here we present a novel circuit model for representing multidimensional real-valued distributions using a spike based spatio-temporal code. Our model combines the computational advantages of the currently competing models for probabilistic codes and exhibits realistic neural responses along a variety of classic measures. Furthermore, the model highlights the challenges associated with interpreting neural activity in relation to behavioral uncertainty and points to alternative population-level approaches for the experimental validation of distributed representations.
AU - Savin, Cristina
AU - Denève, Sophie
ID - 1708
IS - January
TI - Spatio-temporal representations of uncertainty in spiking neural networks
VL - 3
ER -
TY - JOUR
AB - The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces, and how to synthesize an interface from incompatible requirements. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.
AU - Cerny, Pavol
AU - Chmelik, Martin
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
ID - 1733
IS - 3
JF - Theoretical Computer Science
TI - Interface simulation distances
VL - 560
ER -
TY - CHAP
AB - The generation of asymmetry, at both cellular and tissue level, is one of the most essential capabilities of all eukaryotic organisms. It mediates basically all multicellular development ranging from embryogenesis and de novo organ formation till responses to various environmental stimuli. In plants, the awe-inspiring number of such processes is regulated by phytohormone auxin and its directional, cell-to-cell transport. The mediators of this transport, PIN auxin transporters, are asymmetrically localized at the plasma membrane, and this polar localization determines the directionality of intercellular auxin flow. Thus, auxin transport contributes crucially to the generation of local auxin gradients or maxima, which instruct given cell to change its developmental program. Here, we introduce and discuss the molecular components and cellular mechanisms regulating the generation and maintenance of cellular PIN polarity, as the general hallmarks of cell polarity in plants.
AU - Baster, Pawel
AU - Friml, Jiří
ED - Zažímalová, Eva
ED - Petrášek, Jan
ED - Benková, Eva
ID - 1806
T2 - Auxin and Its Role in Plant Development
TI - Auxin on the road navigated by cellular PIN polarity
ER -
TY - JOUR
AB - Watermarking techniques for vector graphics dislocate vertices in order to embed imperceptible, yet detectable, statistical features into the input data. The embedding process may result in a change of the topology of the input data, e.g., by introducing self-intersections, which is undesirable or even disastrous for many applications. In this paper we present a watermarking framework for two-dimensional vector graphics that employs conventional watermarking techniques but still provides the guarantee that the topology of the input data is preserved. The geometric part of this framework computes so-called maximum perturbation regions (MPR) of vertices. We propose two efficient algorithms to compute MPRs based on Voronoi diagrams and constrained triangulations. Furthermore, we present two algorithms to conditionally correct the watermarked data in order to increase the watermark embedding capacity and still guarantee topological correctness. While we focus on the watermarking of input formed by straight-line segments, one of our approaches can also be extended to circular arcs. We conclude the paper by demonstrating and analyzing the applicability of our framework in conjunction with two well-known watermarking techniques.
AU - Huber, Stefan
AU - Held, Martin
AU - Meerwald, Peter
AU - Kwitt, Roland
ID - 1816
IS - 1
JF - International Journal of Computational Geometry and Applications
TI - Topology-preserving watermarking of vector graphics
VL - 24
ER -
TY - JOUR
AB - We review recent progress towards a rigorous understanding of the Bogoliubov approximation for bosonic quantum many-body systems. We focus, in particular, on the excitation spectrum of a Bose gas in the mean-field (Hartree) limit. A list of open problems will be discussed at the end.
AU - Seiringer, Robert
ID - 1821
IS - 7
JF - Journal of Mathematical Physics
TI - Bose gases, Bose-Einstein condensation, and the Bogoliubov approximation
VL - 55
ER -
TY - JOUR
AU - Jakšić, Vojkan
AU - Pillet, Claude
AU - Seiringer, Robert
ID - 1822
IS - 7
JF - Journal of Mathematical Physics
TI - Introduction
VL - 55
ER -
TY - CHAP
AB - Hitting and batting tasks, such as tennis forehands, ping-pong strokes, or baseball batting, depend on predictions where the ball can be intercepted and how it can properly be returned to the opponent. These predictions get more accurate over time, hence the behaviors need to be continuously modified. As a result, movement templates with a learned global shape need to be adapted during the execution so that the racket reaches a target position and velocity that will return the ball over to the other side of the net or court. It requires altering learned movements to hit a varying target with the necessary velocity at a specific instant in time. Such a task cannot be incorporated straightforwardly in most movement representations suitable for learning. For example, the standard formulation of the dynamical system based motor primitives (introduced by Ijspeert et al (2002b)) does not satisfy this property despite their flexibility which has allowed learning tasks ranging from locomotion to kendama. In order to fulfill this requirement, we reformulate the Ijspeert framework to incorporate the possibility of specifying a desired hitting point and a desired hitting velocity while maintaining all advantages of the original formulation.We show that the proposed movement template formulation works well in two scenarios, i.e., for hitting a ball on a string with a table tennis racket at a specified velocity and for returning balls launched by a ball gun successfully over the net using forehand movements.
AU - Muelling, Katharina
AU - Kroemer, Oliver
AU - Lampert, Christoph
AU - Schölkopf, Bernhard
ED - Kober, Jens
ED - Peters, Jan
ID - 1829
T2 - Learning Motor Skills
TI - Movement templates for learning of hitting and batting
VL - 97
ER -
TY - JOUR
AB - We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.
AU - Cibulka, Josef
AU - Gao, Pu
AU - Krcál, Marek
AU - Valla, Tomáš
AU - Valtr, Pavel
ID - 1842
IS - 1
JF - Discrete & Computational Geometry
TI - On the geometric ramsey number of outerplanar graphs
VL - 53
ER -
TY - JOUR
AB - Local protein interactions ("molecular context" effects) dictate amino acid replacements and can be described in terms of site-specific, energetic preferences for any different amino acid. It has been recently debated whether these preferences remain approximately constant during evolution or whether, due to coevolution of sites, they change strongly. Such research highlights an unresolved and fundamental issue with far-reaching implications for phylogenetic analysis and molecular evolution modeling. Here, we take advantage of the recent availability of phenotypically supported laboratory resurrections of Precambrian thioredoxins and β-lactamases to experimentally address the change of site-specific amino acid preferences over long geological timescales. Extensive mutational analyses support the notion that evolutionary adjustment to a new amino acid may occur, but to a large extent this is insufficient to erase the primitive preference for amino acid replacements. Generally, site-specific amino acid preferences appear to remain conserved throughout evolutionary history despite local sequence divergence. We show such preference conservation to be readily understandable in molecular terms and we provide crystallographic evidence for an intriguing structural-switch mechanism: Energetic preference for an ancestral amino acid in a modern protein can be linked to reorganization upon mutation to the ancestral local structure around the mutated site. Finally, we point out that site-specific preference conservation naturally leads to one plausible evolutionary explanation for the existence of intragenic global suppressor mutations.
AU - Risso, Valeria
AU - Manssour Triedo, Fadia
AU - Delgado Delgado, Asuncion
AU - Arco, Rocio
AU - Barroso Deljesús, Alicia
AU - Inglés Prieto, Álvaro
AU - Godoy Ruiz, Raquel
AU - Gavira, Josè
AU - Gaucher, Eric
AU - Ibarra Molero, Beatriz
AU - Sánchez Ruiz, Jose
ID - 1844
IS - 2
JF - Molecular Biology and Evolution
TI - Mutational studies on resurrected ancestral proteins reveal conservation of site-specific amino acid preferences throughout evolutionary history
VL - 32
ER -
TY - JOUR
AB - To control morphogenesis, molecular regulatory networks have to interfere with the mechanical properties of the individual cells of developing organs and tissues, but how this is achieved is not well known. We study this issue here in the shoot meristem of higher plants, a group of undifferentiated cells where complex changes in growth rates and directions lead to the continuous formation of new organs [1, 2]. Here, we show that the plant hormone auxin plays an important role in this process via a dual, local effect on the extracellular matrix, the cell wall, which determines cell shape. Our study reveals that auxin not only causes a limited reduction in wall stiffness but also directly interferes with wall anisotropy via the regulation of cortical microtubule dynamics. We further show that to induce growth isotropy and organ outgrowth, auxin somehow interferes with the cortical microtubule-ordering activity of a network of proteins, including AUXIN BINDING PROTEIN 1 and KATANIN 1. Numerical simulations further indicate that the induced isotropy is sufficient to amplify the effects of the relatively minor changes in wall stiffness to promote organogenesis and the establishment of new growth axes in a robust manner.
AU - Sassi, Massimiliano
AU - Ali, Olivier
AU - Boudon, Frédéric
AU - Cloarec, Gladys
AU - Abad, Ursula
AU - Cellier, Coralie
AU - Chen, Xu
AU - Gilles, Benjamin
AU - Milani, Pascale
AU - Friml, Jirí
AU - Vernoux, Teva
AU - Godin, Christophe
AU - Hamant, Olivier
AU - Traas, Jan
ID - 1852
IS - 19
JF - Current Biology
TI - An auxin-mediated shift toward growth isotropy promotes organ formation at the shoot meristem in Arabidopsis
VL - 24
ER -
TY - CONF
AB - Wireless sensor networks (WSNs) composed of low-power, low-cost sensor nodes are expected to form the backbone of future intelligent networks for a broad range of civil, industrial and military applications. These sensor nodes are often deployed through random spreading, and function in dynamic environments. Many applications of WSNs such as pollution tracking, forest fire detection, and military surveillance require knowledge of the location of constituent nodes. But the use of technologies such as GPS on all nodes is prohibitive due to power and cost constraints. So, the sensor nodes need to autonomously determine their locations. Most localization techniques use anchor nodes with known locations to determine the position of remaining nodes. Localization techniques have two conflicting requirements. On one hand, an ideal localization technique should be computationally simple and on the other hand, it must be resistant to attacks that compromise anchor nodes. In this paper, we propose a computationally light-weight game theoretic secure localization technique and demonstrate its effectiveness in comparison to existing techniques.
AU - Jha, Susmit
AU - Tripakis, Stavros
AU - Seshia, Sanjit
AU - Chatterjee, Krishnendu
ID - 1853
TI - Game theoretic secure localization in wireless sensor networks
ER -
TY - JOUR
AB - In this paper, we present a method for non-rigid, partial shape matching in vector graphics. Given a user-specified query region in a 2D shape, similar regions are found, even if they are non-linearly distorted. Furthermore, a non-linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two-step approach. First, pointwise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non-rigid transform, enabling non-rigid shape matching. In this paper, we present a method for non-rigid, partial shape matching in vector graphics. Given a user-specified query region in a 2D shape, similar regions are found, even if they are non-linearly distorted. Furthermore, a non-linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two-step approach. First, pointwise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non-rigid transform, enabling non-rigid shape matching.
AU - Guerrero, Paul
AU - Auzinger, Thomas
AU - Wimmer, Michael
AU - Jeschke, Stefan
ID - 1854
IS - 1
JF - Computer Graphics Forum
TI - Partial shape matching using transformation parameter similarity
VL - 34
ER -
TY - JOUR
AB - The prominent and evolutionarily ancient role of the plant hormone auxin is the regulation of cell expansion. Cell expansion requires ordered arrangement of the cytoskeleton but molecular mechanisms underlying its regulation by signalling molecules including auxin are unknown. Here we show in the model plant Arabidopsis thaliana that in elongating cells exogenous application of auxin or redistribution of endogenous auxin induces very rapid microtubule re-orientation from transverse to longitudinal, coherent with the inhibition of cell expansion. This fast auxin effect requires auxin binding protein 1 (ABP1) and involves a contribution of downstream signalling components such as ROP6 GTPase, ROP-interactive protein RIC1 and the microtubule-severing protein katanin. These components are required for rapid auxin-and ABP1-mediated re-orientation of microtubules to regulate cell elongation in roots and dark-grown hypocotyls as well as asymmetric growth during gravitropic responses.
AU - Chen, Xu
AU - Grandont, Laurie
AU - Li, Hongjiang
AU - Hauschild, Robert
AU - Paque, Sébastien
AU - Abuzeineh, Anas
AU - Rakusová, Hana
AU - Benková, Eva
AU - Perrot Rechenmann, Catherine
AU - Friml, Jirí
ID - 1862
IS - 729
JF - Nature
TI - Inhibition of cell expansion by rapid ABP1-mediated auxin effect on microtubules
VL - 516
ER -
TY - CONF
AB - Boolean controllers for systems with complex datapaths are often very difficult to implement correctly, in particular when concurrency is involved. Yet, in many instances it is easy to formally specify correctness. For example, the specification for the controller of a pipelined processor only has to state that the pipelined processor gives the same results as a non-pipelined reference design. This makes such controllers a good target for automated synthesis. However, an efficient abstraction for the complex datapath elements is needed, as a bit-precise description is often infeasible. We present Suraq, the first controller synthesis tool which uses uninterpreted functions for the abstraction. Quantified firstorder formulas (with specific quantifier structure) serve as the specification language from which Suraq synthesizes Boolean controllers. Suraq transforms the specification into an unsatisfiable SMT formula, and uses Craig interpolation to compute its results. Using Suraq, we were able to synthesize a controller (consisting of two Boolean signals) for a five-stage pipelined DLX processor in roughly one hour and 15 minutes.
AU - Hofferek, Georg
AU - Gupta, Ashutosh
ED - Yahav, Eran
ID - 1869
T2 - HVC 2014
TI - Suraq - a controller synthesis tool using uninterpreted functions
VL - 8855
ER -
TY - CONF
AB - We investigate the problem of checking if a finite-state transducer is robust to uncertainty in its input. Our notion of robustness is based on the analytic notion of Lipschitz continuity - a transducer 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. We show that K-robustness is undecidable even for deterministic transducers. We identify a class of functional transducers, which admits a polynomial time automata-theoretic decision procedure for K-robustness. This class includes Mealy machines and functional letter-to-letter transducers. We also study K-robustness of nondeterministic transducers. Since a nondeterministic transducer generates a set of output words for each input word, we quantify output perturbation using setsimilarity functions. We show that K-robustness of nondeterministic transducers is undecidable, even for letter-to-letter transducers. We identify a class of set-similarity functions which admit decidable K-robustness of letter-to-letter transducers.
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Samanta, Roopsha
ID - 1870
T2 - Leibniz International Proceedings in Informatics, LIPIcs
TI - Lipschitz robustness of finite-state transducers
VL - 29
ER -
TY - CONF
AB - Extensionality axioms are common when reasoning about data collections, such as arrays and functions in program analysis, or sets in mathematics. An extensionality axiom asserts that two collections are equal if they consist of the same elements at the same indices. Using extensionality is often required to show that two collections are equal. A typical example is the set theory theorem (∀x)(∀y)x∪y = y ∪x. Interestingly, while humans have no problem with proving such set identities using extensionality, they are very hard for superposition theorem provers because of the calculi they use. In this paper we show how addition of a new inference rule, called extensionality resolution, allows first-order theorem provers to easily solve problems no modern first-order theorem prover can solve. We illustrate this by running the VAMPIRE theorem prover with extensionality resolution on a number of set theory and array problems. Extensionality resolution helps VAMPIRE to solve problems from the TPTP library of first-order problems that were never solved before by any prover.
AU - Gupta, Ashutosh
AU - Kovács, Laura
AU - Kragl, Bernhard
AU - Voronkov, Andrei
ED - Cassez, Franck
ED - Raskin, Jean-François
ID - 1872
T2 - ATVA 2014
TI - Extensional crisis and proving identity
VL - 8837
ER -