Damm, Carsten

[["dc.bibliographiccitation.firstpage","223"],["dc.bibliographiccitation.issue","3"],["dc.bibliographiccitation.journal","Mathematical Systems Theory"],["dc.bibliographiccitation.lastpage","237"],["dc.bibliographiccitation.volume","25"],["dc.contributor.author","Buntrock, Gerhard"],["dc.contributor.author","Damm, Carsten"],["dc.contributor.author","Hertrampf, Ulrich"],["dc.contributor.author","Meinel, Christoph"],["dc.date.accessioned","2019-10-24T11:39:35Z"],["dc.date.available","2019-10-24T11:39:35Z"],["dc.date.issued","1992"],["dc.description.abstract","We refine the techniques of Beigelet al. [4] who investigated polynomial-time counting classes, in order to make them applicable to the case of logarithmic space. We define the complexity classes and demonstrate their significance by proving that all standard problems of linear algebra over the finite ringsZ/kZ are complete for these classes. We then define new complexity classes LogFew and LogFew and identify them as adequate logspace versions of Few and Few . We show that LogFew is contained in and that LogFew is contained in for allk. Also an upper bound for in terms of computation of integer determinants is given from which we conclude that all logspace counting classes are contained in ."],["dc.identifier.doi","10.1007/BF01374526"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/62526"],["dc.language.iso","en"],["dc.relation.issn","0025-5661"],["dc.relation.issn","1433-0490"],["dc.title","Structure and importance of logspace-MOD class"],["dc.type","journal_article"],["dc.type.internalPublication","no"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","113"],["dc.bibliographiccitation.issue","2"],["dc.bibliographiccitation.journal","Information and Computation"],["dc.bibliographiccitation.lastpage","124"],["dc.bibliographiccitation.volume","168"],["dc.contributor.author","Bernasconi, A."],["dc.contributor.author","Damm, C."],["dc.contributor.author","Shparlinski, I."],["dc.date.accessioned","2018-11-07T08:48:51Z"],["dc.date.available","2018-11-07T08:48:51Z"],["dc.date.issued","2001"],["dc.description.abstract","We extend the area of applications of the Abstract Harmonic Analysis to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In particular, we prove that deciding if a given integer is square-free and testing co-primality of two integers by unbounded fan-in circuits of bounded depth requires super-polynomial size. (C) 2001 Academic Press."],["dc.identifier.doi","10.1006/inco.2000.3017"],["dc.identifier.isi","000170174600002"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/21320"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Academic Press Inc"],["dc.relation.issn","0890-5401"],["dc.title","Circuit and decision tree complexity of some number theoretic problems"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.status","published"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.artnumber","142"],["dc.bibliographiccitation.journal","BMC Bioinformatics"],["dc.bibliographiccitation.volume","7"],["dc.contributor.author","Waack, Stephan"],["dc.contributor.author","Keller, Oliver"],["dc.contributor.author","Asper, Roman"],["dc.contributor.author","Brodag, Thomas"],["dc.contributor.author","Damm, Carsten"],["dc.contributor.author","Fricke, Wolfgang Florian"],["dc.contributor.author","Surovcik, Katharina"],["dc.contributor.author","Meinicke, Peter"],["dc.contributor.author","Merkl, Rainer"],["dc.date.accessioned","2018-11-07T10:05:47Z"],["dc.date.available","2018-11-07T10:05:47Z"],["dc.date.issued","2006"],["dc.description.abstract","Background: Horizontal gene transfer (HGT) is considered a strong evolutionary force shaping the content of microbial genomes in a substantial manner. It is the difference in speed enabling the rapid adaptation to changing environmental demands that distinguishes HGT from gene genesis, duplications or mutations. For a precise characterization, algorithms are needed that identify transfer events with high reliability. Frequently, the transferred pieces of DNA have a considerable length, comprise several genes and are called genomic islands (GIs) or more specifically pathogenicity or symbiotic islands. Results: We have implemented the program SIGI-HMM that predicts GIs and the putative donor of each individual alien gene. It is based on the analysis of codon usage (CU) of each individual gene of a genome under study. CU of each gene is compared against a carefully selected set of CU tables representing microbial donors or highly expressed genes. Multiple tests are used to identify putatively alien genes, to predict putative donors and to mask putatively highly expressed genes. Thus, we determine the states and emission probabilities of an inhomogeneous hidden Markov model working on gene level. For the transition probabilities, we draw upon classical test theory with the intention of integrating a sensitivity controller in a consistent manner. SIGI-HMM was written in JAVA and is publicly available. It accepts as input any file created according to the EMBL-format. It generates output in the common GFF format readable for genome browsers. Benchmark tests showed that the output of SIGI-HMM is in agreement with known findings. Its predictions were both consistent with annotated GIs and with predictions generated by different methods. Conclusion: SIGI-HMM is a sensitive tool for the identification of GIs in microbial genomes. It allows to interactively analyze genomes in detail and to generate or to test hypotheses about the origin of acquired genes."],["dc.identifier.doi","10.1186/1471-2105-7-142"],["dc.identifier.isi","000238903700001"],["dc.identifier.pmid","16542435"],["dc.identifier.purl","https://resolver.sub.uni-goettingen.de/purl?gs-1/12509"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/38969"],["dc.language.iso","en"],["dc.notes.intern","Merged from goescholar"],["dc.notes.status","final"],["dc.notes.submitter","Najko"],["dc.relation.issn","1471-2105"],["dc.rights","CC BY 2.0"],["dc.rights.uri","https://creativecommons.org/licenses/by/2.0/"],["dc.title","Score-based prediction of genomic islands in prokaryotic genomes using hidden Markov models"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dc.type.version","published_version"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","39"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Computational Complexity"],["dc.bibliographiccitation.lastpage","51"],["dc.bibliographiccitation.volume","9"],["dc.contributor.author","Bernasconi, A."],["dc.contributor.author","Damm, C."],["dc.contributor.author","Shparlinski, I."],["dc.date.accessioned","2018-11-07T11:02:43Z"],["dc.date.available","2018-11-07T11:02:43Z"],["dc.date.issued","2000"],["dc.description.abstract","We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain an asymptotic formula, having a linear main term, for the average sensitivity of the Boolean function deciding whether a given integer is square-free. This result allows us to derive a quadratic lower bound for the formula size complexity of testing square-free numbers and a linear lower bound on the average decision tree depth. We also obtain lower bounds on the degrees of exact and approximate polynomial representations of this function."],["dc.identifier.doi","10.1007/PL00001600"],["dc.identifier.isi","000166071000003"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/51454"],["dc.language.iso","en"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.relation.issn","1016-3328"],["dc.title","The average sensitivity of square-freeness"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","17"],["dc.bibliographiccitation.issue","1"],["dc.bibliographiccitation.journal","Information Processing Letters"],["dc.bibliographiccitation.lastpage","21"],["dc.bibliographiccitation.volume","102"],["dc.contributor.author","Brosenne, Henrik"],["dc.contributor.author","Damm, Carsten"],["dc.contributor.author","Homeister, Matthias"],["dc.contributor.author","Waack, Stephan"],["dc.date.accessioned","2018-11-07T11:03:11Z"],["dc.date.available","2018-11-07T11:03:11Z"],["dc.date.issued","2007"],["dc.description.abstract","We show that for every V-OBDD of quasipolynomial size there is a circle plus-OBDD of quasipolynornial size computing the same function up to a small fraction of the inputs. We also prove that the final step in the approximation cannot be improved and discuss possibilities of proving non-approximability results and connections to lower bounds on matrix rigidity. (c) 2006 Elsevier B.V. All rights reserved."],["dc.identifier.doi","10.1016/j.ipl.2006.10.011"],["dc.identifier.isi","000244631900003"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/51558"],["dc.language.iso","en"],["dc.notes.status","final"],["dc.notes.submitter","Najko"],["dc.relation.issn","0020-0190"],["dc.title","On approximation by circle plus-OBDDs"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","259"],["dc.bibliographiccitation.issue","2"],["dc.bibliographiccitation.journal","Journal of Computer and System Sciences"],["dc.bibliographiccitation.lastpage","280"],["dc.bibliographiccitation.volume","69"],["dc.contributor.author","Damm, Carsten"],["dc.contributor.author","Krause, M."],["dc.contributor.author","Meinel, C."],["dc.contributor.author","Waack, S."],["dc.date.accessioned","2018-11-07T10:46:00Z"],["dc.date.available","2018-11-07T10:46:00Z"],["dc.date.issued","2004"],["dc.description.abstract","We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established. This extends the investigation of the complexity of communication between two processors in terms of complexity classes initiated by Babai et al. (Proceedings of the 27th IEEE FOCS, 1986, pp. 337-347) and continued in several papers (e.g., J. Comput. System Sci. 41 (1990) 402; 49 (1994) 247; Proceedings of the 36th IEEE FOCS, 1995, pp. 6-15). In particular, it will be shown that for all pairs of distinct primes p and q the communication complexity classes MODpPcc and MODqPcc are incomparable with regard to inclusion. The same is true for PPcc and MODmPcc, for any number m greater than or equal to 2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if m = p(1)(l1.)...(.)p(r)(lr) is the prime decomposition of m greater than or equal to 2, then the complexity classes MODmPcc and MODrho(m)Pcc coincide, where rho(m) = p(1) (.)...(.) p(r). The results are obtained by characterizing the modular and probabilistic communication complexity in terms of the minimum rank of matrices ranging over certain equivalence classes. Methods from algebra and analytic geometry are used. This paper is the completely revised and strongly extended version of the conference paper Damm et al. (Proc. 9th Ann. STACS, pp. 281-291) where a subset of the results was presented. (C) 2004 Elsevier Inc. All rights reserved."],["dc.identifier.doi","10.1016/j.jcss.2004.03.002"],["dc.identifier.isi","000223292400007"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/47640"],["dc.language.iso","en"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.relation.issn","1090-2724"],["dc.relation.issn","0022-0000"],["dc.title","On relations between counting communication complexity classes"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","23"],["dc.bibliographiccitation.issue","1-2"],["dc.bibliographiccitation.journal","Computational Complexity"],["dc.bibliographiccitation.lastpage","47"],["dc.bibliographiccitation.volume","12"],["dc.contributor.author","Allender, E."],["dc.contributor.author","Bernasconi, A."],["dc.contributor.author","Damm, C."],["dc.contributor.author","von zur Gathen, J."],["dc.contributor.author","Saks, M."],["dc.contributor.author","Shparlinski, I."],["dc.date.accessioned","2018-11-07T10:38:28Z"],["dc.date.available","2018-11-07T10:38:28Z"],["dc.date.issued","2003"],["dc.description.abstract","We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over F-2. In particular, we consider the Boolean function deciding whether a given polynomial over F-2 is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that testing squarefreeness and irreducibility of polynomials over F-2 cannot be done in AC(0)[p] for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over F-2 as well."],["dc.identifier.doi","10.1007/s00037-003-0176-9"],["dc.identifier.isi","000220987300002"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/45822"],["dc.language.iso","en"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.relation.issn","1016-3328"],["dc.title","Complexity of some arithmetic problems for binary polynomials"],["dc.type","journal_article"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dspace.entity.type","Publication"]]

[["dc.bibliographiccitation.firstpage","54"],["dc.bibliographiccitation.issue","1-2"],["dc.bibliographiccitation.journal","Computational Complexity"],["dc.bibliographiccitation.lastpage","89"],["dc.bibliographiccitation.volume","11"],["dc.contributor.author","Damm, C."],["dc.contributor.author","Holzer, M."],["dc.contributor.author","McKenzie, P."],["dc.date.accessioned","2018-11-07T10:27:29Z"],["dc.date.available","2018-11-07T10:27:29Z"],["dc.date.issued","2002"],["dc.description.abstract","Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for circle plusP, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitz's theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts circle plusLOGCFL and circle plusL, and several other counting classes. Finally, the known inclusions NP/poly subset of or equal to circle plusP/poly, LOGCFL/poly subset of or equal to circle plusLOGCFL/poly, and NL/poly subset of or equal to circle plusL/poly, which have scattered proofs in the literature (Valiant Vazirani 1986; Gaal & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring S."],["dc.identifier.doi","10.1007/s00037-000-0170-4"],["dc.identifier.isi","000186494800002"],["dc.identifier.uri","https://resolver.sub.uni-goettingen.de/purl?gro-2/43239"],["dc.language.iso","en"],["dc.notes.status","zu prüfen"],["dc.notes.submitter","Najko"],["dc.publisher","Springer"],["dc.publisher.place","Basel"],["dc.relation.conference","15th Annual IEEE Conference on Computational Complexity"],["dc.relation.eventlocation","FLORENCE, ITALY"],["dc.relation.eventstart","2002"],["dc.relation.issn","1420-8954"],["dc.relation.issn","1016-3328"],["dc.title","Complexity of tensor calculus"],["dc.type","conference_paper"],["dc.type.internalPublication","yes"],["dc.type.peerReviewed","yes"],["dspace.entity.type","Publication"]]