Polynomial threshold functions and Boolean threshold circuits

Kristoffer Arnsfelt Hansen; Vladimir V. Podolskii

doi:10.1007/978-3-642-40313-2_46

Polynomial threshold functions and Boolean threshold circuits

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:

9783642403132, 9783642403125

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

Polynomial threshold functions and Boolean threshold circuits

Full text access

On-site access

At institution

Metrics

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