Nearest neighbor representations of Boolean functions

DOI10.1016/J.IC.2022.104879MaRDI QIDQ2672259zbMATH OpenOpenAlexFDO

Authors Péter Hajnal, Gy. Turán, Zhi-Hao Liu

Publication date 8 June 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.01741

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Abstract: A nearest neighbor representation of a Boolean function is a set of positive and negative prototypes in $R^n$ such that the function has value 1 on an input iff the closest prototype is positive. For $k$-nearest neighbor representation the majority classification of the $k$ closest prototypes is considered. The nearest neighbor complexity of a Boolean function is the minimal number of prototypes needed to represent the function. We give several bounds for this measure. Separations are given between the cases when prototypes can be real or are required to be Boolean. The complexity of parity is determined exactly. An exponential lower bound is given for mod 2 inner product, and a linear lower bound is given for its $k$-nearest neighbor complexity. The results are proven using connections to other models such as polynomial threshold functions over $1,2$. We also discuss some of the many open problems arising.

Recommendations

• On the degree of Boolean functions as real polynomials
• scientific article; zbMATH DE number 7250146
• The best asymptotic representation of Boolean functions by information graphs
• Minimal sign representation of Boolean functions: algorithms and exact results for low dimensions
• Estimating the efficiency of threshold representations of Boolean functions

Cites work

• A linear lower bound on the unbounded error probabilistic communication complexity.
• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• Boolean function complexity. Advances and frontiers.
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
• Distance-based classification with Lipschitz functions
• scientific article; zbMATH DE number 410386 (Why is no real title available?)
• scientific article; zbMATH DE number 176776 (Why is no real title available?)
• scientific article; zbMATH DE number 1301790 (Why is no real title available?)
• scientific article; zbMATH DE number 1179314 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Large width nearest prototype classification on general distance spaces
• Near-Optimal Sample Compression for Nearest Neighbors
• NEAREST NEIGHBOR PROBLEMS
• On the minimum consistent subset problem
• Polynomial threshold functions and Boolean threshold circuits
• Polynomials that sign represent parity and Descartes' rule of signs
• Selecting the Median
• Understanding machine learning. From theory to algorithms
• Unit sphere packings and coverings of the Hamming space

Cited in

(2)

• Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
• Title not available (Why is no real title available?)

Describes a project that uses

Uses Software

• ElemStatLearn

This page was built for publication: Nearest neighbor representations of Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672259)