As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [lower-bounds]

The tag has no usage guidance.

241 questions
Filter by
Sorted by
Tagged with
39 views

### Circuit Lower bound for $EXP^{NP}$

By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$. Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures). By using the ...
169 views

### Tight bound on the number of intersections between a line and a triangulation

I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of ...
4k views

### How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication. Question : How to prove that it is impossible to ...
2k views

### Is $Ω(n\log ⁡n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms? If the latter, is it possible for there to be general-purpose sorting algorithms which perform ...
306 views

### "Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)

For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical ...
2k views

### How to prove that matrix inversion is at least as hard as matrix multiplication?

Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
104 views

### Find a subset in constant many queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point. Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$. Question : $\mathbb{S} \subseteq \mathbb{Z}$,...
1 vote
7k views

### how to find upper bound and lower bound of quadratic equation

I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields ...
1 vote
1k views

753 views

### Lower bound on worst case pancake number?

Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$. I think ...
1 vote
333 views

### Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?

Look at this solution: Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION ...
2k views

### Lower bound for $k$-sorting an array

This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds. We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we ...
93 views

### Original literature on adversary argument

I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems. I cannot find the ...
866 views

### (Nontrivial) Algorithms for finding the third largest element of a set

According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
2k views

### Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

I wish to discuss the element uniqueness problem. First let's define the problem: Definition from wikipedia: In computational complexity theory, the element distinctness problem or element ...
657 views

### Lower bound on the number of comparisons needed for finding the two largest elements

Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to ...
449 views

### How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?

Input : Two matrices $A$ and $B$ of size $n$ X $n$. Compute : Matrix product $A$ X $B$. Some of the known results about matrix multiplication are given below. Brute Force : $O(n^3)$. Nader H. ... 305 views

### lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ... 297 views

### Size of constant depth circuit for digital comparator?

Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers? Two $n$-bit binary numbers can be compared using a digital ...
173 views

### Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has ...
1k views

### Determining if an integer appears more than $n/2$ times

What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers? I am trying binary search on the array A. Algorithm(A): ... 1 vote
504 views

### Sorting using comparison is superlinear or sublinear?

My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem? In more details: we know that sorting using comparison have the achievable lower ...
1k views

### Precise relation between complexity classes(focus on P, NP and EXPTIME)

I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes. What I know so far: $P \subseteq EXP$ (from Time Hierarchy Theorem ) We don't know an exact relation between $P$ ... 1 vote
2k views

### How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?

$A = \{w \in \{a, b\}^* |$ 10th character from the end of $w$ is $b\}$ Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states. So there's only 2 characters possible at any state, aside ...
103 views

### Complexity of sorting $A+A$

Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n. In this [thread] people discuss solving this problem by sorting the ...
1k views

### Deleting edges from complete graph

I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a_i, b_i)$. I want to know if the graph is still connected after performing all the ...
132 views

### Examples for lower bounds proof except sorting

After i read this question here. All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof. What ...