@inproceedings{999, abstract = {In multi-task learning, a learner is given a collection of prediction tasks and needs to solve all of them. In contrast to previous work, which required that annotated training data must be available for all tasks, we consider a new setting, in which for some tasks, potentially most of them, only unlabeled training data is provided. Consequently, to solve all tasks, information must be transferred between tasks with labels and tasks without labels. Focusing on an instance-based transfer method we analyze two variants of this setting: when the set of labeled tasks is fixed, and when it can be actively selected by the learner. We state and prove a generalization bound that covers both scenarios and derive from it an algorithm for making the choice of labeled tasks (in the active case) and for transferring information between the tasks in a principled way. We also illustrate the effectiveness of the algorithm on synthetic and real data. }, author = {Pentina, Anastasia and Lampert, Christoph}, isbn = {9781510855144}, location = {Sydney, Australia}, pages = {2807 -- 2816}, publisher = {ML Research Press}, title = {{Multi-task learning with labeled and unlabeled tasks}}, volume = {70}, year = {2017}, } @article{373, abstract = {This review captures the synthesis, assembly, properties, and applications of copper chalcogenide NCs, which have achieved significant research interest in the last decade due to their compositional and structural versatility. The outstanding functional properties of these materials stems from the relationship between their band structure and defect concentration, including charge carrier concentration and electronic conductivity character, which consequently affects their optoelectronic, optical, and plasmonic properties. This, combined with several metastable crystal phases and stoichiometries and the low energy of formation of defects, makes the reproducible synthesis of these materials, with tunable parameters, remarkable. Further to this, the review captures the progress of the hierarchical assembly of these NCs, which bridges the link between their discrete and collective properties. Their ubiquitous application set has cross-cut energy conversion (photovoltaics, photocatalysis, thermoelectrics), energy storage (lithium-ion batteries, hydrogen generation), emissive materials (plasmonics, LEDs, biolabelling), sensors (electrochemical, biochemical), biomedical devices (magnetic resonance imaging, X-ray computer tomography), and medical therapies (photochemothermal therapies, immunotherapy, radiotherapy, and drug delivery). The confluence of advances in the synthesis, assembly, and application of these NCs in the past decade has the potential to significantly impact society, both economically and environmentally. }, author = {Coughlan, Claudia and Ibanez Sabate, Maria and Dobrozhan, Oleksandr and Singh, Ajay and Cabot, Andreu and Ryan, Kevin}, issn = {1520-6890}, journal = {Chemical Reviews}, number = {9}, pages = {5865 -- 6109}, publisher = {American Chemical Society}, title = {{Compound copper chalcogenide nanocrystals}}, doi = {10.1021/acs.chemrev.6b00376}, volume = {117}, year = {2017}, } @article{374, abstract = {The conversion of thermal energy to electricity and vice versa by means of solid state thermoelectric devices is extremely appealing. However, its cost-effectiveness is seriously hampered by the relatively high production cost and low efficiency of current thermoelectric materials and devices. To overcome present challenges and enable a successful deployment of thermoelectric systems in their wide application range, materials with significantly improved performance need to be developed. Nanostructuration can help in several ways to reach the very particular group of properties required to achieve high thermoelectric performances. Nanodomains inserted within a crystalline matrix can provide large charge carrier concentrations without strongly influencing their mobility, thus allowing to reach very high electrical conductivities. Nanostructured materials contain numerous grain boundaries that efficiently scatter mid- and long-wavelength phonons thus reducing the thermal conductivity. Furthermore, nanocrystalline domains can enhance the Seebeck coefficient by modifying the density of states and/or providing type- and energy-dependent charge carrier scattering. All these advantages can only be reached when engineering a complex type of material, nanocomposites, with exquisite control over structural and chemical parameters at multiple length scales. Since current conventional nanomaterial production technologies lack such level of control, alternative strategies need to be developed and adjusted to the specifics of the field. A particularly suitable approach to produce nanocomposites with unique level of control over their structural and compositional parameters is their bottom-up engineering from solution-processed nanoparticles. In this work, we review the state-of-the-art of this technology applied to the thermoelectric field, including the synthesis of nanoparticles of suitable materials with precisely engineered composition and surface chemistry, their combination and consolidation into nanostructured materials, the strategies to electronically dope such materials and the attempts to fabricate thermoelectric devices using nanoparticle-based nanopowders and inks.}, author = {Ortega, Silvia and Ibanez Sabate, Maria and Liu, Yu and Zhang, Yu and Kovalenko, Maksym and Cadavid, Doris and Cabot, Andreu}, issn = {1460-4744}, journal = {Chemical Society Reviews}, number = {12}, pages = {3510 -- 3528}, publisher = {Royal Society of Chemistry}, title = {{Bottom up engineering of thermoelectric nanomaterials and devices from solution processed nanoparticle building blocks}}, doi = {10.1039/c6cs00567e}, volume = {46}, year = {2017}, } @article{375, abstract = {Branched nanocrystals (NCs) enable high atomic surface exposure within a crystalline network that provides avenues for charge transport. This combination of properties makes branched NCs particularly suitable for a range of applications where both interaction with the media and charge transport are involved. Herein we report on the colloidal synthesis of branched ceria NCs by means of a ligand-mediated overgrowth mechanism. In particular, the differential coverage of oleic acid as an X-type ligand at ceria facets with different atomic density, atomic coordination deficiency, and oxygen vacancy density resulted in a preferential growth in the [111] direction and thus in the formation of ceria octapods. Alcohols, through an esterification alcoholysis reaction, promoted faster growth rates that translated into nanostructures with higher geometrical complexity, increasing the branch aspect ratio and triggering the formation of side branches. On the other hand, the presence of water resulted in a significant reduction of the growth rate, decreasing the reaction yield and eliminating side branching, which we associate to a blocking of the surface reaction sites or a displacement of the alcoholysis reaction. Overall, adjusting the amounts of each chemical, well-defined branched ceria NCs with tuned number, thickness, and length of branches and with overall size ranging from 5 to 45 nm could be produced. We further demonstrate that such branched ceria NCs are able to provide higher surface areas and related oxygen storage capacities (OSC) than quasi-spherical NCs. }, author = {Berestok, Taisiia and Guardia, Pablo and Blanco, Javier and Nafria, Raquel and Torruella, Pau and López Conesa, Luis and Estradé, Sònia and Ibanez Sabate, Maria and De Roo, Jonathan and Luo, Zhishan and Cadavid, Doris and Martins, José and Kovalenko, Maksym and Peiró, Francesca and Cabot, Andreu}, issn = {1520-5002}, journal = {Chemistry of Materials}, number = {10}, pages = {4418 -- 4424}, publisher = {American Chemical Society}, title = {{Tuning branching in ceria nanocrystals}}, doi = {10.1021/acs.chemmater.7b00896}, volume = {29}, year = {2017}, } @article{391, abstract = {Three-dimensional topological insulators are bulk insulators with Z 2 topological electronic order that gives rise to conducting light-like surface states. These surface electrons are exceptionally resistant to localization by non-magnetic disorder, and have been adopted as the basis for a wide range of proposals to achieve new quasiparticle species and device functionality. Recent studies have yielded a surprise by showing that in spite of resisting localization, topological insulator surface electrons can be reshaped by defects into distinctive resonance states. Here we use numerical simulations and scanning tunnelling microscopy data to show that these resonance states have significance well beyond the localized regime usually associated with impurity bands. At native densities in the model Bi2X3 (X=Bi, Te) compounds, defect resonance states are predicted to generate a new quantum basis for an emergent electron gas that supports diffusive electrical transport. }, author = {Xu, Yishuai and Chiu, Janet and Miao, Lin and He, Haowei and Alpichshev, Zhanybek and Kapitulnik, Aharon and Biswas, Rudro and Wray, Lewis}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Disorder enabled band structure engineering of a topological insulator surface}}, doi = {10.1038/ncomms14081}, volume = {8}, year = {2017}, } @inbook{424, abstract = {We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b, d) such that the following holds. If F is a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map C*(K)→C*(Rd).}, author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli}, booktitle = {A Journey through Discrete Mathematics: A Tribute to Jiri Matousek}, editor = {Loebl, Martin and Nešetřil, Jaroslav and Thomas, Robin}, isbn = {978-331944479-6}, pages = {407 -- 447}, publisher = {Springer}, title = {{Bounding helly numbers via betti numbers}}, doi = {10.1007/978-3-319-44479-6_17}, year = {2017}, } @inproceedings{431, abstract = {Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8 × faster than the full-precision variant. }, author = {Alistarh, Dan-Adrian and Grubic, Demjan and Li, Jerry and Tomioka, Ryota and Vojnović, Milan}, issn = {1049-5258}, location = {Long Beach, CA, United States}, pages = {1710--1721}, publisher = {Neural Information Processing Systems Foundation}, title = {{QSGD: Communication-efficient SGD via gradient quantization and encoding}}, volume = {2017}, year = {2017}, } @inproceedings{432, abstract = {Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We mainly focus on linear models, and the answer is yes for linear models. We develop a simple framework called ZipML based on one simple but novel strategy called double sampling. Our ZipML framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quanti- zation would introduce significant bias. We val- idate our framework across a range of applica- tions, and show that it enables an FPGA proto- type that is up to 6.5 × faster than an implemen- tation using full 32-bit precision. We further de- velop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7 × in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the- art XNOR-Net. }, author = {Zhang, Hantian and Li, Jerry and Kara, Kaan and Alistarh, Dan-Adrian and Liu, Ji and Zhang, Ce}, booktitle = {Proceedings of Machine Learning Research}, isbn = {978-151085514-4}, location = {Sydney, Australia}, pages = {4035 -- 4043}, publisher = {ML Research Press}, title = {{ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning}}, volume = { 70}, year = {2017}, } @article{443, abstract = {Pancreatic cancer has a five-year survival rate of ~8%, with characteristic molecular heterogeneity and restricted treatment options. Targeting metabolism has emerged as a potentially effective therapeutic strategy for cancers such as pancreatic cancer, which are driven by genetic alterations that are not tractable drug targets. Although somatic mitochondrial genome (mtDNA) mutations have been observed in various tumors types, understanding of metabolic genotype-phenotype relationships is limited.}, author = {Hardie, Rae and Van Dam, Ellen and Cowley, Mark and Han, Ting and Balaban, Seher and Pajic, Marina and Pinese, Mark and Iconomou, Mary and Shearer, Robert and Mckenna, Jessie and Miller, David and Waddell, Nicola and Pearson, John and Grimmond, Sean and Sazanov, Leonid A and Biankin, Andrew and Villas Boas, Silas and Hoy, Andrew and Turner, Nigel and Saunders, Darren}, journal = {Cancer & Metabolism}, number = {2}, publisher = {BioMed Central}, title = {{Mitochondrial mutations and metabolic adaptation in pancreatic cancer}}, doi = {10.1186/s40170-017-0164-1}, volume = {5}, year = {2017}, } @inbook{444, abstract = {Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy generation, contributing to the proton motive force used to produce ATP. It couples the transfer of two electrons between NADH and quinone to translocation of four protons across the membrane. It is the largest protein assembly of bacterial and mitochondrial respiratory chains, composed, in mammals, of up to 45 subunits with a total molecular weight of ∼1 MDa. Bacterial enzyme is about half the size, providing the important “minimal” model of complex I. The l-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. Previously, we have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus and of the membrane domain from Escherichia coli, followed by the atomic structure of intact, entire complex I from T. thermophilus. Recently, we have solved by cryo-EM a first complete atomic structure of mammalian (ovine) mitochondrial complex I. Core subunits are well conserved from the bacterial version, whilst supernumerary subunits form an interlinked, stabilizing shell around the core. Subunits containing additional cofactors, including Zn ion, NADPH and phosphopantetheine, probably have regulatory roles. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The structure of mammalian enzyme provides many insights into complex I mechanism, assembly, maturation and dysfunction, allowing detailed molecular analysis of disease-causing mutations.}, author = {Sazanov, Leonid A}, booktitle = {Mechanisms of primary energy transduction in biology }, editor = {Wikström, Mårten}, isbn = {978-1-78262-865-1}, pages = {25 -- 59}, publisher = {Royal Society of Chemistry}, title = {{Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions}}, doi = {10.1039/9781788010405-00025}, year = {2017}, } @article{445, abstract = {The Loschmidt echo, defined as the overlap between quantum wave function evolved with different Hamiltonians, quantifies the sensitivity of quantum dynamics to perturbations and is often used as a probe of quantum chaos. In this work we consider the behavior of the Loschmidt echo in the many-body localized phase, which is characterized by emergent local integrals of motion and provides a generic example of nonergodic dynamics. We demonstrate that the fluctuations of the Loschmidt echo decay as a power law in time in the many-body localized phase, in contrast to the exponential decay in few-body ergodic systems. We consider the spin-echo generalization of the Loschmidt echo and argue that the corresponding correlation function saturates to a finite value in localized systems. Slow, power-law decay of fluctuations of such spin-echo-type overlap is related to the operator spreading and is present only in the many-body localized phase, but not in a noninteracting Anderson insulator. While most of the previously considered probes of dephasing dynamics could be understood by approximating physical spin operators with local integrals of motion, the Loschmidt echo and its generalizations crucially depend on the full expansion of the physical operators via local integrals of motion operators, as well as operators which flip local integrals of motion. Hence these probes allow one to get insights into the relation between physical operators and local integrals of motion and access the operator spreading in the many-body localized phase.}, author = {Serbyn, Maksym and Abanin, Dimitry}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {1}, publisher = {American Physical Society}, title = {{Loschmidt echo in many body localized phases}}, doi = {10.1103/PhysRevB.96.014202}, volume = {96}, year = {2017}, } @article{447, abstract = {We consider last passage percolation (LPP) models with exponentially distributed random variables, which are linked to the totally asymmetric simple exclusion process (TASEP). The competition interface for LPP was introduced and studied in Ferrari and Pimentel (2005a) for cases where the corresponding exclusion process had a rarefaction fan. Here we consider situations with a shock and determine the law of the fluctuations of the competition interface around its deter- ministic law of large number position. We also study the multipoint distribution of the LPP around the shock, extending our one-point result of Ferrari and Nejjar (2015).}, author = {Ferrari, Patrik and Nejjar, Peter}, journal = {Revista Latino-Americana de Probabilidade e Estatística}, pages = {299 -- 325}, publisher = {Instituto Nacional de Matematica Pura e Aplicada}, title = {{Fluctuations of the competition interface in presence of shocks}}, doi = {10.30757/ALEA.v14-17}, volume = {9}, year = {2017}, } @article{452, abstract = {Spinning tops and yo-yos have long fascinated cultures around the world with their unexpected, graceful motions that seemingly elude gravity. Yet, due to the exceeding difficulty of creating stably spinning objects of asymmetric shape in a manual trial-and-error process, there has been little departure from rotationally symmetric designs. With modern 3D printing technologies, however, we can manufacture shapes of almost unbounded complexity at the press of a button, shifting this design complexity toward computation. In this article, we describe an algorithm to generate designs for spinning objects by optimizing their mass distribution: as input, the user provides a solid 3D model and a desired axis of rotation. Our approach then modifies the interior mass distribution such that the principal directions of the moment of inertia align with the target rotation frame. To create voids inside the model, we represent its volume with an adaptive multiresolution voxelization and optimize the discrete voxel fill values using a continuous, nonlinear formulation. We further optimize for rotational stability by maximizing the dominant principal moment. Our method is well-suited for a variety of 3D printed models, ranging from characters to abstract shapes. We demonstrate tops and yo-yos that spin surprisingly stably despite their asymmetric appearance.}, author = {Bächer, Moritz and Bickel, Bernd and Whiting, Emily and Sorkine Hornung, Olga}, journal = {Communications of the ACM}, number = {8}, pages = {92 -- 99}, publisher = {ACM}, title = {{Spin it: Optimizing moment of inertia for spinnable objects}}, doi = {10.1145/3068766}, volume = {60}, year = {2017}, } @article{453, abstract = {Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor.}, author = {Fallesen, Todd and Roostalu, Johanna and Düllberg, Christian F and Pruessner, Gunnar and Surrey, Thomas}, issn = {1542-0086}, journal = {Biophysical Journal}, number = {9}, pages = {2055 -- 2067}, publisher = {Biophysical Society}, title = {{Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement}}, doi = {10.1016/j.bpj.2017.09.006}, volume = {113}, year = {2017}, } @article{459, abstract = {The social insects bees, wasps, ants, and termites are species-rich, occur in many habitats, and often constitute a large part of the biomass. Many are also invasive, including species of termites, the red imported fire ant, and the Argentine ant. While invasive social insects have been a problem in Southern Europe for some time, Central Europa was free of invasive ant species until recently because most ants are adapted to warmer climates. Only in the 1990s, did Lasius neglectus, a close relative of the common black garden ant, arrive in Germany. First described in 1990 based on individuals collected in Budapest, the species has since been detected for example in France, Germany, Spain, England, and Kyrgyzstan. The species is spread with soil during construction work or plantings, and L. neglectus therefore is often found in parks and botanical gardens. Another invasive ant now spreading in southern Germany is Formica fuscocinerea, which occurs along rivers, including in the sandy floodplains of the river Isar. As is typical of pioneer species, F. fuscocinerea quickly becomes extremely abundant and therefore causes problems for example on playgrounds in Munich. All invasive ant species are characterized by cooperation across nests, leading to strongly interconnected, very large super-colonies. The resulting dominance results in the extinction of native ant species as well as other arthropod species and thus in the reduction of biodiversity.}, author = {Cremer, Sylvia}, issn = {2366-2875}, journal = {Rundgespräche Forum Ökologie}, pages = {105 -- 116}, publisher = {Verlag Dr. Friedrich Pfeil}, title = {{Invasive Ameisen in Europa: Wie sie sich ausbreiten und die heimische Fauna verändern}}, volume = {46}, year = {2017}, } @article{12193, abstract = {DNA methylation regulates eukaryotic gene expression and is extensively reprogrammed during animal development. However, whether developmental methylation reprogramming during the sporophytic life cycle of flowering plants regulates genes is presently unknown. Here we report a distinctive gene-targeted RNA-directed DNA methylation (RdDM) activity in the Arabidopsis thaliana male sexual lineage that regulates gene expression in meiocytes. Loss of sexual-lineage-specific RdDM causes mis-splicing of the MPS1 gene (also known as PRD2), thereby disrupting meiosis. Our results establish a regulatory paradigm in which de novo methylation creates a cell-lineage-specific epigenetic signature that controls gene expression and contributes to cellular function in flowering plants.}, author = {Walker, James and Gao, Hongbo and Zhang, Jingyi and Aldridge, Billy and Vickers, Martin and Higgins, James D. and Feng, Xiaoqi}, issn = {1546-1718}, journal = {Nature Genetics}, keywords = {Genetics}, number = {1}, pages = {130--137}, publisher = {Nature Research}, title = {{Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis}}, doi = {10.1038/s41588-017-0008-5}, volume = {50}, year = {2017}, } @proceedings{638, abstract = {This book constitutes the refereed proceedings of the 9th InternationalWorkshop on Numerical Software Verification, NSV 2016, held in Toronto, ON, Canada in July 2011 - colocated with CAV 2016, the 28th International Conference on Computer Aided Verification. The NSV workshop is dedicated to the development of logical and mathematical techniques for the reasoning about programmability and reliability.}, editor = {Bogomolov, Sergiy and Martel, Matthieu and Prabhakar, Pavithra}, issn = {0302-9743}, location = {Toronto, ON, Canada}, publisher = {Springer}, title = {{Numerical Software Verification}}, doi = {10.1007/978-3-319-54292-8}, volume = {10152}, year = {2017}, } @inproceedings{1194, abstract = {Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples. }, author = {Chatterjee, Krishnendu and Novotny, Petr and Zikelic, Djordje}, issn = {0730-8566}, location = {Paris, France}, number = {1}, pages = {145 -- 160}, publisher = {ACM}, title = {{Stochastic invariants for probabilistic termination}}, doi = {10.1145/3009837.3009873}, volume = {52}, year = {2017}, } @inproceedings{637, abstract = {For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.}, author = {Jafargholi, Zahra and Kamath Hosdurg, Chethan and Klein, Karen and Komargodski, Ilan and Pietrzak, Krzysztof Z and Wichs, Daniel}, editor = {Katz, Jonathan and Shacham, Hovav}, isbn = {978-331963687-0}, location = {Santa Barbara, CA, United States}, pages = {133 -- 163}, publisher = {Springer}, title = {{Be adaptive avoid overcommitting}}, doi = {10.1007/978-3-319-63688-7_5}, volume = {10401}, year = {2017}, } @inproceedings{1001, abstract = {We present a computational approach for designing CurveUps, curvy shells that form from an initially flat state. They consist of small rigid tiles that are tightly held together by two pre-stretched elastic sheets attached to them. Our method allows the realization of smooth, doubly curved surfaces that can be fabricated as a flat piece. Once released, the restoring forces of the pre-stretched sheets support the object to take shape in 3D. CurveUps are structurally stable in their target configuration. The design process starts with a target surface. Our method generates a tile layout in 2D and optimizes the distribution, shape, and attachment areas of the tiles to obtain a configuration that is fabricable and in which the curved up state closely matches the target. Our approach is based on an efficient approximate model and a local optimization strategy for an otherwise intractable nonlinear optimization problem. We demonstrate the effectiveness of our approach for a wide range of shapes, all realized as physical prototypes.}, author = {Guseinov, Ruslan and Miguel, Eder and Bickel, Bernd}, location = {Los Angeles, CA, United States}, number = {4}, publisher = {ACM}, title = {{CurveUps: Shaping objects from flat plates with tension-actuated curvature}}, doi = {10.1145/3072959.3073709}, volume = {36}, year = {2017}, }