Questions tagged [lower-bounds]

The tag has no usage guidance.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
119 views

Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is there a ...
4
votes
0answers
61 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
3
votes
0answers
392 views

Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
2
votes
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?
2
votes
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 ...
2
votes
0answers
25 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 ...
2
votes
0answers
30 views

Query complexity of exact learning and combinatorial parameter

When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following ...
2
votes
0answers
81 views

Highest lower bound on an NP complete problem

What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
2
votes
0answers
38 views

From SETH to circuit lowerbounds

Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR) In threshold ...
2
votes
0answers
138 views

Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound

I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
1
vote
1answer
29 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 ...
1
vote
1answer
77 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}...
1
vote
0answers
7 views

Lower bounds for orthogonal matrix multiplication

Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices? More precisely, let $T(N)$ denote the worst-case time of the ...
1
vote
0answers
286 views

Reductions: Lower Bound and Upper Bound

The question is from my complexity-theory course. Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can ...
1
vote
0answers
186 views

Minimum exchanges for heap sort

I'm studying heap sort and was presented with the following question. What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
0
votes
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 ...
0
votes
1answer
56 views

Decision tree and information-theoretic lower bound

Consider the following problem : ...
0
votes
0answers
18 views

Finding the lower bound through decision trees

One way to find the lower bound of a comparison based algorithm is to use the decision tree. U have two questions regarding this method : 1) We know that the height of the tree is path that connects ...
0
votes
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 ...
0
votes
0answers
67 views

Postive interval problem lower bound

I was trying to solve the question given below. Algorithm : Using divide and conquer technique, divide the input till we get a very small size array's ( let us say of size 2 ). Solve these small ...
0
votes
0answers
441 views

How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
0
votes
0answers
38 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 ...