23
votes
Accepted
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
This is a classical result of Winograd: On multiplication of 2x2 matrices.
Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix ...
- 275k
18
votes
How to prove that matrix inversion is at least as hard as matrix multiplication?
If you want to multiply two matrices $A$ and $B$ then observe that
$$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}=
\begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&...
- 1,181
10
votes
Accepted
$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem
I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.
You ...
- 9,037
9
votes
Accepted
Lower Bounds for Size of Independent Set in a Graph?
The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.
- 275k
9
votes
Accepted
space complexity of DFA intersection problem
Solving intersection Non-Emptiness for 2 DFA's:
It essentially just becomes a reachability problem for the product DFA.
Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ ...
- 246
9
votes
Accepted
guillotine cuts versus general cuts
Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.
Let us start with the upper bound and assume we are ...
- 618
8
votes
Accepted
Is Green's the best 16-input sorting network so far?
No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be ...
- 81.4k
8
votes
Accepted
Why is the lower bound of element uniqueness in $\Omega(n\log n)$?
We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.
- 9,501
7
votes
Accepted
Are there any known lower-bounds for complexity on Non-determinsitic machines
No. There are no known polynomial bounds. The best lower bounds known are merely linear.
As described here, the situation for circuits at least is "quite depressing": there are no known lower ...
D.W.♦
- 156k
7
votes
Accepted
Complexity of sorting $A+A$
This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$.
This problem is a special case of $X+Y$ sorting. ...
- 275k
7
votes
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
You can find the result at:
S.Winograd, On multiplication of 2×2
matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).
- 767
7
votes
Accepted
Does finding a cycle with $\log n$ length in $\text{P}$?
You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.
- 275k
7
votes
What is Ironic complexity? What are some good resources to learn about it?
Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term:
There is one technique that has had some striking recent successes in proving circuit lower ...
- 275k
6
votes
Using Context free language to simulate regular expression in finite automata
No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar ...
- 275k
6
votes
Is Green's the best 16-input sorting network so far?
The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates.
Sometimes there can be ...
- 881
6
votes
Is there a decision algorithm with time complexity of Ө(n²)?
Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.
In general the time hierachy theorem implies that there are such problems for most reasonable ...
- 5,931
6
votes
What is an optimal algorithm?
There are various notions of optimality one can think of. One popular notion of optimality is worst-case running time, which is what you describe:
An algorithm for solving a problem $P$ is ...
- 275k
6
votes
Prove a lower bound
Let me suggest direct simple solution: definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from ...
- 2,364
5
votes
Linear time algorithms on regular graphs
We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or ...
- 275k
5
votes
Examples for lower bounds proof except sorting
Here are some examples:
Finding an element in a sorted list takes time $\Omega(\log n)$ in the RAM model.
Implementing a disjoint sets data structure requires an amortized $\Omega(\alpha(n))$ ...
- 275k
5
votes
Accepted
Determining if an integer appears more than $n/2$ times
You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it ...
- 275k
5
votes
Accepted
How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?
Here is a proof in the real case. For general fields, this only gives a lower bound of $\lceil n/2 \rceil$, though the correct lower bound should indeed be $n$. For more, take a look at the monograph ...
- 275k
5
votes
Accepted
Lower bound of degree of polynomial approximating parity
You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$).
...
- 334
5
votes
Accepted
Lower Bound for Sorted 2-Sum
Consider the following problem I'll call check-for-ones (where it is easy to show a lower bound of $\Omega(n)$): given a binary array of length $n$, check if there are any 1s in this array. We'll ...
- 334
5
votes
Accepted
Complexity of determining whether three points are collinear from a set of points
There is an $O(n^2)$ algorithm for the more general problem of minimum area triangle, see for example these lecture notes. The problem itself (as well as minimum area triangle) is 3SUM-hard, as shown ...
- 275k
5
votes
Accepted
Lower bound on space of DFS keeping the running time linear
The questions as stated seems to be beyond reach. Without the time constraint, a superlogarithmic space lower bound on your question would imply that $\mathsf{L} \neq \mathsf{NL}$, a famous conjecture ...
- 275k
5
votes
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
O($n$ $log$ $n$) lower bound complexity assumes the length of each key bit is constant. If not, then in the worst case you must compare nearly all bits, and multiply the complexity by that length and ...
- 206
5
votes
Is it possible to solve 3SUM in $O(n^2)$ time?
A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:
Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
For each $a \in A$:
Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. ...
- 9,501
5
votes
Accepted
What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?
It is conjectured that 3SUM cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon > 0$; equivalently, it requires time $n^{2-o(1)}$. This is not the same as the stronger conjecture that ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible