[{"citation":{"ista":"Sullivan D, Csicsvari JL, Mizuseki K, Montgomery S, Diba K, Buzsáki G. 2011. Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity. Journal of Neuroscience. 31(23), 8605–8616.","chicago":"Sullivan, David, Jozsef L Csicsvari, Kenji Mizuseki, Sean Montgomery, Kamran Diba, and György Buzsáki. “Relationships between Hippocampal Sharp Waves Ripples and Fast Gamma Oscillation Influence of Dentate and Entorhinal Cortical Activity.” <i>Journal of Neuroscience</i>. Society for Neuroscience, 2011. <a href=\"https://doi.org/10.1523/JNEUROSCI.0294-11.2011\">https://doi.org/10.1523/JNEUROSCI.0294-11.2011</a>.","apa":"Sullivan, D., Csicsvari, J. L., Mizuseki, K., Montgomery, S., Diba, K., &#38; Buzsáki, G. (2011). Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity. <i>Journal of Neuroscience</i>. Society for Neuroscience. <a href=\"https://doi.org/10.1523/JNEUROSCI.0294-11.2011\">https://doi.org/10.1523/JNEUROSCI.0294-11.2011</a>","ama":"Sullivan D, Csicsvari JL, Mizuseki K, Montgomery S, Diba K, Buzsáki G. Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity. <i>Journal of Neuroscience</i>. 2011;31(23):8605-8616. doi:<a href=\"https://doi.org/10.1523/JNEUROSCI.0294-11.2011\">10.1523/JNEUROSCI.0294-11.2011</a>","short":"D. Sullivan, J.L. Csicsvari, K. Mizuseki, S. Montgomery, K. Diba, G. Buzsáki, Journal of Neuroscience 31 (2011) 8605–8616.","mla":"Sullivan, David, et al. “Relationships between Hippocampal Sharp Waves Ripples and Fast Gamma Oscillation Influence of Dentate and Entorhinal Cortical Activity.” <i>Journal of Neuroscience</i>, vol. 31, no. 23, Society for Neuroscience, 2011, pp. 8605–16, doi:<a href=\"https://doi.org/10.1523/JNEUROSCI.0294-11.2011\">10.1523/JNEUROSCI.0294-11.2011</a>.","ieee":"D. Sullivan, J. L. Csicsvari, K. Mizuseki, S. Montgomery, K. Diba, and G. Buzsáki, “Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity,” <i>Journal of Neuroscience</i>, vol. 31, no. 23. Society for Neuroscience, pp. 8605–8616, 2011."},"volume":31,"year":"2011","month":"06","type":"journal_article","abstract":[{"text":"Hippocampal sharp waves (SPWs) and associated fast (&quot;ripple&quot;) oscillations (SPW-Rs) in the CA1 region are among the most synchronous physiological patterns in the mammalian brain. Using two-dimensional arrays of electrodes for recording local field potentials and unit discharges in freely moving rats, we studied the emergence of ripple oscillations (140-220 Hz) and compared their origin and cellular-synaptic mechanisms with fast gamma oscillations (90-140 Hz). We show that (1) hippocampal SPW-Rs and fast gamma oscillations are quantitatively distinct patterns but involve the same networks and share similar mechanisms; (2) both the frequency and magnitude of fast oscillations are positively correlated with the magnitude of SPWs; (3) during both ripples and fast gamma oscillations the frequency of network oscillation is higher in CA1 than in CA3; and (4) the emergence of CA3 population bursts, a prerequisite for SPW-Rs, is biased by activity patterns in the dentate gyrus and entorhinal cortex, with the highest probability of ripples associated with an &quot;optimum&quot; level of dentate gamma power. We hypothesize that each hippocampal subnetwork possesses distinct resonant properties, tuned by the magnitude of the excitatory drive.","lang":"eng"}],"day":"08","page":"8605 - 8616","publication":"Journal of Neuroscience","title":"Relationships between hippocampal sharp waves ripples and fast gamma oscillation Influence of dentate and entorhinal cortical activity","date_updated":"2021-01-12T07:41:19Z","status":"public","date_created":"2018-12-11T12:01:36Z","issue":"23","date_published":"2011-06-08T00:00:00Z","extern":1,"intvolume":"        31","quality_controlled":0,"_id":"3138","publist_id":"3559","doi":"10.1523/JNEUROSCI.0294-11.2011","publisher":"Society for Neuroscience","publication_status":"published","author":[{"last_name":"Sullivan","first_name":"David","full_name":"Sullivan, David W"},{"id":"3FA14672-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5193-4036","full_name":"Jozsef Csicsvari","last_name":"Csicsvari","first_name":"Jozsef L"},{"first_name":"Kenji","last_name":"Mizuseki","full_name":"Mizuseki, Kenji"},{"last_name":"Montgomery","first_name":"Sean","full_name":"Montgomery, Sean M"},{"first_name":"Kamran","last_name":"Diba","full_name":"Diba, Kamran"},{"last_name":"Buzsáki","first_name":"György","full_name":"Buzsáki, György"}]},{"extern":1,"intvolume":"       108","_id":"3145","quality_controlled":0,"publication_status":"published","author":[{"full_name":"Tasic, Bosiljka","last_name":"Tasic","first_name":"Bosiljka"},{"first_name":"Simon","last_name":"Hippenmeyer","full_name":"Simon Hippenmeyer","orcid":"0000-0003-2279-1061","id":"37B36620-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wang, Charlene","first_name":"Charlene","last_name":"Wang"},{"last_name":"Gamboa","first_name":"Matthew","full_name":"Gamboa, Matthew"},{"full_name":"Zong, Hui","last_name":"Zong","first_name":"Hui"},{"full_name":"Chen-Tsai, Yanru","first_name":"Yanru","last_name":"Chen Tsai"},{"full_name":"Luo, Liqun","last_name":"Luo","first_name":"Liqun"}],"publist_id":"3549","doi":"10.1073/pnas.1019507108","publisher":"National Academy of Sciences","volume":108,"year":"2011","month":"05","type":"journal_article","citation":{"short":"B. Tasic, S. Hippenmeyer, C. Wang, M. Gamboa, H. Zong, Y. Chen Tsai, L. Luo, PNAS 108 (2011) 7902–7907.","ieee":"B. Tasic <i>et al.</i>, “Site specific integrase mediated transgenesis in mice via pronuclear injection,” <i>PNAS</i>, vol. 108, no. 19. National Academy of Sciences, pp. 7902–7907, 2011.","mla":"Tasic, Bosiljka, et al. “Site Specific Integrase Mediated Transgenesis in Mice via Pronuclear Injection.” <i>PNAS</i>, vol. 108, no. 19, National Academy of Sciences, 2011, pp. 7902–07, doi:<a href=\"https://doi.org/10.1073/pnas.1019507108\">10.1073/pnas.1019507108</a>.","apa":"Tasic, B., Hippenmeyer, S., Wang, C., Gamboa, M., Zong, H., Chen Tsai, Y., &#38; Luo, L. (2011). Site specific integrase mediated transgenesis in mice via pronuclear injection. <i>PNAS</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.1019507108\">https://doi.org/10.1073/pnas.1019507108</a>","ama":"Tasic B, Hippenmeyer S, Wang C, et al. Site specific integrase mediated transgenesis in mice via pronuclear injection. <i>PNAS</i>. 2011;108(19):7902-7907. doi:<a href=\"https://doi.org/10.1073/pnas.1019507108\">10.1073/pnas.1019507108</a>","chicago":"Tasic, Bosiljka, Simon Hippenmeyer, Charlene Wang, Matthew Gamboa, Hui Zong, Yanru Chen Tsai, and Liqun Luo. “Site Specific Integrase Mediated Transgenesis in Mice via Pronuclear Injection.” <i>PNAS</i>. National Academy of Sciences, 2011. <a href=\"https://doi.org/10.1073/pnas.1019507108\">https://doi.org/10.1073/pnas.1019507108</a>.","ista":"Tasic B, Hippenmeyer S, Wang C, Gamboa M, Zong H, Chen Tsai Y, Luo L. 2011. Site specific integrase mediated transgenesis in mice via pronuclear injection. PNAS. 108(19), 7902–7907."},"status":"public","date_updated":"2021-01-12T07:41:22Z","date_created":"2018-12-11T12:01:39Z","issue":"19","date_published":"2011-05-10T00:00:00Z","abstract":[{"text":"Microinjection of recombinant DNA into zygotic pronuclei has been widely used for producing transgenic mice. However, with this method, the insertion site, integrity, and copy number of the transgene cannot be controlled. Here, we present an integrase-based approach to produce transgenic mice via pronuclear injection, whereby an intact single-copy transgene can be inserted into predetermined chromosomal loci with high efficiency (up to 40%), and faithfully transmitted through generations. We show that neighboring transgenic elements and bacterial DNA within the transgene cause profound silencing and expression variability of the transgenic marker. Removal of these undesirable elements leads to global high-level marker expression from transgenes driven by a ubiquitous promoter. We also obtained faithful marker expression from a tissue-specific promoter. The technique presented here will greatly facilitate murine transgenesis and precise structure/function dissection of mammalian gene function and regulation in vivo.","lang":"eng"}],"day":"10","page":"7902 - 7907","title":"Site specific integrase mediated transgenesis in mice via pronuclear injection","publication":"PNAS"},{"extern":1,"intvolume":"       146","quality_controlled":0,"_id":"3147","publist_id":"3548","doi":"10.1016/j.cell.2011.06.014","publisher":"Cell Press","author":[{"last_name":"Liu","first_name":"Chong","full_name":"Liu, Chong"},{"first_name":"Jonathan","last_name":"Sage","full_name":"Sage, Jonathan C"},{"first_name":"Michael","last_name":"Miller","full_name":"Miller, Michael R"},{"last_name":"Verhaak","first_name":"Roel","full_name":"Verhaak, Roel G"},{"last_name":"Hippenmeyer","first_name":"Simon","id":"37B36620-F248-11E8-B48F-1D18A9856A87","full_name":"Simon Hippenmeyer","orcid":"0000-0003-2279-1061"},{"last_name":"Vogel","first_name":"Hannes","full_name":"Vogel, Hannes"},{"first_name":"Oded","last_name":"Foreman","full_name":"Foreman, Oded"},{"first_name":"Roderick","last_name":"Bronson","full_name":"Bronson, Roderick T"},{"first_name":"Akiko","last_name":"Nishiyama","full_name":"Nishiyama, Akiko"},{"last_name":"Luo","first_name":"Liqun","full_name":"Luo, Liqun"},{"first_name":"Hui","last_name":"Zong","full_name":"Zong, Hui"}],"publication_status":"published","citation":{"mla":"Liu, Chong, et al. “Mosaic Analysis with Double Markers Reveals Tumor Cell of Origin in Glioma.” <i>Cell</i>, vol. 146, no. 2, Cell Press, 2011, pp. 209–21, doi:<a href=\"https://doi.org/10.1016/j.cell.2011.06.014\">10.1016/j.cell.2011.06.014</a>.","ieee":"C. Liu <i>et al.</i>, “Mosaic analysis with double markers reveals tumor cell of origin in glioma,” <i>Cell</i>, vol. 146, no. 2. Cell Press, pp. 209–221, 2011.","short":"C. Liu, J. Sage, M. Miller, R. Verhaak, S. Hippenmeyer, H. Vogel, O. Foreman, R. Bronson, A. Nishiyama, L. Luo, H. Zong, Cell 146 (2011) 209–221.","apa":"Liu, C., Sage, J., Miller, M., Verhaak, R., Hippenmeyer, S., Vogel, H., … Zong, H. (2011). Mosaic analysis with double markers reveals tumor cell of origin in glioma. <i>Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cell.2011.06.014\">https://doi.org/10.1016/j.cell.2011.06.014</a>","ama":"Liu C, Sage J, Miller M, et al. Mosaic analysis with double markers reveals tumor cell of origin in glioma. <i>Cell</i>. 2011;146(2):209-221. doi:<a href=\"https://doi.org/10.1016/j.cell.2011.06.014\">10.1016/j.cell.2011.06.014</a>","chicago":"Liu, Chong, Jonathan Sage, Michael Miller, Roel Verhaak, Simon Hippenmeyer, Hannes Vogel, Oded Foreman, et al. “Mosaic Analysis with Double Markers Reveals Tumor Cell of Origin in Glioma.” <i>Cell</i>. Cell Press, 2011. <a href=\"https://doi.org/10.1016/j.cell.2011.06.014\">https://doi.org/10.1016/j.cell.2011.06.014</a>.","ista":"Liu C, Sage J, Miller M, Verhaak R, Hippenmeyer S, Vogel H, Foreman O, Bronson R, Nishiyama A, Luo L, Zong H. 2011. Mosaic analysis with double markers reveals tumor cell of origin in glioma. Cell. 146(2), 209–221."},"volume":146,"year":"2011","month":"07","type":"journal_article","abstract":[{"lang":"eng","text":"Cancer cell of origin is difficult to identify by analyzing cells within terminal stage tumors, whose identity could be concealed by the acquired plasticity. Thus, an ideal approach to identify the cell of origin is to analyze proliferative abnormalities in distinct lineages prior to malignancy. Here, we use mosaic analysis with double markers (MADM) in mice to model gliomagenesis by initiating concurrent p53/Nf1 mutations sporadically in neural stem cells (NSCs). Surprisingly, MADM-based lineage tracing revealed significant aberrant growth prior to malignancy only in oligodendrocyte precursor cells (OPCs), but not in any other NSC-derived lineages or NSCs themselves. Upon tumor formation, phenotypic and transcriptome analyses of tumor cells revealed salient OPC features. Finally, introducing the same p53/Nf1 mutations directly into OPCs consistently led to gliomagenesis. Our findings suggest OPCs as the cell of origin in this model, even when initial mutations occur in NSCs, and highlight the importance of analyzing premalignant stages to identify the cancer cell of origin."}],"day":"22","page":"209 - 221","publication":"Cell","title":"Mosaic analysis with double markers reveals tumor cell of origin in glioma","status":"public","date_updated":"2021-01-12T07:41:23Z","issue":"2","date_created":"2018-12-11T12:01:40Z","date_published":"2011-07-22T00:00:00Z"},{"publisher":"Cell Press","publist_id":"3541","doi":"10.1016/j.devcel.2010.12.007","author":[{"full_name":"DeGennaro, Matthew","first_name":"Matthew","last_name":"Degennaro"},{"first_name":"Thomas","last_name":"Hurd","full_name":"Hurd, Thomas R"},{"first_name":"Daria E","last_name":"Siekhaus","orcid":"0000-0001-8323-8353","full_name":"Daria Siekhaus","id":"3D224B9E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Benoit","last_name":"Biteau","full_name":"Biteau, Benoit"},{"first_name":"Heinrich","last_name":"Jasper","full_name":"Jasper, Heinrich"},{"full_name":"Lehmann, Ruth","first_name":"Ruth","last_name":"Lehmann"}],"publication_status":"published","_id":"3154","quality_controlled":0,"extern":1,"intvolume":"        20","page":"233 - 243","publication":"Developmental Cell","title":"Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion","abstract":[{"lang":"eng","text":"Regulated adhesion between cells and their environment is critical for normal cell migration. We have identified mutations in a gene encoding the Drosophila hydrogen peroxide (H2O2)-degrading enzyme Jafrac1, which lead to germ cell adhesion defects. During gastrulation, primordial germ cells (PGCs) associate tightly with the invaginating midgut primordium as it enters the embryo; however, in embryos from jafrac1 mutant mothers this association is disrupted, leaving some PGCs trailing on the outside of the embryo. We observed similar phenotypes in embryos from DE-cadherin/shotgun (shg) mutant mothers and were able to rescue the jafrac1 phenotype by increasing DE-cadherin levels. This and our biochemical evidence strongly suggest that Jafrac1-mediated reduction of H2O2 is required to maintain DE-cadherin protein levels in the early embryo. Our results present in vivo evidence of a peroxiredoxin regulating DE-cadherin-mediated adhesion."}],"day":"15","issue":"2","date_created":"2018-12-11T12:01:42Z","date_published":"2011-02-15T00:00:00Z","date_updated":"2021-01-12T07:41:26Z","status":"public","citation":{"chicago":"Degennaro, Matthew, Thomas Hurd, Daria E Siekhaus, Benoit Biteau, Heinrich Jasper, and Ruth Lehmann. “Peroxiredoxin Stabilization of DE-Cadherin Promotes Primordial Germ Cell Adhesion.” <i>Developmental Cell</i>. Cell Press, 2011. <a href=\"https://doi.org/10.1016/j.devcel.2010.12.007\">https://doi.org/10.1016/j.devcel.2010.12.007</a>.","ista":"Degennaro M, Hurd T, Siekhaus DE, Biteau B, Jasper H, Lehmann R. 2011. Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion. Developmental Cell. 20(2), 233–243.","short":"M. Degennaro, T. Hurd, D.E. Siekhaus, B. Biteau, H. Jasper, R. Lehmann, Developmental Cell 20 (2011) 233–243.","ieee":"M. Degennaro, T. Hurd, D. E. Siekhaus, B. Biteau, H. Jasper, and R. Lehmann, “Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion,” <i>Developmental Cell</i>, vol. 20, no. 2. Cell Press, pp. 233–243, 2011.","mla":"Degennaro, Matthew, et al. “Peroxiredoxin Stabilization of DE-Cadherin Promotes Primordial Germ Cell Adhesion.” <i>Developmental Cell</i>, vol. 20, no. 2, Cell Press, 2011, pp. 233–43, doi:<a href=\"https://doi.org/10.1016/j.devcel.2010.12.007\">10.1016/j.devcel.2010.12.007</a>.","ama":"Degennaro M, Hurd T, Siekhaus DE, Biteau B, Jasper H, Lehmann R. Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion. <i>Developmental Cell</i>. 2011;20(2):233-243. doi:<a href=\"https://doi.org/10.1016/j.devcel.2010.12.007\">10.1016/j.devcel.2010.12.007</a>","apa":"Degennaro, M., Hurd, T., Siekhaus, D. E., Biteau, B., Jasper, H., &#38; Lehmann, R. (2011). Peroxiredoxin stabilization of DE-cadherin promotes primordial germ cell adhesion. <i>Developmental Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.devcel.2010.12.007\">https://doi.org/10.1016/j.devcel.2010.12.007</a>"},"month":"02","type":"journal_article","volume":20,"year":"2011"},{"department":[{"_id":"ChLa"}],"publication_status":"published","author":[{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","first_name":"Christoph"}],"publist_id":"3522","publisher":"Neural Information Processing Systems","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","_id":"3163","date_updated":"2023-10-17T11:47:35Z","status":"public","date_published":"2011-12-01T00:00:00Z","date_created":"2018-12-11T12:01:45Z","day":"01","abstract":[{"text":"We study multi-label prediction for structured output sets, a problem that occurs, for example, in object detection in images, secondary structure prediction in computational biology, and graph matching with symmetries. Conventional multilabel classification techniques are typically not applicable in this situation, because they require explicit enumeration of the label set, which is infeasible in case of structured outputs. Relying on techniques originally designed for single-label structured prediction, in particular structured support vector machines, results in reduced prediction accuracy, or leads to infeasible optimization problems. In this work we derive a maximum-margin training formulation for multi-label structured prediction that remains computationally tractable while achieving high prediction accuracy. It also shares most beneficial properties with single-label maximum-margin approaches, in particular formulation as a convex optimization problem, efficient working set training, and PAC-Bayesian generalization bounds.","lang":"eng"}],"conference":{"start_date":"2011-12-12","location":"Granada, Spain","end_date":"2011-12-14","name":"NIPS: Neural Information Processing Systems"},"title":"Maximum margin multi-label structured prediction","related_material":{"record":[{"relation":"later_version","id":"3322","status":"public"}]},"scopus_import":1,"year":"2011","type":"conference","month":"12","language":[{"iso":"eng"}],"citation":{"mla":"Lampert, Christoph. <i>Maximum Margin Multi-Label Structured Prediction</i>. Neural Information Processing Systems, 2011.","ieee":"C. Lampert, “Maximum margin multi-label structured prediction,” presented at the NIPS: Neural Information Processing Systems, Granada, Spain, 2011.","short":"C. Lampert, in:, Neural Information Processing Systems, 2011.","ama":"Lampert C. Maximum margin multi-label structured prediction. In: Neural Information Processing Systems; 2011.","apa":"Lampert, C. (2011). Maximum margin multi-label structured prediction. Presented at the NIPS: Neural Information Processing Systems, Granada, Spain: Neural Information Processing Systems.","chicago":"Lampert, Christoph. “Maximum Margin Multi-Label Structured Prediction.” Neural Information Processing Systems, 2011.","ista":"Lampert C. 2011. Maximum margin multi-label structured prediction. NIPS: Neural Information Processing Systems."},"oa_version":"None"},{"_id":"3204","quality_controlled":0,"intvolume":"      6907","extern":1,"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Vladimir Kolmogorov","last_name":"Kolmogorov","first_name":"Vladimir"}],"publication_status":"published","alternative_title":["LNCS"],"publisher":"Springer","doi":"10.1007/978-3-642-22993-0_37","publist_id":"3478","type":"conference","month":"08","year":"2011","volume":6907,"citation":{"chicago":"Kolmogorov, Vladimir. “Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions,” 6907:400–411. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-22993-0_37\">https://doi.org/10.1007/978-3-642-22993-0_37</a>.","ista":"Kolmogorov V. 2011. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6907, 400–411.","ieee":"V. Kolmogorov, “Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions,” presented at the MFCS: Mathematical Foundations of Computer Science, 2011, vol. 6907, pp. 400–411.","mla":"Kolmogorov, Vladimir. <i>Submodularity on a Tree: Unifying Submodularity on a Tree: Unifying L-Convex and Bisubmodular Functions Convex and Bisubmodular Functions</i>. Vol. 6907, Springer, 2011, pp. 400–11, doi:<a href=\"https://doi.org/10.1007/978-3-642-22993-0_37\">10.1007/978-3-642-22993-0_37</a>.","short":"V. Kolmogorov, in:, Springer, 2011, pp. 400–411.","apa":"Kolmogorov, V. (2011). Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions (Vol. 6907, pp. 400–411). Presented at the MFCS: Mathematical Foundations of Computer Science, Springer. <a href=\"https://doi.org/10.1007/978-3-642-22993-0_37\">https://doi.org/10.1007/978-3-642-22993-0_37</a>","ama":"Kolmogorov V. Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions. In: Vol 6907. Springer; 2011:400-411. doi:<a href=\"https://doi.org/10.1007/978-3-642-22993-0_37\">10.1007/978-3-642-22993-0_37</a>"},"date_published":"2011-08-09T00:00:00Z","main_file_link":[{"open_access":"0","url":"http://arxiv.org/pdf/1007.1229v3"}],"date_created":"2018-12-11T12:02:00Z","date_updated":"2021-01-12T07:41:47Z","status":"public","conference":{"name":"MFCS: Mathematical Foundations of Computer Science"},"title":"Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions","page":"400 - 411","day":"09","abstract":[{"text":"We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms. ","lang":"eng"}]},{"citation":{"chicago":"Tarlow, Daniel, Druv Batra, Pushmeet Kohli, and Vladimir Kolmogorov. “Dynamic Tree Block Coordinate Ascent,” 113–20. Omnipress, 2011.","ista":"Tarlow D, Batra D, Kohli P, Kolmogorov V. 2011. Dynamic tree block coordinate ascent. ICML: International Conference on Machine Learning, 113–120.","short":"D. Tarlow, D. Batra, P. Kohli, V. Kolmogorov, in:, Omnipress, 2011, pp. 113–120.","ieee":"D. Tarlow, D. Batra, P. Kohli, and V. Kolmogorov, “Dynamic tree block coordinate ascent,” presented at the ICML: International Conference on Machine Learning, 2011, pp. 113–120.","mla":"Tarlow, Daniel, et al. <i>Dynamic Tree Block Coordinate Ascent</i>. Omnipress, 2011, pp. 113–20.","ama":"Tarlow D, Batra D, Kohli P, Kolmogorov V. Dynamic tree block coordinate ascent. In: Omnipress; 2011:113-120.","apa":"Tarlow, D., Batra, D., Kohli, P., &#38; Kolmogorov, V. (2011). Dynamic tree block coordinate ascent (pp. 113–120). Presented at the ICML: International Conference on Machine Learning, Omnipress."},"year":"2011","month":"01","type":"conference","abstract":[{"lang":"eng","text":"This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems."}],"day":"01","page":"113 - 120","conference":{"name":"ICML: International Conference on Machine Learning"},"title":"Dynamic tree block coordinate ascent","status":"public","date_updated":"2021-01-12T07:41:47Z","date_created":"2018-12-11T12:02:00Z","date_published":"2011-01-01T00:00:00Z","main_file_link":[{"url":"http://ttic.uchicago.edu/~dbatra/publications/assets/tbkk_icml11.pdf","open_access":"0"}],"extern":1,"quality_controlled":0,"_id":"3205","publist_id":"3475","publisher":"Omnipress","author":[{"first_name":"Daniel","last_name":"Tarlow","full_name":"Tarlow, Daniel"},{"last_name":"Batra","first_name":"Druv","full_name":"Batra, Druv"},{"full_name":"Kohli, Pushmeet","first_name":"Pushmeet","last_name":"Kohli"},{"full_name":"Vladimir Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"}],"publication_status":"published"},{"title":"Submodular decomposition framework for inference in associative Markov networks with global constraints","conference":{"name":"CVPR: Computer Vision and Pattern Recognition"},"page":"1889 - 1896","day":"22","abstract":[{"lang":"eng","text":"In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems."}],"date_published":"2011-08-22T00:00:00Z","main_file_link":[{"open_access":"0","url":"http://arxiv.org/pdf/1103.1077v1"}],"date_created":"2018-12-11T12:02:00Z","date_updated":"2021-01-12T07:41:47Z","status":"public","citation":{"ista":"Osokin A, Vetrov D, Kolmogorov V. 2011. Submodular decomposition framework for inference in associative Markov networks with global constraints. CVPR: Computer Vision and Pattern Recognition, 1889–1896.","chicago":"Osokin, Anton, Dmitry Vetrov, and Vladimir Kolmogorov. “Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints,” 1889–96. IEEE, 2011. <a href=\"https://doi.org/10.1109/CVPR.2011.5995361\">https://doi.org/10.1109/CVPR.2011.5995361</a>.","ama":"Osokin A, Vetrov D, Kolmogorov V. Submodular decomposition framework for inference in associative Markov networks with global constraints. In: IEEE; 2011:1889-1896. doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995361\">10.1109/CVPR.2011.5995361</a>","apa":"Osokin, A., Vetrov, D., &#38; Kolmogorov, V. (2011). Submodular decomposition framework for inference in associative Markov networks with global constraints (pp. 1889–1896). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. <a href=\"https://doi.org/10.1109/CVPR.2011.5995361\">https://doi.org/10.1109/CVPR.2011.5995361</a>","short":"A. Osokin, D. Vetrov, V. Kolmogorov, in:, IEEE, 2011, pp. 1889–1896.","ieee":"A. Osokin, D. Vetrov, and V. Kolmogorov, “Submodular decomposition framework for inference in associative Markov networks with global constraints,” presented at the CVPR: Computer Vision and Pattern Recognition, 2011, pp. 1889–1896.","mla":"Osokin, Anton, et al. <i>Submodular Decomposition Framework for Inference in Associative Markov Networks with Global Constraints</i>. IEEE, 2011, pp. 1889–96, doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995361\">10.1109/CVPR.2011.5995361</a>."},"type":"conference","month":"08","year":"2011","publisher":"IEEE","doi":"10.1109/CVPR.2011.5995361","publist_id":"3476","author":[{"first_name":"Anton","last_name":"Osokin","full_name":"Osokin, Anton"},{"full_name":"Vetrov, Dmitry","first_name":"Dmitry","last_name":"Vetrov"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Vladimir Kolmogorov"}],"publication_status":"published","quality_controlled":0,"_id":"3206","extern":1},{"status":"public","date_updated":"2021-01-12T07:41:48Z","date_published":"2011-08-22T00:00:00Z","date_created":"2018-12-11T12:02:01Z","day":"22","abstract":[{"lang":"eng","text":"Cosegmentation is typically defined as the task of jointly segmenting something similar in a given set of images. Existing methods are too generic and so far have not demonstrated competitive results for any specific task. In this paper we overcome this limitation by adding two new aspects to cosegmentation: (1) the &quot;something&quot; has to be an object, and (2) the &quot;similarity&quot; measure is learned. In this way, we are able to achieve excellent results on the recently introduced iCoseg dataset, which contains small sets of images of either the same object instance or similar objects of the same class. The challenge of this dataset lies in the extreme changes in viewpoint, lighting, and object deformations within each set. We are able to considerably outperform several competitors. To achieve this performance, we borrow recent ideas from object recognition: the use of powerful features extracted from a pool of candidate object-like segmentations. We believe that our work will be beneficial to several application areas, such as image retrieval."}],"title":"Object cosegmentation","conference":{"name":"CVPR: Computer Vision and Pattern Recognition"},"page":"2217 - 2224","year":"2011","type":"conference","month":"08","citation":{"chicago":"Vicente, Sara, Carsten Rother, and Vladimir Kolmogorov. “Object Cosegmentation,” 2217–24. IEEE, 2011. <a href=\"https://doi.org/10.1109/CVPR.2011.5995530\">https://doi.org/10.1109/CVPR.2011.5995530</a>.","ista":"Vicente S, Rother C, Kolmogorov V. 2011. Object cosegmentation. CVPR: Computer Vision and Pattern Recognition, 2217–2224.","short":"S. Vicente, C. Rother, V. Kolmogorov, in:, IEEE, 2011, pp. 2217–2224.","mla":"Vicente, Sara, et al. <i>Object Cosegmentation</i>. IEEE, 2011, pp. 2217–24, doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995530\">10.1109/CVPR.2011.5995530</a>.","ieee":"S. Vicente, C. Rother, and V. Kolmogorov, “Object cosegmentation,” presented at the CVPR: Computer Vision and Pattern Recognition, 2011, pp. 2217–2224.","apa":"Vicente, S., Rother, C., &#38; Kolmogorov, V. (2011). Object cosegmentation (pp. 2217–2224). Presented at the CVPR: Computer Vision and Pattern Recognition, IEEE. <a href=\"https://doi.org/10.1109/CVPR.2011.5995530\">https://doi.org/10.1109/CVPR.2011.5995530</a>","ama":"Vicente S, Rother C, Kolmogorov V. Object cosegmentation. In: IEEE; 2011:2217-2224. doi:<a href=\"https://doi.org/10.1109/CVPR.2011.5995530\">10.1109/CVPR.2011.5995530</a>"},"publication_status":"published","author":[{"full_name":"Vicente, Sara","first_name":"Sara","last_name":"Vicente"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Vladimir Kolmogorov","last_name":"Kolmogorov","first_name":"Vladimir"}],"doi":"10.1109/CVPR.2011.5995530","publist_id":"3477","publisher":"IEEE","extern":1,"_id":"3207","quality_controlled":0},{"extern":1,"quality_controlled":0,"_id":"3236","publist_id":"3443","doi":"10.1007/978-3-642-19571-6_5","publisher":"Springer","alternative_title":["LNCS"],"author":[{"full_name":"Jain, Abhishek","first_name":"Abhishek","last_name":"Jain"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Krzysztof Pietrzak","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z"}],"publication_status":"published","citation":{"chicago":"Jain, Abhishek, and Krzysztof Z Pietrzak. “Parallel Repetition for Leakage Resilience Amplification Revisited,” 6597:58–69. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-19571-6_5\">https://doi.org/10.1007/978-3-642-19571-6_5</a>.","ista":"Jain A, Pietrzak KZ. 2011. Parallel repetition for leakage resilience amplification revisited. TCC: Theory of Cryptography Conference, LNCS, vol. 6597, 58–69.","ieee":"A. Jain and K. Z. Pietrzak, “Parallel repetition for leakage resilience amplification revisited,” presented at the TCC: Theory of Cryptography Conference, 2011, vol. 6597, pp. 58–69.","mla":"Jain, Abhishek, and Krzysztof Z. Pietrzak. <i>Parallel Repetition for Leakage Resilience Amplification Revisited</i>. Vol. 6597, Springer, 2011, pp. 58–69, doi:<a href=\"https://doi.org/10.1007/978-3-642-19571-6_5\">10.1007/978-3-642-19571-6_5</a>.","short":"A. Jain, K.Z. Pietrzak, in:, Springer, 2011, pp. 58–69.","ama":"Jain A, Pietrzak KZ. Parallel repetition for leakage resilience amplification revisited. In: Vol 6597. Springer; 2011:58-69. doi:<a href=\"https://doi.org/10.1007/978-3-642-19571-6_5\">10.1007/978-3-642-19571-6_5</a>","apa":"Jain, A., &#38; Pietrzak, K. Z. (2011). Parallel repetition for leakage resilience amplification revisited (Vol. 6597, pp. 58–69). Presented at the TCC: Theory of Cryptography Conference, Springer. <a href=\"https://doi.org/10.1007/978-3-642-19571-6_5\">https://doi.org/10.1007/978-3-642-19571-6_5</a>"},"year":"2011","volume":"6597 ","month":"01","type":"conference","abstract":[{"text":"If a cryptographic primitive remains secure even if ℓ bits about the secret key are leaked to the adversary, one would expect that at least one of n independent instantiations of the scheme remains secure given n·ℓ bits of leakage. This intuition has been proven true for schemes satisfying some special information-theoretic properties by Alwen et al. [Eurocrypt'10]. On the negative side, Lewko and Waters [FOCS'10] construct a CPA secure public-key encryption scheme for which this intuition fails. The counterexample of Lewko and Waters leaves open the interesting possibility that for any scheme there exists a constant c&gt;0, such that n fold repetition remains secure against c·n·ℓ bits of leakage. Furthermore, their counterexample requires the n copies of the encryption scheme to share a common reference parameter, leaving open the possibility that the intuition is true for all schemes without common setup. In this work we give a stronger counterexample ruling out these possibilities. We construct a signature scheme such that: 1. a single instantiation remains secure given ℓ = log(k) bits of leakage where k is a security parameter. 2. any polynomial number of independent instantiations can be broken (in the strongest sense of key-recovery) given ℓ′ = poly(k) bits of leakage. Note that ℓ does not depend on the number of instances. The computational assumption underlying our counterexample is that non-interactive computationally sound proofs exist. Moreover, under a stronger (non-standard) assumption about such proofs, our counterexample does not require a common reference parameter. The underlying idea of our counterexample is rather generic and can be applied to other primitives like encryption schemes. © 2011 International Association for Cryptologic Research.","lang":"eng"}],"day":"01","page":"58 - 69","title":"Parallel repetition for leakage resilience amplification revisited","conference":{"name":"TCC: Theory of Cryptography Conference"},"date_updated":"2021-01-12T07:42:00Z","status":"public","date_created":"2018-12-11T12:02:11Z","date_published":"2011-01-01T00:00:00Z"},{"language":[{"iso":"eng"}],"citation":{"chicago":"Kiltz, Eike, Krzysztof Z Pietrzak, David Cash, Abhishek Jain, and Daniele Venturi. “Efficient Authentication from Hard Learning Problems,” 6632:7–26. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-20465-4_3\">https://doi.org/10.1007/978-3-642-20465-4_3</a>.","ista":"Kiltz E, Pietrzak KZ, Cash D, Jain A, Venturi D. 2011. Efficient authentication from hard learning problems. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 6632, 7–26.","short":"E. Kiltz, K.Z. Pietrzak, D. Cash, A. Jain, D. Venturi, in:, Springer, 2011, pp. 7–26.","mla":"Kiltz, Eike, et al. <i>Efficient Authentication from Hard Learning Problems</i>. Vol. 6632, Springer, 2011, pp. 7–26, doi:<a href=\"https://doi.org/10.1007/978-3-642-20465-4_3\">10.1007/978-3-642-20465-4_3</a>.","ieee":"E. Kiltz, K. Z. Pietrzak, D. Cash, A. Jain, and D. Venturi, “Efficient authentication from hard learning problems,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011, vol. 6632, pp. 7–26.","apa":"Kiltz, E., Pietrzak, K. Z., Cash, D., Jain, A., &#38; Venturi, D. (2011). Efficient authentication from hard learning problems (Vol. 6632, pp. 7–26). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Tallinn, Estonia: Springer. <a href=\"https://doi.org/10.1007/978-3-642-20465-4_3\">https://doi.org/10.1007/978-3-642-20465-4_3</a>","ama":"Kiltz E, Pietrzak KZ, Cash D, Jain A, Venturi D. Efficient authentication from hard learning problems. In: Vol 6632. Springer; 2011:7-26. doi:<a href=\"https://doi.org/10.1007/978-3-642-20465-4_3\">10.1007/978-3-642-20465-4_3</a>"},"oa_version":"None","year":"2011","volume":6632,"type":"conference","month":"05","day":"01","abstract":[{"text":"We construct efficient authentication protocols and message-authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work - starting with the HB protocol of Hopper and Blum in 2001 - until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle (MIM) attacks. A MAC implies such a (two-round) protocol. © 2011 International Association for Cryptologic Research","lang":"eng"}],"title":"Efficient authentication from hard learning problems","related_material":{"record":[{"status":"public","relation":"later_version","id":"1187"}]},"conference":{"location":"Tallinn, Estonia","start_date":"2011-05-15","end_date":"2011-05-19","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"page":"7 - 26","date_updated":"2023-09-20T11:20:57Z","status":"public","date_published":"2011-05-01T00:00:00Z","date_created":"2018-12-11T12:02:11Z","intvolume":"      6632","extern":"1","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","acknowledgement":"The European Regional Development Fund (ERDF),Guardtime,Qualcomm,Swedbank","quality_controlled":"1","_id":"3238","doi":"10.1007/978-3-642-20465-4_3","publist_id":"3442","alternative_title":["LNCS"],"publisher":"Springer","publication_status":"published","author":[{"full_name":"Kiltz, Eike","last_name":"Kiltz","first_name":"Eike"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"full_name":"Cash, David","first_name":"David","last_name":"Cash"},{"last_name":"Jain","first_name":"Abhishek","full_name":"Jain, Abhishek"},{"last_name":"Venturi","first_name":"Daniele","full_name":"Venturi, Daniele"}]},{"extern":1,"quality_controlled":0,"_id":"3239","publist_id":"3441","doi":"10.1007/978-3-642-22006-7_33","publisher":"Springer","alternative_title":["LNCS"],"publication_status":"published","author":[{"full_name":"Faust, Sebastian","last_name":"Faust","first_name":"Sebastian"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Krzysztof Pietrzak"},{"last_name":"Venturi","first_name":"Daniele","full_name":"Venturi, Daniele"}],"citation":{"ista":"Faust S, Pietrzak KZ, Venturi D. 2011. Tamper proof circuits How to trade leakage for tamper resilience. ICALP: Automata, Languages and Programming, LNCS, vol. 6755, 391–402.","chicago":"Faust, Sebastian, Krzysztof Z Pietrzak, and Daniele Venturi. “Tamper Proof Circuits How to Trade Leakage for Tamper Resilience,” 6755:391–402. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-22006-7_33\">https://doi.org/10.1007/978-3-642-22006-7_33</a>.","apa":"Faust, S., Pietrzak, K. Z., &#38; Venturi, D. (2011). Tamper proof circuits How to trade leakage for tamper resilience (Vol. 6755, pp. 391–402). Presented at the ICALP: Automata, Languages and Programming, Springer. <a href=\"https://doi.org/10.1007/978-3-642-22006-7_33\">https://doi.org/10.1007/978-3-642-22006-7_33</a>","ama":"Faust S, Pietrzak KZ, Venturi D. Tamper proof circuits How to trade leakage for tamper resilience. In: Vol 6755. Springer; 2011:391-402. doi:<a href=\"https://doi.org/10.1007/978-3-642-22006-7_33\">10.1007/978-3-642-22006-7_33</a>","ieee":"S. Faust, K. Z. Pietrzak, and D. Venturi, “Tamper proof circuits How to trade leakage for tamper resilience,” presented at the ICALP: Automata, Languages and Programming, 2011, vol. 6755, no. Part 1, pp. 391–402.","mla":"Faust, Sebastian, et al. <i>Tamper Proof Circuits How to Trade Leakage for Tamper Resilience</i>. Vol. 6755, no. Part 1, Springer, 2011, pp. 391–402, doi:<a href=\"https://doi.org/10.1007/978-3-642-22006-7_33\">10.1007/978-3-642-22006-7_33</a>.","short":"S. Faust, K.Z. Pietrzak, D. Venturi, in:, Springer, 2011, pp. 391–402."},"volume":"6755 ","year":"2011","month":"01","type":"conference","abstract":[{"lang":"eng","text":"Tampering attacks are cryptanalytic attacks on the implementation of cryptographic algorithms (e.g., smart cards), where an adversary introduces faults with the hope that the tampered device will reveal secret information. Inspired by the work of Ishai et al. [Eurocrypt'06], we propose a compiler that transforms any circuit into a new circuit with the same functionality, but which is resilient against a well-defined and powerful tampering adversary. More concretely, our transformed circuits remain secure even if the adversary can adaptively tamper with every wire in the circuit as long as the tampering fails with some probability δ&gt;0. This additional requirement is motivated by practical tampering attacks, where it is often difficult to guarantee the success of a specific attack. Formally, we show that a q-query tampering attack against the transformed circuit can be &quot;simulated&quot; with only black-box access to the original circuit and log(q) bits of additional auxiliary information. Thus, if the implemented cryptographic scheme is secure against log(q) bits of leakage, then our implementation is tamper-proof in the above sense. Surprisingly, allowing for this small amount of information leakage allows for much more efficient compilers, which moreover do not require randomness during evaluation. Similar to earlier works our compiler requires small, stateless and computation-independent tamper-proof gadgets. Thus, our result can be interpreted as reducing the problem of shielding arbitrary complex computation to protecting simple components. © 2011 Springer-Verlag."}],"day":"01","page":"391 - 402","title":"Tamper proof circuits How to trade leakage for tamper resilience","conference":{"name":"ICALP: Automata, Languages and Programming"},"status":"public","date_updated":"2021-01-12T07:42:02Z","issue":"Part 1","date_created":"2018-12-11T12:02:12Z","date_published":"2011-01-01T00:00:00Z"},{"month":"01","type":"conference","volume":6841,"year":"2011","citation":{"mla":"Barak, Boaz, et al. <i>Leftover Hash Lemma Revisited</i>. Vol. 6841, Springer, 2011, pp. 1–20, doi:<a href=\"https://doi.org/ 10.1007/978-3-642-22792-9_1\"> 10.1007/978-3-642-22792-9_1</a>.","ieee":"B. Barak <i>et al.</i>, “Leftover hash lemma revisited,” presented at the CRYPTO: International Cryptology Conference, 2011, vol. 6841, pp. 1–20.","short":"B. Barak, Y. Dodis, H. Krawczyk, O. Pereira, K.Z. Pietrzak, F. Standaert, Y. Yu, in:, Springer, 2011, pp. 1–20.","ama":"Barak B, Dodis Y, Krawczyk H, et al. Leftover hash lemma revisited. In: Vol 6841. Springer; 2011:1-20. doi:<a href=\"https://doi.org/ 10.1007/978-3-642-22792-9_1\"> 10.1007/978-3-642-22792-9_1</a>","apa":"Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K. Z., Standaert, F., &#38; Yu, Y. (2011). Leftover hash lemma revisited (Vol. 6841, pp. 1–20). Presented at the CRYPTO: International Cryptology Conference, Springer. <a href=\"https://doi.org/ 10.1007/978-3-642-22792-9_1\">https://doi.org/ 10.1007/978-3-642-22792-9_1</a>","chicago":"Barak, Boaz, Yevgeniy Dodis, Hugo Krawczyk, Olivier Pereira, Krzysztof Z Pietrzak, François Standaert, and Yu Yu. “Leftover Hash Lemma Revisited,” 6841:1–20. Springer, 2011. <a href=\"https://doi.org/ 10.1007/978-3-642-22792-9_1\">https://doi.org/ 10.1007/978-3-642-22792-9_1</a>.","ista":"Barak B, Dodis Y, Krawczyk H, Pereira O, Pietrzak KZ, Standaert F, Yu Y. 2011. Leftover hash lemma revisited. CRYPTO: International Cryptology Conference, LNCS, vol. 6841, 1–20."},"date_created":"2018-12-11T12:02:12Z","date_published":"2011-01-01T00:00:00Z","date_updated":"2021-01-12T07:42:03Z","status":"public","page":"1 - 20","conference":{"name":"CRYPTO: International Cryptology Conference"},"title":"Leftover hash lemma revisited","abstract":[{"text":"The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short &quot;input seed&quot; S into a longer &quot;output seed&quot; S′, and then use the resulting S′ as the seed required by the LHL (or, more generally, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a &quot;small&quot; (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract approach is likely secure when used with &quot;practical&quot; PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research.","lang":"eng"}],"day":"01","quality_controlled":0,"_id":"3240","extern":1,"intvolume":"      6841","author":[{"full_name":"Barak,  Boaz","first_name":"Boaz","last_name":"Barak"},{"first_name":"Yevgeniy","last_name":"Dodis","full_name":"Dodis, Yevgeniy"},{"first_name":"Hugo","last_name":"Krawczyk","full_name":"Krawczyk, Hugo"},{"last_name":"Pereira","first_name":"Olivier","full_name":"Pereira, Olivier"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Krzysztof Pietrzak","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"last_name":"Standaert","first_name":"François","full_name":"Standaert, François-Xavier"},{"first_name":"Yu","last_name":"Yu","full_name":"Yu, Yu"}],"publication_status":"published","publisher":"Springer","alternative_title":["LNCS"],"publist_id":"3440","doi":" 10.1007/978-3-642-22792-9_1"},{"oa_version":"None","citation":{"chicago":"Gupta, Ashutosh, Corneliu Popeea, and Andrey Rybalchenko. “Solving Recursion-Free Horn Clauses over LI+UIF.” edited by Hongseok Yang, 7078:188–203. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">https://doi.org/10.1007/978-3-642-25318-8_16</a>.","ista":"Gupta A, Popeea C, Rybalchenko A. 2011. Solving recursion-free Horn clauses over LI+UIF. APLAS: Asian Symposium on Programming Languages and Systems, LNCS, vol. 7078, 188–203.","mla":"Gupta, Ashutosh, et al. <i>Solving Recursion-Free Horn Clauses over LI+UIF</i>. Edited by Hongseok Yang, vol. 7078, Springer, 2011, pp. 188–203, doi:<a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">10.1007/978-3-642-25318-8_16</a>.","ieee":"A. Gupta, C. Popeea, and A. Rybalchenko, “Solving recursion-free Horn clauses over LI+UIF,” presented at the APLAS: Asian Symposium on Programming Languages and Systems, Kenting, Taiwan, 2011, vol. 7078, pp. 188–203.","short":"A. Gupta, C. Popeea, A. Rybalchenko, in:, H. Yang (Ed.), Springer, 2011, pp. 188–203.","ama":"Gupta A, Popeea C, Rybalchenko A. Solving recursion-free Horn clauses over LI+UIF. In: Yang H, ed. Vol 7078. Springer; 2011:188-203. doi:<a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">10.1007/978-3-642-25318-8_16</a>","apa":"Gupta, A., Popeea, C., &#38; Rybalchenko, A. (2011). Solving recursion-free Horn clauses over LI+UIF. In H. Yang (Ed.) (Vol. 7078, pp. 188–203). Presented at the APLAS: Asian Symposium on Programming Languages and Systems, Kenting, Taiwan: Springer. <a href=\"https://doi.org/10.1007/978-3-642-25318-8_16\">https://doi.org/10.1007/978-3-642-25318-8_16</a>"},"language":[{"iso":"eng"}],"month":"12","type":"conference","volume":7078,"year":"2011","page":"188 - 203","conference":{"start_date":"2011-12-05","location":"Kenting, Taiwan","end_date":"2011-12-07","name":"APLAS: Asian Symposium on Programming Languages and Systems"},"title":"Solving recursion-free Horn clauses over LI+UIF","abstract":[{"text":"Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms.","lang":"eng"}],"day":"05","date_created":"2018-12-11T12:02:20Z","date_published":"2011-12-05T00:00:00Z","editor":[{"first_name":"Hongseok","last_name":"Yang","full_name":"Yang, Hongseok"}],"date_updated":"2021-01-12T07:42:15Z","status":"public","quality_controlled":"1","_id":"3264","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","intvolume":"      7078","project":[{"call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"publisher":"Springer","alternative_title":["LNCS"],"ec_funded":1,"publist_id":"3383","doi":"10.1007/978-3-642-25318-8_16","publication_status":"published","author":[{"first_name":"Ashutosh","last_name":"Gupta","full_name":"Gupta, Ashutosh","id":"335E5684-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Popeea, Corneliu","last_name":"Popeea","first_name":"Corneliu"},{"full_name":"Rybalchenko, Andrey","last_name":"Rybalchenko","first_name":"Andrey"}],"department":[{"_id":"ToHe"}]},{"publisher":"Neural Information Processing Systems Foundation","publist_id":"3381","author":[{"first_name":"Adrian","last_name":"Ion","full_name":"Ion, Adrian","id":"29F89302-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Carreira","first_name":"Joao","full_name":"Carreira, Joao"},{"first_name":"Cristian","last_name":"Sminchisescu","full_name":"Sminchisescu, Cristian"}],"publication_status":"published","department":[{"_id":"HeEd"}],"quality_controlled":"1","_id":"3266","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"        24","page":"1827 - 1835","publication":"NIPS Proceedings","conference":{"name":"NIPS: Neural Information Processing Systems","end_date":"2011-12-14","start_date":"2011-12-12","location":"Granada, Spain"},"title":"Probabilistic joint image segmentation and labeling","abstract":[{"text":"We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved.","lang":"eng"}],"day":"01","date_created":"2018-12-11T12:02:21Z","date_published":"2011-12-01T00:00:00Z","status":"public","date_updated":"2021-01-12T07:42:15Z","oa_version":"None","citation":{"chicago":"Ion, Adrian, Joao Carreira, and Cristian Sminchisescu. “Probabilistic Joint Image Segmentation and Labeling.” In <i>NIPS Proceedings</i>, 24:1827–35. Neural Information Processing Systems Foundation, 2011.","ista":"Ion A, Carreira J, Sminchisescu C. 2011. Probabilistic joint image segmentation and labeling. NIPS Proceedings. NIPS: Neural Information Processing Systems vol. 24, 1827–1835.","short":"A. Ion, J. Carreira, C. Sminchisescu, in:, NIPS Proceedings, Neural Information Processing Systems Foundation, 2011, pp. 1827–1835.","ieee":"A. Ion, J. Carreira, and C. Sminchisescu, “Probabilistic joint image segmentation and labeling,” in <i>NIPS Proceedings</i>, Granada, Spain, 2011, vol. 24, pp. 1827–1835.","mla":"Ion, Adrian, et al. “Probabilistic Joint Image Segmentation and Labeling.” <i>NIPS Proceedings</i>, vol. 24, Neural Information Processing Systems Foundation, 2011, pp. 1827–35.","ama":"Ion A, Carreira J, Sminchisescu C. Probabilistic joint image segmentation and labeling. In: <i>NIPS Proceedings</i>. Vol 24. Neural Information Processing Systems Foundation; 2011:1827-1835.","apa":"Ion, A., Carreira, J., &#38; Sminchisescu, C. (2011). Probabilistic joint image segmentation and labeling. In <i>NIPS Proceedings</i> (Vol. 24, pp. 1827–1835). Granada, Spain: Neural Information Processing Systems Foundation."},"language":[{"iso":"eng"}],"month":"12","type":"conference","year":"2011","volume":24,"scopus_import":1},{"author":[{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen"},{"last_name":"Freedman","first_name":"Daniel","full_name":"Freedman, Daniel"}],"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer","doi":"10.1007/s00454-010-9322-8","publist_id":"3379","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","_id":"3267","intvolume":"        45","date_published":"2011-01-14T00:00:00Z","date_created":"2018-12-11T12:02:21Z","issue":"3","date_updated":"2023-02-21T16:07:10Z","status":"public","related_material":{"record":[{"relation":"earlier_version","id":"10909","status":"public"}]},"publication":"Discrete & Computational Geometry","title":"Hardness results for homology localization","page":"425 - 448","day":"14","abstract":[{"lang":"eng","text":"We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field."}],"type":"journal_article","month":"01","scopus_import":1,"year":"2011","volume":45,"oa_version":"None","citation":{"short":"C. Chen, D. Freedman, Discrete &#38; Computational Geometry 45 (2011) 425–448.","ieee":"C. Chen and D. Freedman, “Hardness results for homology localization,” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3. Springer, pp. 425–448, 2011.","mla":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>, vol. 45, no. 3, Springer, 2011, pp. 425–48, doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>.","apa":"Chen, C., &#38; Freedman, D. (2011). Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>","ama":"Chen C, Freedman D. Hardness results for homology localization. <i>Discrete &#38; Computational Geometry</i>. 2011;45(3):425-448. doi:<a href=\"https://doi.org/10.1007/s00454-010-9322-8\">10.1007/s00454-010-9322-8</a>","chicago":"Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2011. <a href=\"https://doi.org/10.1007/s00454-010-9322-8\">https://doi.org/10.1007/s00454-010-9322-8</a>.","ista":"Chen C, Freedman D. 2011. Hardness results for homology localization. Discrete &#38; Computational Geometry. 45(3), 425–448."},"language":[{"iso":"eng"}]},{"language":[{"iso":"eng"}],"oa_version":"None","citation":{"apa":"Freedman, D., &#38; Chen, C. (2011). Algebraic topology for computer vision. In <i>Computer Vision</i> (pp. 239–268). Nova Science Publishers.","ama":"Freedman D, Chen C. Algebraic topology for computer vision. In: <i>Computer Vision</i>. Nova Science Publishers; 2011:239-268.","short":"D. Freedman, C. Chen, in:, Computer Vision, Nova Science Publishers, 2011, pp. 239–268.","ieee":"D. Freedman and C. Chen, “Algebraic topology for computer vision,” in <i>Computer Vision</i>, Nova Science Publishers, 2011, pp. 239–268.","mla":"Freedman, Daniel, and Chao Chen. “Algebraic Topology for Computer Vision.” <i>Computer Vision</i>, Nova Science Publishers, 2011, pp. 239–68.","ista":"Freedman D, Chen C. 2011.Algebraic topology for computer vision. In: Computer Vision. Computer Science, Technology and Applications, , 239–268.","chicago":"Freedman, Daniel, and Chao Chen. “Algebraic Topology for Computer Vision.” In <i>Computer Vision</i>, 239–68. Nova Science Publishers, 2011."},"year":"2011","type":"book_chapter","month":"11","day":"30","abstract":[{"lang":"eng","text":"Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field. "}],"publication":"Computer Vision","title":"Algebraic topology for computer vision","page":"239 - 268","date_updated":"2021-01-12T07:42:16Z","status":"public","date_published":"2011-11-30T00:00:00Z","main_file_link":[{"url":"http://www.hpl.hp.com/techreports/2009/HPL-2009-375.pdf"}],"date_created":"2018-12-11T12:02:22Z","extern":"1","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","_id":"3268","publist_id":"3378","alternative_title":["Computer Science, Technology and Applications"],"publisher":"Nova Science Publishers","author":[{"full_name":"Freedman, Daniel","first_name":"Daniel","last_name":"Freedman"},{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao","last_name":"Chen","first_name":"Chao"}],"publication_status":"published"},{"type":"journal_article","scopus_import":1,"year":"2011","volume":30,"oa_version":"Published Version","citation":{"ista":"Sheng Y, Cutler B, Chen C, Nasman J. 2011. Perceptual global illumination cancellation in complex projection environments. Computer Graphics Forum. 30(4), 1261–1268.","chicago":"Sheng, Yu, Barbara Cutler, Chao Chen, and Joshua Nasman. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>. Wiley-Blackwell, 2011. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>.","ama":"Sheng Y, Cutler B, Chen C, Nasman J. Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. 2011;30(4):1261-1268. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>","apa":"Sheng, Y., Cutler, B., Chen, C., &#38; Nasman, J. (2011). Perceptual global illumination cancellation in complex projection environments. <i>Computer Graphics Forum</i>. Wiley-Blackwell. <a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">https://doi.org/10.1111/j.1467-8659.2011.01985.x</a>","mla":"Sheng, Yu, et al. “Perceptual Global Illumination Cancellation in Complex Projection Environments.” <i>Computer Graphics Forum</i>, vol. 30, no. 4, Wiley-Blackwell, 2011, pp. 1261–68, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2011.01985.x\">10.1111/j.1467-8659.2011.01985.x</a>.","ieee":"Y. Sheng, B. Cutler, C. Chen, and J. Nasman, “Perceptual global illumination cancellation in complex projection environments,” <i>Computer Graphics Forum</i>, vol. 30, no. 4. Wiley-Blackwell, pp. 1261–1268, 2011.","short":"Y. Sheng, B. Cutler, C. Chen, J. Nasman, Computer Graphics Forum 30 (2011) 1261–1268."},"main_file_link":[{"open_access":"1","url":"http://www.cs.cmu.edu/%7Eshengyu/download/egsr2011_paper.pdf"}],"date_published":"2011-07-19T00:00:00Z","issue":"4","date_updated":"2021-01-12T07:42:16Z","title":"Perceptual global illumination cancellation in complex projection environments","abstract":[{"lang":"eng","text":"The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"3269","publication_status":"published","author":[{"full_name":"Sheng, Yu","last_name":"Sheng","first_name":"Yu"},{"full_name":"Cutler, Barbara","first_name":"Barbara","last_name":"Cutler"},{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen"},{"full_name":"Nasman, Joshua","first_name":"Joshua","last_name":"Nasman"}],"department":[{"_id":"HeEd"}],"publisher":"Wiley-Blackwell","doi":"10.1111/j.1467-8659.2011.01985.x","month":"07","article_type":"original","language":[{"iso":"eng"}],"date_created":"2018-12-11T12:02:22Z","status":"public","publication":"Computer Graphics Forum","page":"1261 - 1268","day":"19","quality_controlled":"1","article_processing_charge":"No","intvolume":"        30","oa":1,"publist_id":"3377"},{"type":"conference","month":"01","year":"2011","citation":{"mla":"Chen, Chao, and Michael Kerber. <i>Persistent Homology Computation with a Twist</i>. TU Dortmund, 2011, pp. 197–200.","ieee":"C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland, 2011, pp. 197–200.","short":"C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.","apa":"Chen, C., &#38; Kerber, M. (2011). Persistent homology computation with a twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland: TU Dortmund.","ama":"Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200.","chicago":"Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.","ista":"Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry, 197–200."},"oa_version":"None","language":[{"iso":"eng"}],"date_published":"2011-01-01T00:00:00Z","date_created":"2018-12-11T12:02:22Z","date_updated":"2021-01-12T07:42:17Z","status":"public","conference":{"name":"EuroCG: European Workshop on Computational Geometry","end_date":"2011-03-30","start_date":"2011-03-28","location":"Morschach, Switzerland"},"title":"Persistent homology computation with a twist","page":"197 - 200","day":"01","abstract":[{"lang":"eng","text":"The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions."}],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","_id":"3270","author":[{"last_name":"Chen","first_name":"Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","full_name":"Chen, Chao"},{"id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael"}],"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"TU Dortmund","publist_id":"3376"},{"year":"2011","scopus_import":1,"month":"11","type":"book_chapter","language":[{"iso":"eng"}],"oa_version":"None","citation":{"apa":"Wagner, H., Chen, C., &#38; Vuçini, E. (2011). Efficient computation of persistent homology for cubical data. In R. Peikert, H. Hauser, H. Carr, &#38; R. Fuchs (Eds.), <i>Topological Methods in Data Analysis and Visualization II</i> (pp. 91–106). Springer. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>","ama":"Wagner H, Chen C, Vuçini E. Efficient computation of persistent homology for cubical data. In: Peikert R, Hauser H, Carr H, Fuchs R, eds. <i>Topological Methods in Data Analysis and Visualization II</i>. Springer; 2011:91-106. doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>","ieee":"H. Wagner, C. Chen, and E. Vuçini, “Efficient computation of persistent homology for cubical data,” in <i>Topological Methods in Data Analysis and Visualization II</i>, R. Peikert, H. Hauser, H. Carr, and R. Fuchs, Eds. Springer, 2011, pp. 91–106.","mla":"Wagner, Hubert, et al. “Efficient Computation of Persistent Homology for Cubical Data.” <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert et al., Springer, 2011, pp. 91–106, doi:<a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">10.1007/978-3-642-23175-9_7</a>.","short":"H. Wagner, C. Chen, E. Vuçini, in:, R. Peikert, H. Hauser, H. Carr, R. Fuchs (Eds.), Topological Methods in Data Analysis and Visualization II, Springer, 2011, pp. 91–106.","ista":"Wagner H, Chen C, Vuçini E. 2011.Efficient computation of persistent homology for cubical data. In: Topological Methods in Data Analysis and Visualization II. Theory, Algorithms, and Applications, , 91–106.","chicago":"Wagner, Hubert, Chao Chen, and Erald Vuçini. “Efficient Computation of Persistent Homology for Cubical Data.” In <i>Topological Methods in Data Analysis and Visualization II</i>, edited by Ronald Peikert, Helwig Hauser, Hamish Carr, and Raphael Fuchs, 91–106. Springer, 2011. <a href=\"https://doi.org/10.1007/978-3-642-23175-9_7\">https://doi.org/10.1007/978-3-642-23175-9_7</a>."},"date_updated":"2021-01-12T07:42:18Z","status":"public","date_created":"2018-12-11T12:02:23Z","editor":[{"first_name":"Ronald","last_name":"Peikert","full_name":"Peikert, Ronald"},{"first_name":"Helwig","last_name":"Hauser","full_name":"Hauser, Helwig"},{"full_name":"Carr, Hamish","last_name":"Carr","first_name":"Hamish"},{"first_name":"Raphael","last_name":"Fuchs","full_name":"Fuchs, Raphael"}],"date_published":"2011-11-14T00:00:00Z","abstract":[{"lang":"eng","text":"In this paper we present an efficient framework for computation of persis- tent homology of cubical data in arbitrary dimensions. An existing algorithm using simplicial complexes is adapted to the setting of cubical complexes. The proposed approach enables efficient application of persistent homology in domains where the data is naturally given in a cubical form. By avoiding triangulation of the data, we significantly reduce the size of the complex. We also present a data-structure de- signed to compactly store and quickly manipulate cubical complexes. By means of numerical experiments, we show high speed and memory efficiency of our ap- proach. We compare our framework to other available implementations, showing its superiority. Finally, we report performance on selected 3D and 4D data-sets."}],"day":"14","page":"91 - 106","title":"Efficient computation of persistent homology for cubical data","publication":"Topological Methods in Data Analysis and Visualization II","quality_controlled":"1","_id":"3271","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"publication_status":"published","author":[{"last_name":"Wagner","first_name":"Hubert","full_name":"Wagner, Hubert"},{"first_name":"Chao","last_name":"Chen","full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Erald","last_name":"Vuçini","full_name":"Vuçini, Erald"}],"publist_id":"3375","doi":"10.1007/978-3-642-23175-9_7","publisher":"Springer","alternative_title":["Theory, Algorithms, and Applications"]}]