{"controller"=>"catalog", "action"=>"show", "id"=>"250274106"}
  • EN
  • DA

Danish NationalResearch Database

  • Search Publications & Researchers
  • Open Access Indicator
  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the prase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Polynomial threshold functions and Boolean threshold circuits

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Hansen, Kristoffer Arnsfelt ;
    Close
    Department of Computer Science, Science and Technology, Aarhus University
  • Podolskii, Vladimir V.
    Close
    Steklov Mathematical Institute
Editor:
Chatterjee, Krishnendu, Sgall, JirĂ­
DOI:
10.1007/978-3-642-40313-2_46
Abstract:
We study the complexity of computing Boolean functions on general Boolean domains by polynomial threshold functions (PTFs). A typical example of a general Boolean domain is 12n . We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. We show that PTFs on general Boolean domains are tightly connected to depth two threshold circuits. Our main results in regard to this connection are: PTFs of polynomial length and polynomial degree compute exactly the functions computed by THRMAJ circuits. An exponential length lower bound for PTFs that holds regardless of degree, thereby extending known lower bounds for THRMAJ circuits. We generalize two-party unbounded error communication complexity to the multi-party number-on-the-forehead setting, and show that communication lower bounds for 3-player protocols would yield size lower bounds for THRTHR circuits. We obtain several other results about PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length. We also consider a variant of PTFs over the max-plus algebra. We show that they are connected to PTFs over general domains and to AC0THR circuits.
ISBN:
9783642403125, 9783642403132
Type:
Conference paper
Language:
English
Published in:
Lecture Notes in Computer Science: 38th International Symposium, Mfcs 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, 2013, p. 516-527
Keywords:
circuit complexity; Communication complexity; lower bounds; Polynomial threshold functions; threshold circuits
Main Research Area:
Science/technology
Publication Status:
Published
Series:
Lecture Notes in Computer Science
Review type:
Peer Review
Conference:
International Symposium Mathematical Foundations of Computer Science, 2013
Publisher:
Springer-VS
Submission year:
2013
Scientific Level:
Scientific
ID:
250274106

Full text access

  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institution

  • Aarhus university.en

Metrics

Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • Open Access
    • Overview
    • Development
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and privacy policy

Copyright © 1998–2018.

Fivu en