ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
Filter
  • 1990-1994  (2)
Collection
Keywords
Publisher
Years
Year
  • 1
    Electronic Resource
    Electronic Resource
    On the degree of boolean functions as real polynomials (1994)
    Springer
    Computational complexity 4 (1994), S. 301-313 
    Details
    ISSN: 1420-8954
    Keywords: Approximation ; block sensitivity ; Boolean functions ; Fourier degree ; 68Q05 ; 68Q99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related: o The decision tree complexity off. o The degree of the polynomial representingf. o The smallest degree of a polynomialapproximating f in theL max norm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01263419
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On packing bipartite graphs (1992)
    Springer
    Combinatorica 12 (1992), S. 295-301 
    Details
    ISSN: 1439-6912
    Keywords: 05 C 70
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract G andH, two simple graphs, can be packed ifG is isomorphic to a subgraph of $$\overline H$$ , the complement ofH. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees ofG andH. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01285818
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...