Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Some computational problems in linear algebra as hard as matrix multiplication (1991)
    Springer
    Computational complexity 1 (1991), S. 131-155 
    Details
    ISSN: 1420-8954
    Keywords: Problems ; computation trees ; straight line programs ; Ostrowski complexity ; derivations ; matrix multiplication ; 68C20 ; 68C25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are: KER n : Compute a basis of the kernel for a givenn×n-matrix, OGB n : Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form, SPR n : Find a sparse representation of a givenn×n-matrix.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01272518
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Randomization and the computational power of analytic and algebraic decision trees (1996)
    Springer
    Computational complexity 6 (1996), S. 376-388 
    Details
    ISSN: 1420-8954
    Keywords: Computational Complexity ; Randomization ; Decision Trees ; Boolean Functions ; Lower Bounds ; Octants ; MAX Problem ; 68Q15 ; 68Q25 ; 68Q40
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We introduce a new powerful method for provinglower bounds onrandomized anddeterministic analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design alsorandomized algebraic decision trees for recognizing thepositive octant in ℝ n or computing MAX in ℝ n in depth log O(1) n. Both problems are known to have linear lower bounds for the depth of any deterministic analytic decision tree recognizing them. The mainnew (andunifying) proof idea of the paper is in the reduction technique of the signs oftesting functions in a decision tree to the signs of theirleading terms at the specially chosen points. This allows us to reduce the complexity of adecision tree to the complexity of a certainBoolean circuit.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01270388
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    An algorithm to learn read-once threshold formulas, and transformations between learning models (1994)
    Springer
    Computational complexity 4 (1994), S. 37-61 
    Details
    ISSN: 1420-8954
    Keywords: read-once threshold formulas ; learning models ; transformations ; justifying assignments ; membership queries ; equivalence queries ; learning algorithms ; Subject classifications ; 68Q20 ; 68T05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01205054
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A lower bound for randomized algebraic decision trees (1996)
    Springer
    Computational complexity 6 (1996), S. 357-375 
    Details
    ISSN: 1420-8954
    Keywords: Computational Complexity ; Randomized Algebraic Decision Trees ; Knapsack ; Element Distinctness ; Integer Programming ; 68Q15 ; 68Q25 ; 68Q40
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n 2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)randomized lower bound for theElement Distinctness Problem which were previously known only for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary lower bound technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01270387
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Counting curves and their projections (1996)
    Springer
    Computational complexity 6 (1996), S. 64-99 
    Details
    ISSN: 1420-8954
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is #P-complete via probabilistic parsimonious Turing reductions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01202042
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    New Approximation Algorithms for the Steiner Tree Problems (1997)
    Springer
    Journal of combinatorial optimization 1 (1997), S. 47-65 
    Details
    ISSN: 1573-2886
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009758919736
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    On a New High Dimensional Weisfeiler-Lehman Algorithm (1999)
    Springer
    Journal of algebraic combinatorics 10 (1999), S. 29-45 
    Details
    ISSN: 1572-9192
    Keywords: graph isomorphism problem ; cellular algebra ; permutation group
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate the following problem: how different can a cellular algebra be from its Schurian closure, i.e., the centralizer algebra of its automorphism group? For this purpose we introduce the notion of a Schurian polynomial approximation scheme measuring this difference. Some natural examples of such schemes arise from high dimensional generalizations of the Weisfeiler-Lehman algorithm which constructs the cellular closure of a set of matrices. We prove that all of these schemes are dominated by a new Schurian polynomial approximation scheme defined by the m-closure operators. A sufficient condition for the m-closure of a cellular algebra to coincide with its Schurian closure is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1018672019177
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Book
    Book
    Fast parallel algorithms for graph matching problems; 9 (1998)
    Oxford :Clarendon Pr.,
    Details
    Title: Fast parallel algorithms for graph matching problems; 9
    Author: Karpinski, Marek
    Contributer: Rytter, Wojciech
    Publisher: Oxford :Clarendon Pr.,
    Year of publication: 1998
    Pages: 212 S.
    Series Statement: Oxford lecture series in mathematics and its applications 9
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...