<p>Let $a_1,\cdots,a_n$ and $\theta$ be positive reals, define $A^{k}$ to be:</p>

<p>$A^0=\emptyset;\text{ } A^k=A^{k-1}\cup \{\sum_{i\in S}a_i\mid S\subseteq [n], |S|=k\},$</p>

<p>namely the sum set without repetition.</p>

<p>And the distance between two point sets are defined as $d(A,B)=\min_{x\in A; y\in B} \{|x-y|\}$, explore the property of sequence $\{d(A^n,\{\theta\})\}_{n=1}^{\infty}$, or given $\delta &lt;&lt; \theta$, estimate the minimal $k$ such that $d(A^k, [\theta-\delta, \theta+\delta])=0$.</p>

<p>This math problem has concrete connection with communication complexity of linear threshold function, where every bit of input is obtained via AND of corresponding bits from two parties. If the decreasing of sequence $\{d(A^n,\{\theta\})\}_{n=1}^{\infty}$ is rapid, then if furthermore linear threshold function has high communication complexity, then we can obtain smooth property about its weights: they would be distributed "almost log-uniformly" on the certain interval of axis, where by "log-unifrom" we mean, after taking logarithm of the coefficients of the weights, the "log-weight" appears to be uniformly distributed in certain interval.</p>

<p>I wonder if there is some previous research on this? Any previous results or ideas on it would help. Thanks a lot.</p>

CC BY-SA 3.0
2015-12-14T23:19:27.607Z
Is there any computer science content in this? It looks more like pure mathematics to me.
David Eppstein
CC BY-SA 3.0
2015-12-15T05:37:57.927Z
Yes, actually this math problem is closely related to linear threshold function and its complexity measures.
Zihan Tan
CC BY-SA 3.0
2015-12-16T04:45:11.663Z
It would help if you spelled out the connection to linear threshold complexity more concretely in the question.
Joshua Grochow
<co.combinatorics>
Distance between Sum Sets and Another Point
Zihan Tan
# Distance between Sum Sets and Another Point

(Asked by: username_0 on 2015-12-14)

Let $a\_1,\cdots,a\_n$ and $\theta$ be positive reals, define $A^{k}$ to be:

$A^0=\emptyset;\text{ } A^k=A^{k-1}\cup \{\sum\_{i\in S}a\_i\mid S\subseteq [n], |S|=k\},$

namely the sum set without repetition.

And the distance between two point sets are defined as $d(A,B)=\min\_{x\in A; y\in B} \{|x-y|\}$, explore the property of sequence $\{d(A^n,\{\theta\})\}\_{n=1}^{\infty}$, or given $\delta << \theta$, estimate the minimal $k$ such that $d(A^k, [\theta-\delta, \theta+\delta])=0$.

This math problem has concrete connection with communication complexity of linear threshold function, where every bit of input is obtained via AND of corresponding bits from two parties. If the decreasing of sequence $\{d(A^n,\{\theta\})\}\_{n=1}^{\infty}$ is rapid, then if furthermore linear threshold function has high communication complexity, then we can obtain smooth property about its weights: they would be distributed "almost log-uniformly" on the certain interval of axis, where by "log-unifrom" we mean, after taking logarithm of the coefficients of the weights, the "log-weight" appears to be uniformly distributed in certain interval.

I wonder if there is some previous research on this? Any previous results or ideas on it would help. Thanks a lot.

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: Is there any computer science content in this? It looks more like pure mathematics to me.  
> **username_0**: Yes, actually this math problem is closely related to linear threshold function and its complexity measures.  
> **username_2**: It would help if you spelled out the connection to linear threshold complexity more concretely in the question.  

---

## 0 answers

