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, ...
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 ...
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' ...
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. ...
D.W.'s user avatar
  • 12.1k
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 ...
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 ...
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 ...
14 votes

Data structure whose name starts with the letter “N”?

This one seems to fit the bill: Navigation Mesh
14 votes

Data structure whose name starts with the letter “N”?

How about number ? A number is a very simple data structure, but it's an important one. You can store a date in one, or a temperature, or a position, ...
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 ...
Chris Okasaki's user avatar
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 $...
Louis's user avatar
  • 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 ...
usul's user avatar
  • 7,615
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 ...
harold's user avatar
  • 211
11 votes

Data structure whose name starts with the letter “N”?

Neural networks are often considered a computation model, but in effect they store a processed form of the training data, hence I believe it is fair to call them data structures as well.
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.
usul's user avatar
  • 7,615
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/...
Mike Rainey's user avatar
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}$ ...
David Eppstein's user avatar
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 ...
David Eppstein's user avatar
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.
Chao Xu's user avatar
  • 4,479
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 ...
David Eppstein's user avatar
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 ...
Stefan Schneider's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
orlp's user avatar
  • 885
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 ...
Peter Shor 's user avatar
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 ...
David Eppstein's user avatar
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$? ...
Ryan Williams's user avatar
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 ...
jbapple's user avatar
  • 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. ...
Dmitri Urbanowicz's user avatar
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.
7 votes

Data structure whose name starts with the letter “N”?

Just found "Neighborhood grid" Neighborhood grid: A novel data structure for fluids animation with GPU computing. Journal of Parallel and Distributed Computing, Volume 75, 2015. ...

Only top scored, non community-wiki answers of a minimum length are eligible