Questions tagged [independence]
The independence tag has no usage guidance.
12
questions
0
votes
2
answers
33
views
Combining different length epsilon-ADU hash function families
For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that
for any distinct $m, m' \in M$...
- 720
3
votes
1
answer
220
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
4
votes
0
answers
150
views
What degree of hash function independence is needed for Bloom filters?
In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
- 2,121
2
votes
0
answers
57
views
Is there a complete and finite axiom scheme for conditional independence? (Graphoids)
Note: This is a better-written version of an unanswered question asked before on MathOverflow.
Question: Is there a complete and finite axiom scheme for conditional probability?
If so, is there a ...
- 503
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
210
views
When are all facets rank facets? (for independence system polyhedra)
Consider an independence system $(E,\mathcal{I})$, and the corresponding polytope:
$P(E,\mathcal{I}):=\operatorname{conv.hull}\{ x^S ~|~S\in \mathcal{I}\}$
where $x^S \in \{0,1\}^E$ denotes the ...
- 1,166
2
votes
1
answer
199
views
Dual/complement of independence system
An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that:
$\emptyset \in \mathcal{I}$, and
$I_1 \...
- 1,166
4
votes
0
answers
70
views
Set-systems with some version of independence
Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is,
$$
\Pr_{\substack{T\subset [N]\\|T| = m}}...
- 2,482
3
votes
2
answers
520
views
Generalization of independent set
I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices.
How about if you allow no more than $k$ pairs of adjacent vertices? ...
- 299
14
votes
1
answer
338
views
How much independence is required for separate chaining?
If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
- 11.2k
10
votes
1
answer
246
views
Computing the union closure
Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking ...
- 1,339
17
votes
3
answers
2k
views
Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)
Answer: not known.
The questions asked are natural, open, and apparently difficult; the question now is a community wiki.
Overview
The question seeks to divide languages belonging to the complexity ...