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 ...
user avatar
  • 521
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 $...
user avatar
  • 695
9 votes

Quadratic lower bound

I think this works, but I don't have time to check the details carefully right now. I'll sketch the ideas and finish later, or someone else can check. Lemma 1. There is an $O(n\log n)$-time algorithm ...
user avatar
  • 8,273
7 votes
Accepted

Quadratic lower bound

One can also find an $O(n \log n)$ time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.
user avatar
7 votes
Accepted

How can we compute the VC dimension of a finite class of sets?

In 1996 Papadimitriou and Yannakakis noted that there exists an $n^{O(\log n)}$ brute-force algorithm (where $n$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all ...
user avatar
  • 11.8k
6 votes

minimizing size of regular expression

It is PSPACE-complete to decide whether an expression accepts all words, i.e. is equivalent to $(a|b|c|...)^*$. It is not hard to get convinced that in this proof of PSPACE-completeness (see e.g. ...
user avatar
  • 7,653
6 votes

Decomposition of a permutation into increasing subsequences

You seem to be assuming that an ideal decomposition exists for all permutations. It does not. Consider the permutation 6 2 4 8 10 1 3 7 9 5. The maximum length increasing subsequence is 4. If you take ...
user avatar
5 votes
Accepted

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Yes, there are many such algorithms. Two of the easiest are (1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each ...
user avatar
5 votes

Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable

Suppose you have variables $a,b,t_1,t_2,t_3$. Consider the formula $$\bigwedge_i (a \lor b \lor t_i) \land (\neg a \lor \neg b \lor \neg t_i) \land (t_1 \lor t_2 \lor t_3) \land (\neg t_1 \lor \neg ...
user avatar
  • 10.5k
3 votes
Accepted

Young Diagrams and distinguishing between two distributions

Even relaxing the "computationally efficient" requirement, it is information-theoretically impossible. We will use the following "folklore" fact, which can be viewed as a ...
user avatar
  • 4,341
3 votes
Accepted

Is a grid graph a vertex-minor of a complete graph?

Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$. Proof that vertex-minors of complete graphs are complete, star, or ...
user avatar
  • 1,432
2 votes
Accepted

Partition a graph into two clusters

Theorem 1. The problem admits a 2-approximation algorithm that runs in $O((m+n)\log n)$ time, given a graph $G=(V,E)$ with $m$ edges and $n$ vertices. [Caveat: The current post doesn't specify the ...
user avatar
  • 8,273
2 votes

Partition a graph into two clusters

The problem even seems to be solvable in polynomial time. Let us call $C_1$ the black cluster and $C_1$ the white cluster. We test for every two edges $e_1,e_2\in E$ whether there exists a bipartition ...
user avatar
  • 5,722
2 votes

Problem in the paper "Stable Minimum Space Partitioning in Linear Time"

There is no problem here. The paper (which I was led to by your question) could have been worded better, but the $O(\log n / \log \log n)$ counters use $O(\log \log n)$ bits each as they are used to ...
user avatar
2 votes

What's the constant coefficient of the Coppersmith-Winograd algorithm?

I don't know the exact answer, but here are some relevant quotes regarding fast matrix multiplication in general: (This quote is about an earlier method with $O(N^{2.77})$ complexity. $m^{*}(3^s|F)$ ...
user avatar
2 votes

Dynamic programming and shortest path problem

Here's a less formal answer that I hope nonetheless addresses the spirit of the question. Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
user avatar
  • 8,273
2 votes

Multiplying n polynomials of degree 1

In computer algebra, this computation is usually referred as computing the subproduct tree and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. ...
user avatar
  • 4,400
2 votes
Accepted

Divide and Conquer Algorithm for 1-Median Problem

Let $opt^{*}(P_{1})$, $opt^{*}(P_{2})$, and $opt^{*}(P)$ denote the optimal $1$-median costs of $P_{1}$, $P_{2}$, and $P$, repsectively. We show that $\hat{opt} \leq 3 \cdot opt^{*}(P)$ using the ...
user avatar
2 votes
Accepted

Parameterized algorithm when the parameter is not known in advance?

I turn my different comments into an answer as I think it gives most answers. The original definition of FPT states that a parametrized problem $(L, p)$ is FPT if there exists an algorithm deciding ...
user avatar
  • 1,855
2 votes
Accepted

Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

I’m 99% certain that the proof in the paper you cite already shows this - the statement of Theorem 4 states the running time lower bound correctly as $(k-\epsilon)^{fvs}$ and incorrectly as $(3-\...
user avatar
  • 3,236
2 votes
Accepted

Maximize a special monotone submodular function - is it easier?

I believe that the problem is NP-Hard and it admits a FPTAS. Let me sketch my thoughts. NP-Hardness: Consider a slight variant of the well-known 2-Partition problem. Given $2n$ non-negative integers $...
user avatar
2 votes
Accepted

Would the following be an acceptable part of an algorithm if used for prime factorization

It's not cheating. The last step of an algorithm can certainly be: compute $n/p_1$ and check whether that is an integer and is prime. That's an allowable step in an algorithm and can be computed ...
user avatar
  • 10.5k
1 vote

Deciding if all matrix multiplication entries have at least two witnesses

This is not a proper answer but it might help you. I think a reduction to BMM might exist, but if it does, it will be hard to find: on the problem you ask for one bit (whether all ones are double-...
user avatar
  • 695
1 vote

Find whether a 3CNF formula with every clause having either all the variables negated or all the variables non-negated is satisfiable

We can convert any general $3SAT$ instance into the instance that has the form described in the question. This will prove that the problem is $NP$-Complete, and hence finding a polynomial time ...
user avatar
  • 111
1 vote
Accepted

Another variation of $k$-means problem in the plane

Assuming P$\ne$NP, there is no such poly-time approximation algorithm. I assume here that any approximation algorithm must return some feasible $k$-cover, as long as the given input has one. By a $k$-...
user avatar
  • 8,273
1 vote

Optimal solution for partitioning convex polygon into small pieces

Here's an counterexample when each piece is contained in a unit circle. For any solution with at most 3 pieces, A and B must be in the same piece (otherwise A,B,C,D are all in different pieces), which ...
user avatar
  • 328
1 vote

Interesting Variation on Subset Sum Problem

Use the standard meet-in-the-middle algorithm with complexity $O(2^{N/2})$. Contrary to what you wrote, it is not hard to implement. It involves building two lists of size $2^{20}$ (by brute-force ...
user avatar
  • 10.5k
1 vote
Accepted

2-Center problem with forbidden pairs

Maybe this will give ideas for a faster algorithm: Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm. Proof. Here's the algorithm: Using binary search over the $O(n^2)$-pairwise ...
user avatar
  • 8,273
1 vote

Complexity of optimal elimination for a planar tensor network

From Dumitrescu et al.: In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph. From Bryan O'...
user avatar
1 vote

Efficient and simple randomized algorithms where determinism is difficult

Finding a 2-approximate weighted vertex cover is known to be in RNC [1]. I don't think it is known to be in NC. That is, the problem has a randomized poly-log-time poly-processor algorithm, but I don'...
user avatar
  • 8,273

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