# Questions tagged [k-wise-independence]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
221 views

### Family of functions with properties similar to k-wise independent hash functions

I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
• 183
1 vote
121 views

### Efficient randomness reduction using k-wise independence

Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits. Now it is given that we can replace these uniformly random ...
• 849
392 views

I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature. Let $D$ be a fixed distribution over $\{0,1\}^n$, and $1\... • 4,451 3 votes 1 answer 248 views ### Optimal bounds for$k$-wise non-uniform random bits Let$k\geq 2$be a constant (in my case,$k=4$), and$n,t \geq 0$be integers such that$2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ... • 4,451 9 votes 0 answers 199 views ### Fourth(?) moment method for minimum value I would like to lower bound the quantity$\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$using the small moments of$X$,$Y$and$XY$. In particular I am interested in the case where$E[X]=E[Y]=0$, but$E[X ...
• 958
I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ ...