@misc{5377, abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.}, author = {Chatterjee, Krishnendu and Velner, Yaron}, issn = {2664-1690}, pages = {33}, publisher = {IST Austria}, title = {{Mean-payoff pushdown games}}, doi = {10.15479/AT:IST-2012-0002}, year = {2012}, } @misc{5378, abstract = {One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.}, author = {Chatterjee, Krishnendu and Chaubal, Siddhesh and Kamath, Pritish}, issn = {2664-1690}, pages = {21}, publisher = {IST Austria}, title = {{Faster algorithms for alternating refinement relations}}, doi = {10.15479/AT:IST-2012-0001}, year = {2012}, } @misc{5396, abstract = {We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.}, author = {Korc, Filip and Kolmogorov, Vladimir and Lampert, Christoph}, issn = {2664-1690}, pages = {13}, publisher = {IST Austria}, title = {{Approximating marginals using discrete energy minimization}}, doi = {10.15479/AT:IST-2012-0003}, year = {2012}, } @techreport{5398, abstract = {This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers.}, author = {Porsche, Jana}, publisher = {IST Austria}, title = {{Actual state of research data @ ISTAustria}}, year = {2012}, } @inbook{5745, author = {Gupta, Ashutosh}, booktitle = {Automated Technology for Verification and Analysis}, isbn = {9783642333859}, issn = {1611-3349}, location = {Thiruvananthapuram, Kerala, India}, pages = {107--121}, publisher = {Springer Berlin Heidelberg}, title = {{Improved Single Pass Algorithms for Resolution Proof Reduction}}, doi = {10.1007/978-3-642-33386-6_10}, volume = {7561}, year = {2012}, } @article{6588, abstract = {First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.}, author = {Pausinger, Florian}, issn = {1812-9471}, journal = {Journal of Mathematical Physics, Analysis, Geometry}, number = {1}, pages = {63--78}, publisher = {B. Verkin Institute for Low Temperature Physics and Engineering}, title = {{Elementary solutions of the Bernstein problem on two intervals}}, volume = {8}, year = {2012}, } @misc{13075, abstract = {Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, C. semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and - using triplet alignments of intronic loci - quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times.}, author = {Lohse, Konrad and Barton, Nicholas H and Stone, Graham and Melika, George}, publisher = {Dryad}, title = {{Data from: A likelihood-based comparison of population histories in a parasitoid guild}}, doi = {10.5061/DRYAD.0G0FS}, year = {2012}, } @inproceedings{1384, abstract = {Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition Ψ - usually a state predicate - such that the program satisfies the specification under the condition Ψ - that is, as long as the program does not leave the states in which Ψ is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.}, author = {Beyer, Dirk and Henzinger, Thomas A and Keremoglu, Mehmet and Wendler, Philipp}, booktitle = {Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering}, location = {Cary, NC, USA}, publisher = {ACM}, title = {{Conditional model checking: A technique to pass information between verifiers}}, doi = {10.1145/2393596.2393664}, year = {2012}, } @article{9451, abstract = {The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations.}, author = {Ibarra, Christian A. and Feng, Xiaoqi and Schoft, Vera K. and Hsieh, Tzung-Fu and Uzawa, Rie and Rodrigues, Jessica A. and Zemach, Assaf and Chumak, Nina and Machlicova, Adriana and Nishimura, Toshiro and Rojas, Denisse and Fischer, Robert L. and Tamaru, Hisashi and Zilberman, Daniel}, issn = {1095-9203}, journal = {Science}, number = {6100}, pages = {1360--1364}, publisher = {American Association for the Advancement of Science}, title = {{Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes}}, doi = {10.1126/science.1224839}, volume = {337}, year = {2012}, } @article{9497, abstract = {The regulation of eukaryotic chromatin relies on interactions between many epigenetic factors, including histone modifications, DNA methylation, and the incorporation of histone variants. H2A.Z, one of the most conserved but enigmatic histone variants that is enriched at the transcriptional start sites of genes, has been implicated in a variety of chromosomal processes. Recently, we reported a genome-wide anticorrelation between H2A.Z and DNA methylation, an epigenetic hallmark of heterochromatin that has also been found in the bodies of active genes in plants and animals. Here, we investigate the basis of this anticorrelation using a novel h2a.z loss-of-function line in Arabidopsis thaliana. Through genome-wide bisulfite sequencing, we demonstrate that loss of H2A.Z in Arabidopsis has only a minor effect on the level or profile of DNA methylation in genes, and we propose that the global anticorrelation between DNA methylation and H2A.Z is primarily caused by the exclusion of H2A.Z from methylated DNA. RNA sequencing and genomic mapping of H2A.Z show that H2A.Z enrichment across gene bodies, rather than at the TSS, is correlated with lower transcription levels and higher measures of gene responsiveness. Loss of H2A.Z causes misregulation of many genes that are disproportionately associated with response to environmental and developmental stimuli. We propose that H2A.Z deposition in gene bodies promotes variability in levels and patterns of gene expression, and that a major function of genic DNA methylation is to exclude H2A.Z from constitutively expressed genes.}, author = {Coleman-Derr, Devin and Zilberman, Daniel}, issn = {1553-7404}, journal = {PLoS Genetics}, number = {10}, publisher = {Public Library of Science}, title = {{Deposition of histone variant H2A.Z within gene bodies regulates responsive genes}}, doi = {10.1371/journal.pgen.1002988}, volume = {8}, year = {2012}, } @article{9499, abstract = {EMBRYONIC FLOWER1 (EMF1) is a plant-specific gene crucial to Arabidopsis vegetative development. Loss of function mutants in the EMF1 gene mimic the phenotype caused by mutations in Polycomb Group protein (PcG) genes, which encode epigenetic repressors that regulate many aspects of eukaryotic development. In Arabidopsis, Polycomb Repressor Complex 2 (PRC2), made of PcG proteins, catalyzes trimethylation of lysine 27 on histone H3 (H3K27me3) and PRC1-like proteins catalyze H2AK119 ubiquitination. Despite functional similarity to PcG proteins, EMF1 lacks sequence homology with known PcG proteins; thus, its role in the PcG mechanism is unclear. To study the EMF1 functions and its mechanism of action, we performed genome-wide mapping of EMF1 binding and H3K27me3 modification sites in Arabidopsis seedlings. The EMF1 binding pattern is similar to that of H3K27me3 modification on the chromosomal and genic level. ChIPOTLe peak finding and clustering analyses both show that the highly trimethylated genes also have high enrichment levels of EMF1 binding, termed EMF1_K27 genes. EMF1 interacts with regulatory genes, which are silenced to allow vegetative growth, and with genes specifying cell fates during growth and differentiation. H3K27me3 marks not only these genes but also some genes that are involved in endosperm development and maternal effects. Transcriptome analysis, coupled with the H3K27me3 pattern, of EMF1_K27 genes in emf1 and PRC2 mutants showed that EMF1 represses gene activities via diverse mechanisms and plays a novel role in the PcG mechanism.}, author = {Kim, Sang Yeol and Lee, Jungeun and Eshed-Williams, Leor and Zilberman, Daniel and Sung, Z. Renee}, issn = {1553-7404}, journal = {PLoS Genetics}, number = {3}, publisher = {Public Library of Science}, title = {{EMF1 and PRC2 cooperate to repress key regulators of Arabidopsis development}}, doi = {10.1371/journal.pgen.1002512}, volume = {8}, year = {2012}, } @article{9528, abstract = {Accumulating evidence points toward diverse functions for plant chromatin. Remarkable progress has been made over the last few years in elucidating the mechanisms for a number of these functions. Activity of the histone demethylase IBM1 accurately targets DNA methylation to silent repeats and transposable elements, not to genes. A genetic screen uncovered the surprising role of H2A.Z-containing nucleosomes in sensing precise differences in ambient temperature and consequent gene regulation. Precise maintenance of chromosome number is assured by a histone modification that suppresses inappropriate DNA replication and by centromeric histone H3 regulation of chromosome segregation. Histones and noncoding RNAs regulate FLOWERING LOCUS C, the expression of which quantitatively measures the duration of cold exposure, functioning as memory of winter. These findings are a testament to the power of using plants to research chromatin organization, and demonstrate examples of how chromatin functions to achieve biological accuracy, precision, and memory.}, author = {Huff, Jason T. and Zilberman, Daniel}, issn = {0959-437X}, journal = {Current Opinion in Genetics and Development}, number = {2}, pages = {132--138}, publisher = {Elsevier}, title = {{Regulation of biological accuracy, precision, and memory by plant chromatin organization}}, doi = {10.1016/j.gde.2012.01.007}, volume = {22}, year = {2012}, } @article{9535, abstract = {The most well-studied function of DNA methylation in eukaryotic cells is the transcriptional silencing of genes and transposons. More recent results showed that many eukaryotes methylate the bodies of genes as well and that this methylation correlates with transcriptional activity rather than repression. The purpose of gene body methylation remains mysterious, but is potentially related to the histone variant H2A.Z. Studies in plants and animals have shown that the genome-wide distributions of H2A.Z and DNA methylation are strikingly anticorrelated. Furthermore, we and other investigators have shown that this relationship is likely to be the result of an ancient but unknown mechanism by which DNA methylation prevents the incorporation of H2A.Z. Recently, we discovered strong correlations between the presence of H2A.Z within gene bodies, the degree to which a gene's expression varies across tissue types or environmental conditions, and transcriptional misregulation in an h2a.z mutant. We propose that one basal function of gene body methylation is the establishment of constitutive expression patterns within housekeeping genes by excluding H2A.Z from their bodies.}, author = {Coleman-Derr, D. and Zilberman, Daniel}, issn = {1943-4456}, journal = {Cold Spring Harbor Symposia on Quantitative Biology}, pages = {147--154}, publisher = {Cold Spring Harbor Laboratory Press}, title = {{DNA methylation, H2A.Z, and the regulation of constitutive expression}}, doi = {10.1101/sqb.2012.77.014944}, volume = {77}, year = {2012}, } @article{12198, abstract = {The Arabidopsis thaliana central cell, the companion cell of the egg, undergoes DNA demethylation before fertilization, but the targeting preferences, mechanism, and biological significance of this process remain unclear. Here, we show that active DNA demethylation mediated by the DEMETER DNA glycosylase accounts for all of the demethylation in the central cell and preferentially targets small, AT-rich, and nucleosome-depleted euchromatic transposable elements. The vegetative cell, the companion cell of sperm, also undergoes DEMETER-dependent demethylation of similar sequences, and lack of DEMETER in vegetative cells causes reduced small RNA–directed DNA methylation of transposons in sperm. Our results demonstrate that demethylation in companion cells reinforces transposon methylation in plant gametes and likely contributes to stable silencing of transposable elements across generations.}, author = {Ibarra, Christian A. and Feng, Xiaoqi and Schoft, Vera K. and Hsieh, Tzung-Fu and Uzawa, Rie and Rodrigues, Jessica A. and Zemach, Assaf and Chumak, Nina and Machlicova, Adriana and Nishimura, Toshiro and Rojas, Denisse and Fischer, Robert L. and Tamaru, Hisashi and Zilberman, Daniel}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {6100}, pages = {1360--1364}, publisher = {American Association for the Advancement of Science}, title = {{Active DNA demethylation in plant companion cells reinforces transposon methylation in gametes}}, doi = {10.1126/science.1224839}, volume = {337}, year = {2012}, } @misc{9755, abstract = {Due to the omnipresent risk of epidemics, insect societies have evolved sophisticated disease defences at the individual and colony level. An intriguing yet little understood phenomenon is that social contact to pathogen-exposed individuals reduces susceptibility of previously naive nestmates to this pathogen. We tested whether such social immunisation in Lasius ants against the entomopathogenic fungus Metarhizium anisopliae is based on active upregulation of the immune system of nestmates following contact to an infectious individual or passive protection via transfer of immune effectors among group members—that is, active versus passive immunisation. We found no evidence for involvement of passive immunisation via transfer of antimicrobials among colony members. Instead, intensive allogrooming behaviour between naive and pathogen-exposed ants before fungal conidia firmly attached to their cuticle suggested passage of the pathogen from the exposed individuals to their nestmates. By tracing fluorescence-labelled conidia we indeed detected frequent pathogen transfer to the nestmates, where they caused low-level infections as revealed by growth of small numbers of fungal colony forming units from their dissected body content. These infections rarely led to death, but instead promoted an enhanced ability to inhibit fungal growth and an active upregulation of immune genes involved in antifungal defences (defensin and prophenoloxidase, PPO). Contrarily, there was no upregulation of the gene cathepsin L, which is associated with antibacterial and antiviral defences, and we found no increased antibacterial activity of nestmates of fungus-exposed ants. This indicates that social immunisation after fungal exposure is specific, similar to recent findings for individual-level immune priming in invertebrates. Epidemiological modeling further suggests that active social immunisation is adaptive, as it leads to faster elimination of the disease and lower death rates than passive immunisation. Interestingly, humans have also utilised the protective effect of low-level infections to fight smallpox by intentional transfer of low pathogen doses (“variolation” or “inoculation”).}, author = {Konrad, Matthias and Vyleta, Meghan and Theis, Fabian and Stock, Miriam and Klatt, Martina and Drescher, Verena and Marr, Carsten and Ugelvig, Line V and Cremer, Sylvia}, publisher = {Dryad}, title = {{Data from: Social transfer of pathogenic fungus promotes active immunisation in ant colonies}}, doi = {10.5061/dryad.sv37s}, year = {2012}, } @misc{9757, abstract = {To fight infectious diseases, host immune defences are employed at multiple levels. Sanitary behaviour, such as pathogen avoidance and removal, acts as a first line of defence to prevent infection [1] before activation of the physiological immune system. Insect societies have evolved a wide range of collective hygiene measures and intensive health care towards pathogen-exposed group members [2]. One of the most common behaviours is allogrooming, in which nestmates remove infectious particles from the body surfaces of exposed individuals [3]. Here we show that, in invasive garden ants, grooming of fungus-exposed brood is effective beyond the sheer mechanical removal of fungal conidiospores as it also includes chemical disinfection through the application of poison produced by the ants themselves. Formic acid is the main active component of the poison. It inhibits fungal growth of conidiospores remaining on the brood surface after grooming and also those collected in the mouth of the grooming ant. This dual function is achieved by uptake of the poison droplet into the mouth through acidopore self-grooming and subsequent application onto the infectious brood via brood grooming. This extraordinary behaviour extends current understanding of grooming and the establishment of social immunity in insect societies.}, author = {Tragust, Simon and Mitteregger, Barbara and Barone, Vanessa and Konrad, Matthias and Ugelvig, Line V and Cremer, Sylvia}, publisher = {Dryad}, title = {{Data from: Ants disinfect fungus-exposed brood by oral uptake and spread of their poison}}, doi = {10.5061/dryad.61649}, year = {2012}, } @misc{9758, abstract = {We propose a two-step procedure for estimating multiple migration rates in an approximate Bayesian computation (ABC) framework, accounting for global nuisance parameters. The approach is not limited to migration, but generally of interest for inference problems with multiple parameters and a modular structure (e.g. independent sets of demes or loci). We condition on a known, but complex demographic model of a spatially subdivided population, motivated by the reintroduction of Alpine ibex (Capra ibex) into Switzerland. In the first step, the global parameters ancestral mutation rate and male mating skew have been estimated for the whole population in Aeschbacher et al. (Genetics 2012; 192: 1027). In the second step, we estimate in this study the migration rates independently for clusters of demes putatively connected by migration. For large clusters (many migration rates), ABC faces the problem of too many summary statistics. We therefore assess by simulation if estimation per pair of demes is a valid alternative. We find that the trade-off between reduced dimensionality for the pairwise estimation on the one hand and lower accuracy due to the assumption of pairwise independence on the other depends on the number of migration rates to be inferred: the accuracy of the pairwise approach increases with the number of parameters, relative to the joint estimation approach. To distinguish between low and zero migration, we perform ABC-type model comparison between a model with migration and one without. Applying the approach to microsatellite data from Alpine ibex, we find no evidence for substantial gene flow via migration, except for one pair of demes in one direction.}, author = {Aeschbacher, Simon and Futschik, Andreas and Beaumont, Mark}, publisher = {Dryad}, title = {{Data from: Approximate Bayesian computation for modular inference problems with many parameters: the example of migration rates}}, doi = {10.5061/dryad.274b1}, year = {2012}, } @article{3836, abstract = {Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine (or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram structure needs to be flattened; the flattening makes separatecompilation difficult, and may result in E machinecode of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchicalprogram structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.}, author = {Ghosal, Arkadeb and Iercan, Daniel and Kirsch, Christoph and Henzinger, Thomas A and Sangiovanni Vincentelli, Alberto}, journal = {Science of Computer Programming}, number = {2}, pages = {96 -- 112}, publisher = {Elsevier}, title = {{Separate compilation of hierarchical real-time programs into linear-bounded embedded machine code}}, doi = {10.1016/j.scico.2010.06.004}, volume = {77}, year = {2012}, } @article{3846, abstract = {We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A}, journal = {Journal of Computer and System Sciences}, number = {2}, pages = {394 -- 413}, publisher = {Elsevier}, title = {{A survey of stochastic ω regular games}}, doi = {10.1016/j.jcss.2011.05.002}, volume = {78}, year = {2012}, } @inproceedings{3163, abstract = {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.}, author = {Lampert, Christoph}, location = {Granada, Spain}, publisher = {Neural Information Processing Systems}, title = {{Maximum margin multi-label structured prediction}}, year = {2011}, }