34
votes
Recent advances in computer science since 2010?
Deriving fast JIT compilers from interpreters. It has long been known, that, in principle, compilers can be derived
from interpreters in a mechanical way. This is a special case of
partial evaluation, ...
- 11.4k
20
votes
Recent advances in computer science since 2010?
Low precision floating point data types. Historically, most programming used the IEEE 754 Standard for
Floating-Point Arithmetic. Simplifying a great deal, IEEE 754 floats (64 bits version) give you
...
- 11.4k
19
votes
Recent advances in computer science since 2010?
Liquid types. Introduced in [1], and refined in multiple follow-up papers. Liquid types can be seen as a form of dependent types that break with
traditional type theory which is keen to
have 'nice' ...
- 11.4k
16
votes
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. ...
- 11.7k
16
votes
Recent advances in computer science since 2010?
Newer data structures. The mighty Bloom filter, which has been around since 1970, provides a way to store an approximation of a set of $n$ elements with false positive rate $\varepsilon$ using ...
- 2,121
15
votes
Recent advances in computer science since 2010?
Translation validation of compilers.
In compilation, especially optimising compilation, correctness is a big issue for obvious reasons.
Ideally, we'd like the whole compiler being proven correct once ...
- 11.4k
15
votes
Recent advances in computer science since 2010?
async/await pattern
I'm not really sure how well this fits the criteria (especially the "since 2010" part is kinda fuzzy here), but I myself consider this to be the most significant ...
- 275
13
votes
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.9k
11
votes
Purely(ish) functional data structure with fast append and forward iteration
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 ...
- 211
11
votes
Accepted
How to show that the median cannot be maintained in $O(1)$ time?
If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:
first you compute a value $a$ smaller than all elements in the sequence and a value $...
- 775
11
votes
What are examples of recent relatively simple 'toolbox algorithms'?
More attention has been given recently to sketching and streaming data structures, such as Bloom Filters, Count Min Sketch, HyperLogLog.
Related, and also gaining popularity, are linear-algebra-based ...
- 7,595
11
votes
What are examples of recent relatively simple 'toolbox algorithms'?
Suffix arrays, with linear time construction. There are various algorithms, they're relatively approachable, and applications are plenty. SA-IS dates to 2009.
Soft heaps, they're not that complex, and ...
- 211
10
votes
What are examples of recent relatively simple 'toolbox algorithms'?
Quantum algorithms would fit this, if one has time to introduce the model -- specifically, Grover search and possibly Shor's algorithm.
- 7,595
9
votes
What's new in purely functional data structures since Okasaki?
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/...
- 91
9
votes
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.9k
9
votes
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.9k
8
votes
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.9k
8
votes
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,367
8
votes
Accepted
Fast Algorithm to Check if a Set of Sets forms an Anti-chain
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 ...
- 359
8
votes
Accepted
Random sampling data structure with removal
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 ...
- 9,595
8
votes
Sublinear Time Regular Expression Search
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 ...
- 720
8
votes
What are examples of recent relatively simple 'toolbox algorithms'?
You could look at the multiplicative weights update method. Specific instances of this technique have been known since the 1950s, but it's only been recognized as a very useful general algorithmic ...
- 24.3k
7
votes
Accepted
What are the must-read search trees paper?
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 ...
- 50.9k
7
votes
Pairwise comparison of bit vectors
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$? ...
- 27.3k
7
votes
Accepted
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
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 ...
- 11.2k
7
votes
Accepted
How fast can we find and disconnect roots in a forest?
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. ...
7
votes
Recent advances in computer science since 2010?
There is a lot going on in cryptography.
Homomorphic encryption
Zero-knowledge proofs, snarks and zk-snarks
Post-quantum cryptography
This post is community wiki; hopefully others can expand.
6
votes
Accepted
Min Hamming distance of a given string from substrings of another string
Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:
Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.
Define polynomials $$p(x,y) = \sum_{i \...
- 2,803
6
votes
Accepted
maximizing inner product
For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is ...
- 50.9k
6
votes
Huffman Tree Depth, Is there any theory?
I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with ...
- 50.9k
Only top scored, non community-wiki answers of a minimum length are eligible