# Tag Info

Accepted

### Is the traditional analysis of Bloom filters wrong?

The traditional analysis is fine. The "traditional" analysis is, if it is explained correctly, an approximation; it's based on calculating the expected number of cells that are 0/1 when you hash the ...

### Data structure to determine if sets are disjoint in o(n) time

The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. ...
• 10.4k
Accepted

### Splay tree potential function: why sum the logs of the sizes?

How to come up with sum-of-logs potential Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into ...
• 1,120
Accepted

### Improved lower bounds or upper bounds on union-find structures since Tarjan?

There's a matching lower bound in the cell probe model (with a logarithmic number of bits per memory cell); see Fredman and Saks, "The cell probe complexity of dynamic data structures", STOC 1989.
• 50.2k

### Is the traditional analysis of Bloom filters wrong?

Let me add to Michael's answer that for split Bloom filters, where the hash functions have disjoint ranges, the traditional analysis is indeed correct without approximation or any concentration bounds....
• 932
Accepted

• 685

### Would a purely topological computational model be useful in decision problems in topology?

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three ...
• 824
Accepted

### Generalized Priority Queues

You will need to make some assumptions about what kinds of functions are allowed to get anywhere with this. The version of the problem where the elements of $S$ are linear functions from $\mathbb{R}$ ...
• 50.2k
Accepted

### Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution ...
• 50.2k
Accepted

### Would a purely topological computational model be useful in decision problems in topology?

I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau ...

### Sorted dictionary structure supporting efficient merges?

If you have a balanced binary search tree data structure with the finger search tree property (a search for an item $d$ positions away takes time $O(\log d)$), such as for instance a splay tree, then ...
• 50.2k
Accepted

### Quick-select contiguous subarray

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
• 4,256
Accepted

• 50.2k