On a Communication Complexity problem in Combinatorial Number Theory

2021/03/15 by Bence Bakos, Bakos, Bence, Norbert Hegyvári +3
Computer Science · Engineering · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems #Optimization and Search Problems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2103.08174

openalex publication_date 2021/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

The original knapsack problem is well known to be NP-complete. In a multidimensional version one have to decide whether a p∈ \N^k is in a sumset-sum of a set X ⊆ \N^k or not. In this paper we are going to investigate a communication complexity problem related to this.

Related

• On the distribution of subset sums of certain sets in ℤ²_p
• A Note on Multiparty Communication Complexity and the Hales-Jewett\n Theorem
• Solving k-SUM using few linear queries
• Communication Complexity
• Recognizing Sumsets is NP-Complete