@article{17957, abstract = {While the single-molecule conductance properties of π-conjugated and σ-conjugated systems have been well-studied, little is known regarding the conductance properties of mixed σ–π backbone wires and the factors that control their transport properties. Here we utilize a scanning tunneling microscope-based break-junction technique to study a series of molecular wires with π–σ–π backbone structures, where the π-moiety is an electrode-binding thioanisole ring and the σ-moiety is a triatomic α–β–α chain composed of C, Si, or Ge atoms. We find that the sequence and composition of group 14 atoms in the α–β–α chain dictates whether electronic communication between the aryl rings is enhanced or suppressed. Placing heavy atoms at the α-position decreases conductance, whereas placing them at the β-position increases conductance: for example, the C–Ge–C sequence is over 20 times more conductive than the Ge–C–Ge sequence. Density functional theory calculations reveal that these conductance trends arise from periodic trends (i.e., atomic size, polarizability, and electronegativity) that differ from C to Si to Ge. The periodic trends that control molecular conductance here are the same ones that give rise to the α and β silicon effects from physical organic chemistry. These findings outline a new molecular design concept for tuning conductance in single-molecule electrical devices.}, author = {Su, Timothy A. and Li, Haixing and Klausen, Rebekka S. and Widawsky, Jonathan R. and Batra, Arunabh and Steigerwald, Michael L. and Venkataraman, Latha and Nuckolls, Colin}, issn = {1520-5126}, journal = {Journal of the American Chemical Society}, number = {24}, pages = {7791--7795}, publisher = {American Chemical Society}, title = {{Tuning conductance in π–σ–π single-molecule wires}}, doi = {10.1021/jacs.6b04394}, volume = {138}, year = {2016}, } @article{17958, abstract = {Charge transport phenomena in single-molecule junctions are often dominated by tunneling, with a transmission function dictating the probability that electrons or holes tunnel through the junction. Here, we present a new and simple technique for measuring the transmission functions of molecular junctions in the coherent tunneling limit, over an energy range of 1.5 eV around the Fermi energy. We create molecular junctions in an ionic environment with electrodes having different exposed areas, which results in the formation of electric double layers of dissimilar density on the two electrodes. This allows us to electrostatically shift the molecular resonance relative to the junction Fermi levels in a manner that depends on the sign of the applied bias, enabling us to map out the junction’s transmission function and determine the dominant orbital for charge transport in the molecular junction. We demonstrate this technique using two groups of molecules: one group having molecular resonance energies relatively far from EF and one group having molecular resonance energies within the accessible bias window. Our results compare well with previous electrochemical gating data and with transmission functions computed from first principles. Furthermore, with the second group of molecules, we are able to examine the behavior of a molecular junction as a resonance shifts into the bias window. This work provides a new, experimentally simple route for exploring the fundamentals of charge transport at the nanoscale.}, author = {Capozzi, Brian and Low, Jonathan Z. and Xia, Jianlong and Liu, Zhen-Fei and Neaton, Jeffrey B. and Campos, Luis M. and Venkataraman, Latha}, issn = {1530-6992}, journal = {Nano Letters}, number = {6}, pages = {3949--3954}, publisher = {American Chemical Society}, title = {{Mapping the transmission functions of single-molecule junctions}}, doi = {10.1021/acs.nanolett.6b01592}, volume = {16}, year = {2016}, } @article{17959, abstract = {Single-molecule conductance measurements have focused primarily on organic molecular systems. Here, we carry out scanning tunneling microscope-based break-junction measurements on a series of metal chalcogenide Co6Se8 clusters capped with conducting ligands of varying lengths. We compare these measurements with those of individual free ligands and find that the conductance of these clusters and the free ligands have different decay constants with increasing ligand length. We also show, through measurements in two different solvents, 1-bromonaphthalene and 1,2,4-trichlorobenzene, that the conductance decay of the clusters depends on the solvent environment. We discuss several mechanisms to explain our observations.}, author = {Choi, Bonnie and Capozzi, Brian and Ahn, Seokhoon and Turkiewicz, Ari and Lovat, Giacomo and Nuckolls, Colin and Steigerwald, Michael L. and Venkataraman, Latha and Roy, Xavier}, issn = {2041-6539}, journal = {Chemical Science}, number = {4}, pages = {2701--2705}, publisher = {Royal Society of Chemistry}, title = {{Solvent-dependent conductance decay constants in single cluster junctions}}, doi = {10.1039/c5sc02595h}, volume = {7}, year = {2016}, } @article{17960, abstract = {Over the past 10 years, there has been tremendous progress in the measurement, modeling and understanding of structure–function relationships in single molecule junctions. Numerous research groups have addressed significant scientific questions, directed both to conductance phenomena at the single molecule level and to the fundamental chemistry that controls junction functionality. Many different functionalities have been demonstrated, including single-molecule diodes, optically and mechanically activated switches, and, significantly, physical phenomena with no classical analogues, such as those based on quantum interference effects. Experimental techniques for reliable and reproducible single molecule junction formation and characterization have led to this progress. In particular, the scanning tunneling microscope based break-junction (STM-BJ) technique has enabled rapid, sequential measurement of large numbers of nanoscale junctions allowing a statistical analysis to readily distinguish reproducible characteristics. Harnessing fundamental link chemistry has provided the necessary chemical control over junction formation, enabling measurements that revealed clear relationships between molecular structure and conductance characteristics. Such link groups (amines, methylsuflides, pyridines, etc.) maintain a stable lone pair configuration that selectively bonds to specific, undercoordinated transition metal atoms available following rupture of a metal point contact in the STM-BJ experiments. This basic chemical principle rationalizes the observation of highly reproducible conductance signatures. Subsequently, the method has been extended to probe a variety of physical phenomena ranging from basic I–V characteristics to more complex properties such as thermopower and electrochemical response. By adapting the technique to a conducting cantilever atomic force microscope (AFM-BJ), simultaneous measurement of the mechanical characteristics of nanoscale junctions as they are pulled apart has given complementary information such as the stiffness and rupture force of the molecule-metal link bond. Overall, while the BJ technique does not produce a single molecule circuit for practical applications, it has proved remarkably versatile for fundamental studies. Measured data and analysis have been combined with atomic-scale theory and calculations, typically performed for representative junction structures, to provide fundamental physical understanding of structure–function relationships. This Account integrates across an extensive series of our specific nanoscale junction studies which were carried out with the STM- and AFM-BJ techniques and supported by theoretical analysis and density functional theory based calculations, with emphasis on the physical characteristics of the measurement process and the rich data sets that emerge. Several examples illustrate the impact of measured trends based on the most probable values for key characteristics (obtained from ensembles of order 1000–10 000 individual junctions) to build a solid picture of conductance phenomena as well as attributes of the link bond chemistry. The key forward-looking question posed here is the extent to which the full data sets represented by the individual trajectories can be analyzed to address structure–function questions at the level of individual junctions. Initial progress toward physical modeling of conductance of individual junctions indicates trends consistent with physical junction structures. Analysis of junction mechanics reveals a scaling procedure that collapses existing data onto a universal force–extension curve. This research directed to understanding the distribution of structures and physical characteristics addresses fundamental questions concerning the interplay between chemical control and stochastically driven diversity.}, author = {Hybertsen, Mark S. and Venkataraman, Latha}, issn = {1520-4898}, journal = {Accounts of Chemical Research}, number = {3}, pages = {452--460}, publisher = {American Chemical Society}, title = {{Structure–property relationships in atomic-scale junctions: Histograms and beyond}}, doi = {10.1021/acs.accounts.6b00004}, volume = {49}, year = {2016}, } @article{17961, abstract = {The field of single-molecule electronics harnesses expertise from engineering, physics and chemistry to realize circuit elements at the limit of miniaturization; it is a subfield of nanoelectronics in which the electronic components are single molecules. In this Review, we survey the field from a chemical perspective and discuss the structure–property relationships of the three components that form a single-molecule junction: the anchor, the electrode and the molecular bridge. The spatial orientation and electronic coupling between each component profoundly affect the conductance properties and functions of the single-molecule device. We describe the design principles of the anchor group, the influence of the electronic configuration of the electrode and the effect of manipulating the structure of the molecular backbone and of its substituent groups. We discuss single-molecule conductance switches as well as the phenomenon of quantum interference and then trace their fundamental roots back to chemical principles.}, author = {Su, Timothy A. and Neupane, Madhav and Steigerwald, Michael L. and Venkataraman, Latha and Nuckolls, Colin}, issn = {2058-8437}, journal = {Nature Reviews Materials}, number = {3}, publisher = {Springer Nature}, title = {{Chemical principles of single-molecule electronics}}, doi = {10.1038/natrevmats.2016.2}, volume = {1}, year = {2016}, } @article{17962, abstract = {We examine structure–function relationships in a series of N-phenylbenzamide (NPBA) derivatives by using computational modeling to identify molecular structures that exhibit both rectification and good conductance together with experimental studies of bias-dependent single molecule conductance and rectification behavior using the scanning tunneling microscopy break-junction technique. From a large number of computationally screened molecular diode structures, we have identified NPBA as a promising candidate, relative to the other structures that were screened. We demonstrate experimentally that conductance and rectification are both enhanced by functionalization of the NPBA 4-carboxamido-aniline moiety with electron donating methoxy groups, and are strongly correlated with the energy of the conducting frontier orbital relative to the Fermi level of the gold leads used in break-junction experiments.}, author = {Koenigsmann, Christopher and Ding, Wendu and Koepf, Matthieu and Batra, Arunabh and Venkataraman, Latha and Negre, Christian F. A. and Brudvig, Gary W. and Crabtree, Robert H. and Batista, Victor S. and Schmuttenmaer, Charles A.}, issn = {1369-9261}, journal = {New Journal of Chemistry}, number = {9}, pages = {7373--7378}, publisher = {Royal Society of Chemistry}, title = {{Structure–function relationships in single molecule rectification by N-phenylbenzamide derivatives}}, doi = {10.1039/c6nj00870d}, volume = {40}, year = {2016}, } @article{17963, abstract = {Here we examine the impact of ring conformation on the charge transport characteristics of cyclic pentasilane structures bound to gold electrodes in single molecule junctions. We investigate the conductance properties of alkylated cyclopentasilane cis and trans stereoisomers substituted in the 1,3-position with methylthiomethyl electrode binding groups using both the scanning tunneling microscope-based break junction technique and density functional theory based ab initio calculations. In contrast with the linear ones, these cyclic silanes yield lower conductance values; calculations reveal that the constrained dihedral geometries occurring within the ring are suboptimal for σ-orbital delocalization, and therefore, conductance. Theoretical calculations reproduce the measured conductance trends for both cis and trans isomers and find several distinct conformations that are likely to form stable molecular junctions at room temperature. Due to the weakened σ-conjugation in the molecule, through-space interactions are found to contribute significantly to the conductance. This manuscript details the vast conformational flexibility in cyclopentasilanes and the tremendous impact it has on controlling conductance.}, author = {Li, Haixing and Garner, Marc H. and Shangguan, Zhichun and Zheng, Qianwen and Su, Timothy A. and Neupane, Madhav and Li, Panpan and Velian, Alexandra and Steigerwald, Michael L. and Xiao, Shengxiong and Nuckolls, Colin and Solomon, Gemma C. and Venkataraman, Latha}, issn = {2041-6539}, journal = {Chemical Science}, number = {9}, pages = {5657--5662}, publisher = {Royal Society of Chemistry}, title = {{Conformations of cyclopentasilane stereoisomers control molecular junction conductance}}, doi = {10.1039/c6sc01360k}, volume = {7}, year = {2016}, } @article{17964, abstract = {Charge transfer rates at metal/organic interfaces affect the efficiencies of devices for organic based electronics and photovoltaics. A quantitative study of electron transfer rates, which take place on the femtosecond timescale, is often difficult, especially since in most systems the molecular adsorption geometry is unknown. Here, we use X-ray resonant photoemission spectroscopy to measure ultrafast charge transfer rates across pyridine/Au(111) interfaces while also controlling the molecular orientation on the metal. We demonstrate that a bi-directional charge transfer across the molecule/metal interface is enabled upon creation of a core-exciton on the molecule with a rate that has a strong dependence on the molecular adsorption angle. Through density functional theory calculations, we show that the alignment of molecular levels relative to the metal Fermi level is dramatically altered when a core-hole is created on the molecule, allowing the lowest unoccupied molecular orbital to fall partially below the metal Fermi level. We also calculate charge transfer rates as a function of molecular adsorption geometry and find a trend that agrees with the experiment. These findings thus give insight into the charge transfer dynamics of a photo-excited molecule on a metal surface.}, author = {Cvetko, Dean and Fratesi, Guido and Kladnik, Gregor and Cossaro, Albano and Brivio, Gian Paolo and Venkataraman, Latha and Morgante, Alberto}, issn = {1463-9084}, journal = {Physical Chemistry Chemical Physics}, number = {32}, pages = {22140--22145}, publisher = {Royal Society of Chemistry}, title = {{Ultrafast electron injection into photo-excited organic molecules}}, doi = {10.1039/c6cp04099c}, volume = {18}, year = {2016}, } @inbook{18328, abstract = {We present a novel sparse modeling approach to non-rigid shape matching using only the ability to detect repeatable regions. As the input to our algorithm, we are given only two sets of regions in two shapes; no descriptors are provided so the correspondence between the regions is not know, nor do we know how many regions correspond in the two shapes. We show that even with such scarce information, it is possible to establish very accurate correspondence between the shapes by using methods from the field of sparse modeling, being this, the first non-trivial use of sparse models in shape correspondence. We formulate the problem of permuted sparse coding, in which we solve simultaneously for an unknown permutation ordering the regions on two shapes and for an unknown correspondence in functional representation. We also propose a robust variant capable of handling incomplete matches. Numerically, the problem is solved efficiently by alternating the solution of a linear assignment and a sparse coding problem. The proposed methods are evaluated qualitatively and quantitatively on standard benchmarks containing both synthetic and scanned objects.}, author = {Pokrass, Jonathan and Bronstein, Alexander and Bronstein, Michael M. and Sprechmann, Pablo and Sapiro, Guillermo}, booktitle = {Perspectives in Shape Analysis}, editor = {Breuß, Michael and Bruckstein, Alfred and Maragos, Petros and Wuhrer, Stefanie}, isbn = {9783319247243}, issn = {2197-666X}, pages = {211--230}, publisher = {Springer International Publishing}, title = {{Sparse Models for Intrinsic Shape Correspondence}}, doi = {10.1007/978-3-319-24726-7_10}, year = {2016}, } @article{1833, abstract = {Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections. }, author = {Klimova, Anna and Rudas, Tamás}, journal = {Journal of Multivariate Analysis}, pages = {440 -- 452}, publisher = {Elsevier}, title = {{On the closure of relational models}}, doi = {10.1016/j.jmva.2015.10.005}, volume = {143}, year = {2016}, } @article{18361, abstract = {3D models of humans are commonly used within computer graphics and vision, and so the ability to distinguish between body shapes is an important shape retrieval problem. We extend our recent paper which provided a benchmark for testing non-rigid 3D shape retrieval algorithms on 3D human models. This benchmark provided a far stricter challenge than previous shape benchmarks. We have added 145 new models for use as a separate training set, in order to standardise the training data used and provide a fairer comparison. We have also included experiments with the FAUST dataset of human scans. All participants of the previous benchmark study have taken part in the new tests reported here, many providing updated results using the new data. In addition, further participants have also taken part, and we provide extra analysis of the retrieval results. A total of 25 different shape retrieval methods are compared.}, author = {Pickup, D. and Sun, X. and Rosin, P. L. and Martin, R. R. and Cheng, Z. and Lian, Z. and Aono, M. and Hamza, A. Ben and Bronstein, Alexander and Bronstein, M. and Bu, S. and Castellani, U. and Cheng, S. and Garro, V. and Giachetti, A. and Godil, A. and Isaia, L. and Han, J. and Johan, H. and Lai, L. and Li, B. and Li, C. and Li, H. and Litman, R. and Liu, X. and Liu, Z. and Lu, Y. and Sun, L. and Tam, G. and Tatsuma, A. and Ye, J.}, issn = {1573-1405}, journal = {International Journal of Computer Vision}, number = {2}, pages = {169--193}, publisher = {Springer Nature}, title = {{Shape retrieval of non-rigid 3D human models}}, doi = {10.1007/s11263-016-0903-8}, volume = {120}, year = {2016}, } @inproceedings{18374, abstract = {The L 1 norm has been tremendously popular in signal and image processing in the past two decades due to its sparsity-promoting properties. More recently, its generalization to non-Euclidean domains has been found useful in shape analysis applications. For example, in conjunction with the minimization of the Dirichlet energy, it was shown to produce a compactly supported quasi-harmonic orthonormal basis, dubbed as compressed manifold modes [14]. The continuous L 1 norm on the manifold is often replaced by the vector ℓ 1 norm applied to sampled functions. We show that such an approach is incorrect in the sense that it does not consistently discretize the continuous norm and warn against its sensitivity to the specific sampling. We propose two alternative discretizations resulting in an iteratively-reweighed ℓ 2 norm. We demonstrate the proposed strategy on the compressed modes problem, which reduces to a sequence of simple eigendecomposition problems not requiring non-convex optimization on Stiefel manifolds and producing more stable and accurate results.}, author = {Bronstein, Alexander and Choukroun, Yoni and Kimmel, Ron and Sela, Matan}, booktitle = {2016 Fourth International Conference on 3D Vision (3DV)}, isbn = {9781509054084}, location = { Stanford, CA, United States}, publisher = {IEEE}, title = {{Consistent discretization and minimization of the L1 norm on manifolds}}, doi = {10.1109/3dv.2016.53}, year = {2016}, } @inproceedings{18375, abstract = {We present a method to approximate pairwise distance on a graph, having an amortized sub-linear complexity in its size. The proposed method follows the so called heat method due to Crane et al. The only additional input are the values of the eigenfunctions of the graph Laplacian at a subset of the vertices. Using these values we estimate a random walk from the source points, and normalize the result into a unit gradient function. The eigenfunctions are then used to synthesize distance values abiding by these constraints at desired locations. We show that this method works in practice on different types of inputs ranging from triangular meshes to general graphs. We also demonstrate that the resulting approximate distance is accurate enough to be used as the input to a recent method for intrinsic shape correspondence computation.}, author = {Litman, Roee and Bronstein, Alexander}, booktitle = {2016 Fourth International Conference on 3D Vision (3DV)}, isbn = {9781509054084}, location = {Stanford, CA, United States}, publisher = {IEEE}, title = {{SpectroMeter: Amortized sublinear spectral approximation of distance on graphs}}, doi = {10.1109/3dv.2016.60}, year = {2016}, } @inproceedings{18388, abstract = {The pursuit of smaller pixel sizes at ever increasing resolution in digital image sensors is mainly driven by the stringent price and form-factor requirements of sensors and optics in the cellular phone market. Recently, Eric Fossum proposed a novel concept of an image sensor with dense sub-diffraction limit one-bit pixels (jots), which can be considered a digital emulation of silver halide photographic film. This idea has been recently embodied as the EPFL Gigavision camera. A major bottleneck in the design of such sensors is the image reconstruction process, producing a continuous high dynamic range image from oversampled binary measurements. The extreme quantization of the Poisson statistics is incompatible with the assumptions of most standard image processing and enhancement frameworks. The recently proposed maximum-likelihood (ML) approach addresses this difficulty, but suffers from image artefacts and has impractically high computational complexity. In this work, we study a variant of a sensor with binary threshold pixels and propose a reconstruction algorithm combining an ML data fitting term with a sparse synthesis prior. We also show an efficient hardware-friendly real-time approximation of this inverse operator. Promising results are shown on synthetic data as well as on HDR data emulated using multiple exposures of a regular CMOS sensor.}, author = {Remez, Tal and Litany, Or and Bronstein, Alexander}, booktitle = {2016 IEEE International Conference on Computational Photography (ICCP)}, location = {Evanston, IL, United States}, publisher = {IEEE}, title = {{A picture is worth a billion bits: Real-time image reconstruction from dense binary threshold pixels}}, doi = {10.1109/iccphot.2016.7492874}, year = {2016}, } @article{18419, abstract = {Three important properties of a classification machinery are i) the system preserves the core information of the input data; ii) the training examples convey information about unseen data; and iii) the system is able to treat differently points from different classes. In this paper, we show that these fundamental properties are satisfied by the architecture of deep neural networks. We formally prove that these networks with random Gaussian weights perform a distance-preserving embedding of the data, with a special treatment for in-class and out-of-class data. Similar points at the input of the network are likely to have a similar output. The theoretical analysis of deep networks here presented exploits tools used in the compressed sensing and dictionary learning literature, thereby making a formal connection between these important topics. The derived results allow drawing conclusions on the metric learning properties of the network and their relation to its structure, as well as providing bounds on the required size of the training set such that the training examples would represent faithfully the unseen data. The results are validated with state-of-the-art trained networks.}, author = {Giryes, Raja and Sapiro, Guillermo and Bronstein, Alexander}, issn = {1941-0476}, journal = {IEEE Transactions on Signal Processing}, number = {13}, pages = {3444--3457}, publisher = {IEEE}, title = {{Deep neural networks with random Gaussian weights: A universal classification strategy?}}, doi = {10.1109/tsp.2016.2546221}, volume = {64}, year = {2016}, } @article{18426, abstract = {Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non-rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario.}, author = {Litany, O. and Rodolà, E. and Bronstein, Alexander and Bronstein, M. M. and Cremers, D.}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {5}, pages = {135--143}, publisher = {Wiley}, title = {{Non‐rigid puzzles}}, doi = {10.1111/cgf.12970}, volume = {35}, year = {2016}, } @article{18430, abstract = {Sparse models in dictionary learning have been successfully applied in a wide variety of machine learning and computer vision problems, and as a result have recently attracted increased research interest. Another interesting related problem based on linear equality constraints, namely the sparse null space (SNS) problem, first appeared in 1986 and has since inspired results on sparse basis pursuit. In this paper, we investigate the relation between the SNS problem and the analysis dictionary learning (ADL) problem, and show that the SNS problem plays a central role, and may be utilized to solve dictionary learning problems. Moreover, we propose an efficient algorithm of sparse null space basis pursuit (SNS-BP) and extend it to a solution of ADL. Experimental results on numerical synthetic data and real-world data are further presented to validate the performance of our method.}, author = {Bian, Xiao and Krim, Hamid and Bronstein, Alexander and Dai, Liyi}, issn = {1936-4954}, journal = {SIAM Journal on Imaging Sciences}, number = {3}, pages = {1107--1126}, publisher = {Society for Industrial & Applied Mathematics}, title = {{Sparsity and nullity: Paradigms for analysis dictionary learning}}, doi = {10.1137/15m1030376}, volume = {9}, year = {2016}, } @inproceedings{18434, abstract = {Notions of similarity and correspondence between geometric shapes and images are central to many tasks in geometry processing, computer vision, and computer graphics. The goal of this course is to familiarize the audience with a set of recent techniques that greatly facilitate the computation of mappings or correspondences between geometric datasets, such as 3D shapes or 2D images by formulating them as mappings between functions rather than points or triangles. Methods based on the functional map framework have recently led to state-of-the-art results in problems as diverse as non-rigid shape matching, image co-segmentation and even some aspects of tangent vector field design. One challenge in adopting these methods in practice, however, is that their exposition often assumes a significant amount of background in geometry processing, spectral methods and functional analysis, which can make it difficult to gain an intuition about their performance or about their applicability to real-life problems. In this course, we try to provide all the tools necessary to appreciate and use these techniques, while assuming very little background knowledge. We also give a unifying treatment of these techniques, which may be difficult to extract from the individual publications and, at the same time, hint at the generality of this point of view, which can help tackle many problems in the analysis and creation of visual content. This course is structured as a half day course. We will assume that the participants have knowledge of basic linear algebra and some knowledge of differential geometry, to the extent of being familiar with the concepts of a manifold and a tangent vector space. We will discuss in detail the functional approach to finding correspondences between non-rigid shapes, the design and analysis of tangent vector fields on surfaces, consistent map estimation in networks of shapes and applications to shape and image segmentation, shape variability analysis, and other areas.}, author = {Ovsjanikov, Maks and Corman, Etienne and Bronstein, Michael and Rodolà, Emanuele and Ben-Chen, Mirela and Guibas, Leonidas and Chazal, Frederic and Bronstein, Alexander}, booktitle = {SIGGRAPH ASIA 2016 Courses}, isbn = {9781450345385}, location = {Macau}, publisher = {ACM}, title = {{Computing and processing correspondences with functional maps}}, doi = {10.1145/2988458.2988494}, year = {2016}, } @inproceedings{1227, abstract = {Many biological systems can be modeled as multiaffine hybrid systems. Due to the nonlinearity of multiaffine systems, it is difficult to verify their properties of interest directly. A common strategy to tackle this problem is to construct and analyze a discrete overapproximation of the original system. However, the conservativeness of a discrete abstraction significantly determines the level of confidence we can have in the properties of the original system. In this paper, in order to reduce the conservativeness of a discrete abstraction, we propose a new method based on a sufficient and necessary decision condition for computing discrete transitions between states in the abstract system. We assume the state space partition of a multiaffine system to be based on a set of multivariate polynomials. Hence, a rectangular partition defined in terms of polynomials of the form (xi − c) is just a simple case of multivariate polynomial partition, and the new decision condition applies naturally. We analyze and demonstrate the improvement of our method over the existing methods using some examples.}, author = {Kong, Hui and Bartocci, Ezio and Bogomolov, Sergiy and Grosu, Radu and Henzinger, Thomas A and Jiang, Yu and Schilling, Christian}, location = {Grenoble, France}, pages = {128 -- 144}, publisher = {Springer}, title = {{Discrete abstraction of multiaffine systems}}, doi = {10.1007/978-3-319-47151-8_9}, volume = {9957}, year = {2016}, } @inproceedings{1231, abstract = {We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).}, author = {Alwen, Joel F and Chen, Binyi and Kamath Hosdurg, Chethan and Kolmogorov, Vladimir and Pietrzak, Krzysztof Z and Tessaro, Stefano}, location = {Vienna, Austria}, pages = {358 -- 387}, publisher = {Springer}, title = {{On the complexity of scrypt and proofs of space in the parallel random oracle model}}, doi = {10.1007/978-3-662-49896-5_13}, volume = {9666}, year = {2016}, }