Candidate Boolean Functions towards Super-Quadratic Formula Size

Kenya UENO

doi:10.1587/transinf.2014FCP0011

Candidate Boolean Functions towards Super-Quadratic Formula Size

Kenya UENO

Full Text Views

0

Share
Cite this

Summary :

In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss recursive Boolean functions based on exact 2-bit functions. We show that their formula complexity are at least Ω(n²). Hence they can be candidate Boolean functions to prove super-quadratic formula size lower bounds. Next, we consider the reason of the difficulty of resolving the formula complexity of the majority function in contrast with the parity function. In particular, we discuss the structure of an optimal protocol partition for the Karchmer-Wigderson communication game.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.524-531

Publication Date: 2015/03/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2014FCP0011

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)

Category

Authors

Kenya UENO
Kyoto University

Keyword

Boolean function, computational complexity, formula complexity

Cite this

Copy

Kenya UENO, "Candidate Boolean Functions towards Super-Quadratic Formula Size" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 3, pp. 524-531, March 2015, doi: 10.1587/transinf.2014FCP0011.
Abstract: In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss recursive Boolean functions based on exact 2-bit functions. We show that their formula complexity are at least Ω(n²). Hence they can be candidate Boolean functions to prove super-quadratic formula size lower bounds. Next, we consider the reason of the difficulty of resolving the formula complexity of the majority function in contrast with the parity function. In particular, we discuss the structure of an optimal protocol partition for the Karchmer-Wigderson communication game.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0011/_p

Copy

@ARTICLE{e98-d_3_524,
author={Kenya UENO, },
journal={IEICE TRANSACTIONS on Information},
title={Candidate Boolean Functions towards Super-Quadratic Formula Size},
year={2015},
volume={E98-D},
number={3},
pages={524-531},
abstract={In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss recursive Boolean functions based on exact 2-bit functions. We show that their formula complexity are at least Ω(n²). Hence they can be candidate Boolean functions to prove super-quadratic formula size lower bounds. Next, we consider the reason of the difficulty of resolving the formula complexity of the majority function in contrast with the parity function. In particular, we discuss the structure of an optimal protocol partition for the Karchmer-Wigderson communication game.},
keywords={},
doi={10.1587/transinf.2014FCP0011},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Candidate Boolean Functions towards Super-Quadratic Formula Size
T2 - IEICE TRANSACTIONS on Information
SP - 524
EP - 531
AU - Kenya UENO
PY - 2015
DO - 10.1587/transinf.2014FCP0011
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - In this paper, we explore possibilities and difficulties to prove super-quadratic formula size lower bounds from the following aspects. First, we consider recursive Boolean functions and prove their general formula size upper bounds. We also discuss recursive Boolean functions based on exact 2-bit functions. We show that their formula complexity are at least Ω(n²). Hence they can be candidate Boolean functions to prove super-quadratic formula size lower bounds. Next, we consider the reason of the difficulty of resolving the formula complexity of the majority function in contrast with the parity function. In particular, we discuss the structure of an optimal protocol partition for the Karchmer-Wigderson communication game.
ER -