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, ...
27 votes

Theoretical explanations for practical success of SAT solvers?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were ...
Kaveh's user avatar
  • 21.6k
27 votes
Accepted

Deciding whether an interval contains a prime number

Disclaimer: I'm not an expert in number theory. Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\...
Noah Stephens-Davidowitz's user avatar
26 votes
Accepted

Has parameterized complexity led to better algorithms?

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of ...
Christian Komusiewicz's user avatar
24 votes

Theoretical explanations for practical success of SAT solvers?

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I ...
Jakob Nordstrom's user avatar
21 votes

Algorithms Careers

A friend of mine works on the combinatorics of Sturmian words, and did so for years. A Sturmian word is typically obtained from a straight line drawn on a lattice: whenever the line crosses an ...
Matthieu Latapy's user avatar
20 votes
Accepted

Examples of algorithms and proofs that seem correct, but aren't

2D local maximum input: 2-dimensional $n \times n$ array $A$ output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...
Neal Young's user avatar
  • 10.1k
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

Theoretical explanations for practical success of SAT solvers?

I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff. E.g., the very good solvers ...
Ryan O'Donnell'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' ...
18 votes

Theoretical explanations for practical success of SAT solvers?

Let me add my two cents of understanding to this, even though I've never actually worked in the area. You're asking one of two questions, "what are all the known approaches to proving theoretical ...
Magnus Wahlström's user avatar
17 votes

Theoretical explanations for practical success of SAT solvers?

There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness ...
Jan Johannsen's user avatar
17 votes
Accepted

Counterexample to max-flow algorithms with irrational weights?

The answer is that for every irrational number $r$, there exists a network with $n=6$ vertices and $m=8$ arcs, in which seven arcs have integer capacity, in which one arc has capacity $r$, and on ...
Gamow's user avatar
  • 5,772
17 votes
Accepted

Algorithm whose running time depends on P vs. NP

If you assume that $P=^?NP$ is provable in PA (or ZFC), a trivial example is the following: ...
Marzio De Biasi's user avatar
17 votes
Accepted

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

The answer is no: the 3-coloring problem can be solved in linear time on graphs of maximal degree 3 or less, by application of Brooks' theorem. I wasted some time figuring this out, so I thought I'd ...
a3nm's user avatar
  • 9,234
16 votes
Accepted

Memory requirement for fast matrix multiplication

The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See Space complexity of Coppersmith–Winograd ...
Ryan Williams's user avatar
16 votes
Accepted

Are there poly time algorithms to determine if a graph is almost bipartite?

The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See: Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of ...
David Eppstein's user avatar
16 votes
Accepted

Problems that are counter-intuitively solvable in practice?

Highly structured SAT instances (even on millions of variables) can often be solved in practice. However, random SAT instances near the satisfiability threshold with even a few hundred variables are ...
Joshua Grochow's user avatar
16 votes
Accepted

NP-hard problems with very fast exponential-time algorithms

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width. Fix any constant $\epsilon>0$ and consider the Independent Set problem ...
Neal Young's user avatar
  • 10.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
Accepted

What is the hardest instance for the group isomorphism problem?

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are ...
Joshua Grochow'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 ...
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
Accepted

Best Upper Bounds on SAT

The best algorithm for 3-SAT now has numerical upper bound $O^{*}(1.306995^n)$ on unique-3-SAT and on general-3-SAT it is also fastest but now the specific values have not been analyzed yet. Authors ...
Bubble's user avatar
  • 490
13 votes

Is the 2016 implementation of Shor's algorithm really scalable?

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get ...
Peter Shor 's user avatar
13 votes

Problems that are counter-intuitively solvable in practice?

The Hindley-Milner type system is used in functional programming languages (Haskell, SML, OCaml). The type-inference algorithm is nearly linear in practice and works amazingly well, but is known to be ...
Andrej Bauer's user avatar
  • 28.8k
13 votes
Accepted

Best parameterized algorithm for maximum clique

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the ...
Laakeri's user avatar
  • 1,767
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

Choosing random permutations in "strict" polynomial time

If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random ...
Peter Shor 's user avatar
11 votes
Accepted

Can we approximate the number of words accepted by an NFA?

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
ricardorr's user avatar
  • 541

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