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

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?

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 ...
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 ...
13 votes
Accepted

Find odd-ranked numbers from a list

Lemma 1. Any comparison-based algorithm requires $\Omega(n\log n)$ comparisons in the worst case. Proof sketch. Let $A$ be any comparison-based algorithm for the problem. Let $x=(x_1, x_2, \ldots, ...
Neal Young's user avatar
  • 10.1k
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
10 votes
Accepted

Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$

Getting an algorithm which runs in time $O(n \log n \log(1/\epsilon))$ for a $\epsilon$-approximation is pretty standard. We will require the following data structure, which I'll call a ``line ...
yangpliu's user avatar
  • 169
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
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
8 votes

Algorithm to check whether a given set is Sidon

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, per [1]: Corollary 1.2 [1]. Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ ...
Neal Young's user avatar
  • 10.1k
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

What are examples of recent relatively simple 'toolbox algorithms'?

Perhaps Markov Chain Monte Carlo. Like most other answers, it can be traced farther back, but rose to much more prominence since the mid-90s. In general, Markov chains and (random) walks on graphs are ...
usul's user avatar
  • 7,615
6 votes

What are examples of recent relatively simple 'toolbox algorithms'?

I think we could include submodular optimization. Many common optimization problems can be framed as maximizing or minimizing submodular functions subject to natural constraints. Examples include max ...
usul's user avatar
  • 7,615
5 votes

What are examples of recent relatively simple 'toolbox algorithms'?

I guess it depends on what constitutes "too advanced from a math point of view." It is natural that modern algorithmic ideas will involve more modern mathematics. The theory of Linear ...
NaturalLogZ's user avatar
5 votes

Recent advances in computer science since 2010?

CRDT (Conflict-free replicated data type), data structure used for decentralized real-time editors, has been formally defined in 2011, according to wikipedia. Industry adoption is also mentioned in ...
5 votes

Recent advances in computer science since 2010?

Differential privacy, a technique for analyzing data and releasing statistics privately, was in its infancy in 2010 and has since had a lot of development and advances, and adoption by major web ...
4 votes

What are examples of recent relatively simple 'toolbox algorithms'?

Montgomery's ladder and a whole host of other algorithms developed to mitigate side-channel attacks only appeared in the 1980-1990s. They're conceptually quite simple to understand, and the rationale ...
Raphael Treccani-Chinelli's user avatar
4 votes
Accepted

Independent set queries with preprocessing

If the graph is uniformly sparse in the sense that every subgraph with $n$ vertices contains at most $d \cdot n$ edges for some small $d$, then degeneracy ordering could be exploited to have $O(|E|)$ ...
Laakeri's user avatar
  • 1,767
4 votes
Accepted

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

Let $z$ be the coordinate-wise product of $x$ and $y$; that is, $z_i = x_i y_i$ for all $i$. Then we need to compute $\sum_{S\in {\cal S}} z_S$. Q1: We can solve the problem using dynamic programming. ...
Yury's user avatar
  • 3,899
4 votes
Accepted

On parallel complexity of modular inverse

Inverses modulo $2^n$ (for $n$ given in unary) can be computed in NC—more precisely, uniform $\mathrm{TC}^0$—by lifting (trivially computable) inverses modulo $2$: given the inverse $Y$ of $X$ modulo $...
Emil Jeřábek's user avatar
4 votes

Bigger picture behind the choice of matrices in the Strassen algorithm

Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are: Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the ...
Joshua Grochow's user avatar
4 votes

Recent advances in computer science since 2010?

There have been numerous advances in machine learning since 2010. Most of the highly impactful advances are not fully theoretically sound, but most of them involve some theoretical backings, to ...
4 votes

Complexity of simplex method

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\...
NaturalLogZ's user avatar
4 votes

Algorithm to check whether a given set is Sidon

In what range are the values in your set $S$? Note that if the range is not too large you can represent $S$ by a polynomial $P_S$ ($P_S = \sum_{s \in S} x^s$) and compute $P_S^{2}$ with the FFT ...
Bernardo Subercaseaux's user avatar
3 votes

Finding $k \times k$ rectangle in a matrix with maximum sum

If you think of your matrix as the adjacency of a bipartite graph, where $a_{ij}=1$ if and only if vertices $i$ and $j$ are adjacent, your problem is very similar to the "Densest $k$-subgraph&...
Vinicius dos Santos's user avatar
3 votes

Reducing #SAT to #MONOTONE-2SAT

In arXiv:2304.02524 Konstantinos Meichanetzidis, John van de Wetering, and I give a direct reduction from #SAT to #MONOTONE-2SAT that doesn't rely on the permanent and can be easily translated to an ...
Tuomas Laakkonen's user avatar
3 votes
Accepted

Rearrange vectors so partial sums are all non-negative

I don't know if it has an official name, but it is NP complete; I give a reduction idea from Exact Cover from 3-Sets: Given $n = 3q$, $X = \{x_1,...,x_{n}\}$ and $C_1,C_2,...,C_m$ a collection of 3 ...
Marzio De Biasi's user avatar

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