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 ...
Yuval Filmus's user avatar
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\\&...
Amaury Pouly's user avatar
  • 1,181
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.
Yuval Filmus's user avatar
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 ...
David Richerby's user avatar
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.
hengxin's user avatar
  • 9,551
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.'s user avatar
  • 159k
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. ...
Yuval Filmus's user avatar
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).
Stella Biderman's user avatar
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.
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
adrianN's user avatar
  • 5,951
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 ...
Nayuki's user avatar
  • 881
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 ...
Yuval Filmus's user avatar
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 ...
zkutch's user avatar
  • 2,364
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))$ ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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})$). ...
jschnei's user avatar
  • 364
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 ...
jschnei's user avatar
  • 364
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Craig  Hicks's user avatar
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$. ...
hengxin's user avatar
  • 9,551
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 ...
Yuval Filmus's user avatar
5 votes

Prove a lower bound

Just apply the definition. So in this case, we must have that $\lim_{n \to \infty} f(n) / g(n) > 0$ in order for $f(n) = \Omega(g(n))$. Let's plug in what you have and observe that $$\lim_{n \to \...
Juho's user avatar
  • 22.6k
5 votes
Accepted

What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

Without arrays, $\Omega(\log n)$ time is needed. Without arrays, the memory address you access is entirely determined by the control-flow path, i.e., the sequence of control-flow decisions (if ...
D.W.'s user avatar
  • 159k
5 votes
Accepted

Read-once complexity of a matrix problem

The computation of the erasing machine can be expressed as a read-once branching program. A branching program is a DAG with a unique source and two sinks, labelled "Yes" and "No". ...
Yuval Filmus's user avatar
4 votes

Sorting using comparison is superlinear or sublinear?

In complexity theory, the input size is by convention (or definition, really) the number of cells the input takes up on a Turing machine tape. The famous $\Omega(n \log n)$ bound does not adhere to ...
Raphael's user avatar
  • 72.4k

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