Questions tagged [k-wise-independence]
The k-wise-independence tag has no usage guidance.
9
questions
3
votes
1
answer
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
1
answer
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
7
votes
2
answers
392
views
Analogue of $k$-wise independence for other distributions than uniform
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
3
votes
1
answer
141
views
Notion similar to k-wise independence
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$ ...
- 31
4
votes
1
answer
199
views
How well do subspaces hit sets
Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\...
- 209
8
votes
1
answer
183
views
A bounded-independence variant of the Berry-Esseen theorem
I came across a presentation by Ryan O'Donnell regarding invariance principles. After proving the Berry-Esseen theorem, there is a slide that discusses extensions of the theorem and one that is ...
- 225
10
votes
1
answer
357
views
Can we construct a k-wise independent permutation on [n] using only constant time and space?
Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:
The construction uses constant time and space (i.e. preprocessing takes constant ...
- 9,596