37
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 keys into the filter, and then analyzing as though that was the actual number. The point is that the number of cells that are 0 (or 1) are tightly ...
32
Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the ...
17
This is almost certainly impossible.
Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$. Then there is a simple algorithm to solve the 3SUM problem—Given a set of $n$ real numbers, do any three elements sum to zero?—in $P(n)+n\cdot Q(n)$ time. We pre-process all the numbers, then for each number $a_k$, we find the ...
16
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. Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ ...
14
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 some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. ...
13
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.
12
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. This is because the error probabilities for different hash functions become independent rather than correlated. The space/error trade-off for split Bloom ...
12
Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.
Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.
Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$,...
10
The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, Finding orthogonal vectors in discrete structures. For the case of $\mathbb F_2$, we give an $O(nd)$ time algorithm for determining, given two sets of $n$ vectors $A$ and $B$, whether there is a vector in $A$ and vector in $B$ with zero inner product.
I'm sure you ...
10
You're quite right that the "queue = two lists" approaches don't give you the running time you want when you have the ability to re-use earlier versions. To get O(1) running time (amortized or worst case), you need a way to reverse the rear list and append it to the front list incrementally. Instead of doing the reverse&append all at once, taking O(N) ...
9
Edit: This algorithm is now presented here: http://arxiv.org/abs/1406.1717
Yes, to solve this problem it is sufficient to perform the following operations:
Sort $n/k$ vectors, each with $k$ elements.
Do linear-time post-processing.
Very roughly, the idea is this:
Consider two adjacent blocks of input, $a$ and $b$, both with $k$ elements; let the elements ...
9
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 introductory posts on the blog "Low Dimensional Topology" :
http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/
9
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}$ to $\mathbb{R}$ has been studied, in a projectively dual form: if you think of each linear function $y=ax+b$ as being coordinatized by the pair of parameters $(...
9
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 that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make ...
8
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 and Freedman-Kitaev-Wang proved that a quantum computer can "additively" approximate the Jones polynomial at a root of unity in polynomial time. Furthermore, by ...
8
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 if you insert a sorted sequence of $k$ items into it the total time for the insertion will be $O(k\log(n/k))$.
Now, suppose that you want to support insertions,...
8
$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.
8
This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.
For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (Abboud, Williams, Yu 15)
8
Copying my comment on that from here:
There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per update:
Hagerup, T., K. Mehlhorn, and J. I. Munro. "Optimal algorithms for
generating discrete random variables with changing distributions."
Lecture Notes in ...
8
Consider the following setup. Let $s$ be a string in the pattern <w1><w2>... for words $w_1, w_2, \dots$ that don't include <> in their alphabet. Now with the regex .*<w>.* we can check the existence of a word in the 'database' $s$. Better yet, we can substitute arbitrary characters of $w$ with a wildcard symbol ..
This gives a ...
7
Following up on the 2012 paper linked above, the work on RRB vectors has since been extended and published in ICFP'15.
RRB vector: a practical general purpose immutable sequence
http://dl.acm.org/citation.cfm?id=2784739
7
The Lin-Kernighan heuristic for the TSP ("An effective heuristic for the traveling salesman problem", Operations Research 21:489–516, 1973) is very successful in practice, but still lacks an average-case or smoothed analysis to explain its performance. It contrast, there is a smoothed analysis of the 2-opt heuristic for the TSP by Matthias Englert, Heiko ...
7
Spoiler: the types are isomorphic.
First let me clarify what might be meant by "isomorphic". Say that two datatypes $S$ and $T$ are isomorphic if there are maps $f : S \to T$ and $g : T \to S$ such that $f(g(v)) = v$ for every value $v : T$ and $g(f(u)) = u$ for every value $u : U$.
Let us fix a type $A$. We can then write your equations without the ...
7
Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list.
There is a lot of other recent work related to splay trees and dynamic optimality, for instance:
Applications of forbidden 0-1 matrices to search tree and path compression-based data structures, Seth Pettie, SODA 2010
An O (log log n)-competitive binary search tree with optimal ...
7
This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? (I believe the reduction is folklore and appears in several places, but one concrete reference is the arxiv paper "Into the Square".) In turn, this ...
7
2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key."
1.44 bits per element is optimal. See
"Hash, displace, and compress"
"Improved Bounds For Covering Complete Uniform Hypergraphs"
Data Structures and Algorithms
, Vol. 1: ...
7
The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).
The same paper states that it ...
6
This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over array[n-i-1] rather than calling reverse(array) followed by a loop over array[i].
The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of ...
6
This problem is well considered and learned in recent decades as every GPS device faces this problem.
In practice (AFAIK), the standard way of facing this problem is by the usage of distance oracles, which usually (or more correctly, used to) approximate the distance between every two nodes by keeping only a $k\times n$ distances tables for a well-selected $...
6
Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes ...
Only top voted, non community-wiki answers of a minimum length are eligible