# Questions tagged [lower-bounds]

The tag has no usage guidance.

215 questions
Filter by
Sorted by
Tagged with
0answers
64 views

1answer
118 views

### Minimum and maximum of sum of inverse degree of a graph

Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
1answer
5k views

### What is an optimal algorithm?

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
0answers
14 views

### Finding upper bound on number of I/Os needed to generate all permutations of some input in external memory

The general approach outlined in this paper in its proof of the lower bound on the average number of I/Os needed to obtain a given permutation of some input in external memory is as follows. Note that ...
1answer
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 ...
0answers
30 views

### Techniques to prove lower bounds on randomized algorithms

I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines. Intuitively, when I think ...
1answer
30 views

### “Equality” problem in distributed computation

I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads). I have seen as a side note in a few lower bound proofs, a reference ...
1answer
83 views

### CLRS Question 8-6 Lower bound on merging sorted lists

I'm doing the CLRS Problems and there's a part I'm having trouble following. The question is: Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each ...
1answer
69 views

### Decision tree and information-theoretic lower bound

Consider the following problem : ...
1answer
93 views

### Lower bound on algorithm solving certain recurrence

I have to find the lower bound of the following recursion: $A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Evaluate $F_n$. \begin{align} A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}...
0answers
20 views

### How many strings for CLOSEST STRING lower bound to apply

In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming ...
1answer
31 views

### Hardness of boolean functions

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of ...
0answers
19 views

0answers
35 views

### Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?

$P \ne NP$ would imply that any polynomial is a lower bound on the time complexity of any NP complete problem. Is some non-trivial lower bound known at all?
1answer
73 views

### Existence of boolean function with exponential average case hardness

Show that for every large enough $n$, there is a boolean function $f\colon \{0,1\}^n\longrightarrow\{0,1\}$, whose average case hardness is exponential. The question is taken from Arora Barak ...
1answer
29 views

### Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3): "More ...
1answer
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 ...
3answers
76 views

### 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)$?

I have seen the formulations there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time a problem requires time $n^{2-o(1)}$ a problem requires time $\Omega(n^2)$ being used ...
2answers
118 views

### Information-theoretic limits for a weighing puzzle

Consider the following problem: You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can ...
2answers
137 views

### Why decision tree method for lower bound on finding a minimum doesn't work

(Motivated by this question. Also I suspect that my question is a bit too broad) We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
1answer
65 views

### Counting circuits with constraints

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one). In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
1answer
32 views

3answers
217 views

### Dealing with test condition '=' for a while loop when determining a bound function/loop variant

The following is the definition of what a bound function for a while loop must satisfy: The bound function is an integer-valued, total function of some of the inputs, variables and global data that ...
2answers
470 views

### Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

So far we have learned Recursion Tree, Substitution Method, and Master's Theorem. I'm not sure how we can find lower AND upper bounds. I know that using Master's Theorem, we get $T(n) = \Theta(n^4)$, ...
0answers
88 views

### Decision Tree for searching an element in an n*n matrix

I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree. My ...
0answers
26 views

### Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
1answer
70 views

### Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
0answers
26 views

### Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...