IEICE TRANSACTIONS on Fundamentals
Lower Bounds on the PTF Weight of ODD-MAXBIT Function
Summary :
We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1189-1190
- Publication Date
- 2023/09/01
- Publicized
- 2022/12/07
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2022DML0003
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures
Authors
Kazuyuki AMANO
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuyuki AMANO, "Lower Bounds on the PTF Weight of ODD-MAXBIT Function" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1189-1190, September 2023, doi: 10.1587/transfun.2022DML0003.
Abstract: We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DML0003/_p
Copy
@ARTICLE{e106-a_9_1189,
author={Kazuyuki AMANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Lower Bounds on the PTF Weight of ODD-MAXBIT Function},
year={2023},
volume={E106-A},
number={9},
pages={1189-1190},
abstract={We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.},
keywords={},
doi={10.1587/transfun.2022DML0003},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Lower Bounds on the PTF Weight of ODD-MAXBIT Function
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1189
EP - 1190
AU - Kazuyuki AMANO
PY - 2023
DO - 10.1587/transfun.2022DML0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
AB - We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.
ER -
English
