# Questions tagged [independence]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
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 ...
324 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 ...
226 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 ...
187 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 ...
98 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 ...
69 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}}...
435 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? ...
123 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 ...
135 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$ ...
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 \...