26

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 length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has ...


21

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 horizontal edge of the lattice, output an 1; whenever it crosses a vertical edge, output a 0. From my point of view, this is quite theoretical. Yet, my friend was ...


11

It really depends on what you mean with "higher algorithms". I work in game development, and we use graph theory, linear and nonlinear optimization, computational geometry, dynamic programming, and lots of other fun stuff. If you work in robotics, simulations, industrial control software, aerospace industry, etc., there will be plenty of stuff that ...


9

There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. 1989. The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction ...


8

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 <> in their alphabet. Now with the regex .*<w>.* we can check the existence of a word in the 'database' $s$. Better yet, we can substitute arbitrary characters of $w$ with a wildcard symbol .. This gives a ...


7

Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open. Please let me know if you have any ideas. :) Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if ...


6

(This is probably a comment but I cannot comment) This seems to be 1-dimensional $k$-means clustering for $k=2$ and $k=4$. Here is a reference that gives a $O(kn + n \log n)$ algorithm for 1-d $k$-means clustering: Grønlund, Larsen, Mathiasen, Nielsen, Schneider, Song, Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. It seems similar to ...


6

In my experience (a few decades of "business" style IT, having studied CS myself) there were very few occasions where we actually programmed "interesting" algorithms, and a majority of my colleagues did not have a real CS background - if they studied it, then theoretical CS certainly did not interest them that much, judging by our non-...


6

There are plenty of places that need algorithmic research in practical applications. Just to give you some examples: My current company makes a specialised machine learning supercomputer. Most of our engineers have primarily academic background; in fact, this is a particular challenge for us, since many of them are not used to doing software engineering, ...


6

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below. EDIT: But, per the comment, the proof applies only to polytopes, not (unbounded) polyhedra! Let $P\subset \mathbb R^n$ be any polyhedron polytope such that, for all $c\in \...


5

It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a bit more of an open question. If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using ...


5

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.


4

Breaking news! A fresh result dating back to Monday: The Petri net reachibility problem was shown to have an Ackermannian lower bound (paper), which matches the complexity of the best known algorithm. Thus, the latter algorithm is optimal (if one ignores some function in the complexity that is much smaller than Ackermann, making the difference between ...


4

Computing this type of edit distance is NP-complete, which I will prove below by reducing from the NP-complete problem Vertex Cover (given a graph $G$ and a number $k$, determine whether there exists a set of vertices $C$ with $|C|\le k$ such that each edge in $G$ has at least one vertex in $C$, aka a vertex cover of size at most $k$). Helpful subproblem ...


4

This is an answer to the updated question (the original question seems harder). Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm. Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time ...


4

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path. This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover: Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...


4

Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?


4

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...


4

This is NP-hard. Here is a reduction from SAT. Suppose you have a CNF formula $\varphi$ with variables $x_1,\dots,x_n$. Add variables $x'_1,\dots,x'_n$ and clauses of the form $x_i \to \neg x'_i$ and $x_i \lor x'_i$. For each clause in $\varphi$, we add a corresponding $\cdots \lor \cdots$ clause: e.g., if $x_i \lor \neg x_j \lor x_k$ is a clause in $\...


4

The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time B. Saha, "The Dyck Language Edit Distance Problem in Near-Linear Time," 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, ...


4

See here: https://cs.stackexchange.com/questions/61113/does-a-given-e-nfa-accepts-all-the-strings "checking whether an NFA accepts all strings is PSPACE-complete". In particular, if an NFA accepts all strings then its smallest equivalent DFA has size 1, and so a positive answer to your question would imply P=PSPACE.


3

Yes. One algorithm is: pick a random $k$-bit prime $p$; reduce $n,a,b$ modulo $p$, and then check whether $n \equiv ab \pmod p$. The chance of failing to detect an error is exponentially small in $k$, and the running time is something like $O(k \log n)$ (can probably be reduced to something like $O((\log k)(\log n))$ in theory by using efficient ...


3

I looked into this last year while teaching. The other answers, including Prof. Erickson's excellent book, feel incomplete, because they handwave a step along the lines of "there is an optimal edit sequence that proceeds left-to-right" or "we start by lining up the two words in columns vertically...." (Even if that feels obvious, can you ...


3

I stumbled upon this question now, many years later. In the interim the following paper has appeared: https://dl.acm.org/doi/10.1145/3278158 https://arxiv.org/abs/1704.08705 There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '...


3

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult. I would like to ...


3

This is #P hard via counting solution to monotone DNF formula. Let $\phi(x_1,...x_n)$ be monotone DNF formula on $n$ variables. We are trying to find regular language $L$ over alphabet $\{0,1\}$ with all words of length $n$ and the words in $L$ are in one to one correspondence with the satisfying assignment of $\phi$. Variable $x_i$ in $\phi$ corresponds to $...


3

If by "edit operations" you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works. Let $x_i$ be the number of ] minus the number of [ in the first $i$ characters. Every edit operation changes each $x_i$ by at most 2. Hence you will need at least $\lceil \frac {\max x_i} 2 \rceil$ operations to ...


3

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP). First, let's restate the problem: Given: values $N$ and $T$ and positive integer intervals $R_1$, $R_2$, $\ldots$, and $R_n$ Output: the largest possible value of $\sum_{i=1}^...


3

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the ...


3

It seems to me that your problem is very close to pattern matching in compressed text, which is an active area of research. It consists in searching given patterns in compressed strings, without decompressing them. It is then faster than parsing the strings. I am not an expert, but the following seems to be a good reference: Practical and flexible pattern ...


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