Skip to main content
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 ...
user555045's user avatar
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
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
7 votes

Problems in NP with non-trivial certificate

I feel like problems $P\in\mathsf{NP}\cap\mathsf{coNP}$ are good examples for your question. Typically, for $P\not\in\mathsf{P}$, at least one of the witnesses is non-trivial. For example, the closest ...
Mark Schultz-Wu's user avatar
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

Problems in NP with non-trivial certificate

Kuperberg's certificate of knottedness of a knot is not entirely trivial, and (I believe still) contingent on the Generalized Riemann Hypothesis. It includes lots of not super-difficult, but not ...
Mark S's user avatar
  • 1,125
5 votes

Obscure characterizations of the regular languages

I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already ...
J.-E. Pin's user avatar
  • 4,841
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

Obscure characterizations of the regular languages

Here are fun ones: computational interpretations of circular proofs for Kleene algebra in linear logic, see https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45 (Theorem 24) ...
Denis's user avatar
  • 8,903
3 votes

What online talks should everyone watch?

Not a technical talk, not a recent one either, but I recommend Jean-Pierre Serre's How to write mathematics badly. Besides being hilarious, it gives genuinely good advice for writing clear papers.
Jean Abou Samra's user avatar
3 votes

Obscure characterizations of the regular languages

The following restrictions on Turing machines force them to recognize only regular languages: space complexity $o(\log \log n)$ https://doi.org/10.1109/FOCS.1965.11 single-tape with time complexity $...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
2 votes

Obscure characterizations of the regular languages

I think this one may fit the bill: A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series. Definitions. Let $\Sigma$ be an alphabet and $\...
Ekene E.'s user avatar
  • 121
2 votes

Obscure characterizations of the regular languages

A language is regular if and only if it is linearly separable by the DFA kernel, defined here: How many DFAs accept two given strings? This is Theorem 11 in https://www.sciencedirect.com/science/...
Aryeh's user avatar
  • 10.6k
2 votes

What are the recent TCS books whose drafts are available online?

A bit awkward as it's my own, but the draft of my monograph on distribution testing, "Topics and Techniques in Distribution Testing: A Biased but Representative Sample" (Now Publishers, FnT ...
1 vote

What are the recent TCS books whose drafts are available online?

The following book is about Database Theory, a small subarea of TCS at the border to Data Management: Principles of Databases by Marcelo Arenas, Pablo Barcelo, Leonid Libkin, Wim Martens, and Andreas ...

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