# Tag Info

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 ...

### 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\\&...
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 ...
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.
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)$ ...
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 ...
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 ...
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.
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 ...
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. ...

### 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).
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.

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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))$ ...
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 ...
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 ...
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})$). ...
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 ...
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 ...
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 ...

### 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 ...
### 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$. ...
### 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 ...