Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed

Gil  Cohen; Ivan Bjerre Damgård; Yuval Ishai; Jonas Kölker; Peter Bro Miltersen; Ran  Raz; Ron   Rothblum

Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed

Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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.

Original language	English
Journal	Electronic Colloquium on Computational Complexity
Issue	TR13-107
Number of pages	56
ISSN	1433-8092
Publication status	Published - 2013

Keywords

circuit complexity
Communication complexity
lower bounds
Polynomial threshold functions
threshold circuits

Access to Document

http://eccc.hpi-web.de/report/2013/107/

Cite this

@article{1c1f7cc3cae14304ae5d1fab51113637,

title = "Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed",

abstract = "We study the complexity of computing Boolean functions on generalBoolean domains by polynomial threshold functions (PTFs). A typicalexample of a general Boolean domain is 12n . We are mainlyinterested in the length (the number of monomials) of PTFs, withtheir degree and weight being of secondary interest. We show thatPTFs on general Boolean domains are tightly connected to depth twothreshold 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 includerelationships between weight and degree of PTFs, and a degree lowerbound for PTFs of constant length. We also consider a variant of PTFsover the max-plus algebra. We show that they are connected to PTFsover general domains and to AC0THR circuits.",

keywords = " MPC, threshold formulae, multiparty computation, circuit complexity, Communication complexity, lower bounds, Polynomial threshold functions, threshold circuits",

author = "Gil Cohen and Damg{\aa}rd, {Ivan Bjerre} and Yuval Ishai and Jonas K{\"o}lker and Miltersen, {Peter Bro} and Ran Raz and Ron Rothblum",

year = "2013",

language = "English",

journal = "Electronic Colloquium on Computational Complexity",

issn = "1433-8092",

number = "TR13-107",

}

Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed. / Cohen, Gil ; Damgård, Ivan Bjerre; Ishai, Yuval et al.
In: Electronic Colloquium on Computational Complexity, No. TR13-107, 2013.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

TY - JOUR

T1 - Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed

AU - Cohen, Gil

AU - Damgård, Ivan Bjerre

AU - Ishai, Yuval

AU - Kölker, Jonas

AU - Miltersen, Peter Bro

AU - Raz, Ran

AU - Rothblum, Ron

PY - 2013

Y1 - 2013

N2 - We study the complexity of computing Boolean functions on generalBoolean domains by polynomial threshold functions (PTFs). A typicalexample of a general Boolean domain is 12n . We are mainlyinterested in the length (the number of monomials) of PTFs, withtheir degree and weight being of secondary interest. We show thatPTFs on general Boolean domains are tightly connected to depth twothreshold 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 includerelationships between weight and degree of PTFs, and a degree lowerbound for PTFs of constant length. We also consider a variant of PTFsover the max-plus algebra. We show that they are connected to PTFsover general domains and to AC0THR circuits.

AB - We study the complexity of computing Boolean functions on generalBoolean domains by polynomial threshold functions (PTFs). A typicalexample of a general Boolean domain is 12n . We are mainlyinterested in the length (the number of monomials) of PTFs, withtheir degree and weight being of secondary interest. We show thatPTFs on general Boolean domains are tightly connected to depth twothreshold 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 includerelationships between weight and degree of PTFs, and a degree lowerbound for PTFs of constant length. We also consider a variant of PTFsover the max-plus algebra. We show that they are connected to PTFsover general domains and to AC0THR circuits.

KW - MPC

KW - threshold formulae

KW - multiparty computation

KW - circuit complexity

KW - Communication complexity

KW - lower bounds

KW - Polynomial threshold functions

KW - threshold circuits

M3 - Journal article

SN - 1433-8092

JO - Electronic Colloquium on Computational Complexity

JF - Electronic Colloquium on Computational Complexity

IS - TR13-107

ER -

Efficient Multiparty Protocols via Log-Depth Threshold Formulae Contact Add Comment RSS-Feed

Abstract

Keywords

Access to Document

Fingerprint

Cite this