Damm, Carsten

[["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.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","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"]]