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, ...
Martin Berger's user avatar
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 ...
Martin Berger's user avatar
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' ...
Martin Berger's user avatar
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
  • 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 ...
templatetypedef's user avatar
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 ...
Martin Berger's user avatar
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 ...
Vilx-'s user avatar
  • 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.
David Eppstein's user avatar
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,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 ...
harold's user avatar
  • 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.
usul's user avatar
  • 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/...
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

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

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,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 ...
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
  • 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 ...
orlp's user avatar
  • 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 ...
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.
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 \...
Thomas's user avatar
  • 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 ...
David Eppstein's user avatar
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 ...
David Eppstein's user avatar

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