Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
234
questions
1
vote
1
answer
64
views
Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions
An $\epsilon$-tester given an input and a property, is defined as follows:
If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input ...
- 13
1
vote
2
answers
91
views
Lower bound union of a unsorted array with sorted array
I read this link and I have similar question.
Suppose given two Arrays $A$ that is sorted array with length $n$ and $B$ unsorted array with length $n$. We want to find union of two arrays (i.e. we try ...
- 1
0
votes
0
answers
44
views
Lower bound union of a sorted array and unsorted array [duplicate]
Suppose given two arrays $A$ and $B$ with length $n$. Array $A$ is sorted and $B$ is unsorted. Is there any lower bound for computing $A\cup B$?
- 1
0
votes
0
answers
28
views
Tight bounds for expected maximum of k binomial(n,p) IIDs
What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables
I tried to derive it :
$$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
- 13
1
vote
1
answer
33
views
How to evaluate the tightness of a bound on a function?
I recently submitted a paper where in part of the paper I derived a bound on a function (note it is an upper bound). The benefit of the bound is that it is much less complex to compute in contrast to ...
- 153
2
votes
2
answers
66
views
What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?
I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
- 235
0
votes
0
answers
47
views
Lower bound of solving a optimization problem [duplicate]
Suppose given $k$-sorted arrays of numbers that contains total of $n$ elements. we try to choose $k$ elements in $k$ arrays (each arrays exactly one element) such that minimize difference between ...
- 1
0
votes
0
answers
14
views
non-linear lower bounds for polynomial time decision problems [duplicate]
Are there any decision problems that have deterministic polynomial time algorithms and proven non-linear lower bounds?
- 1
1
vote
3
answers
142
views
Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)
I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page ...
- 283
0
votes
1
answer
41
views
Lower bound on computing $x^n$
I know that we can compute $x^n$ in $\log n$. Are there any lower bound for computing $x^n$?
- 1
1
vote
0
answers
88
views
Adversary argument and proving a lower bound of an algorithm. How does it work?
I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
- 111
0
votes
0
answers
152
views
Problems/properties of dynamic graphs with strong lower bounds
I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and ...
- 248
6
votes
1
answer
176
views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
- 63
2
votes
1
answer
52
views
Coming up with an adversary strategy for a clique of maximum size
I’m having trouble coming up with a good adversary strategy for this problem:
Input: a graph G
Output: the maximum size of any clique in G
Where the algorithm asks each time, “are vertices x and y ...
- 31
1
vote
1
answer
153
views
Why does IP = PSPACE
Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it?
I looked at many research papers but its very hard to understand the formalism unless you have a solid ...
- 19
0
votes
1
answer
80
views
Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time
We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just ...
- 377
5
votes
5
answers
912
views
Prove a lower bound
Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$.
I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression.
Whenever I see the solutions for ...
- 221
0
votes
1
answer
48
views
Prove that the following algorithm is $\Theta(n^3)$ by induction
I have the following algorithm runtime:
$T(1) = b $ for some positive constant.
Otherwise, $T(n)=8T(\frac n 2) + 100n^2$
I am trying to prove that it is $\Theta(n^3)$ by induction.
I proved that it is ...
2
votes
1
answer
67
views
$\log n$ lower bound for space complexity
I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following:
Since the TM's work tapes are separated from its input tape, it makes sense ...
- 358
1
vote
1
answer
50
views
Communication complexity of equality gap problem
I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by:
$$f_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at ...
- 10.8k
0
votes
3
answers
83
views
Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity?
Considering the following recursive algorithm:
$ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$.
I was able to prove that this algorithm is $O(n^2 logn)$
I was trying to understand whether it is a ...
0
votes
0
answers
128
views
How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
Here Huffman coding problem is Huffman encoding.
For example,
...
- 157
2
votes
0
answers
72
views
Prove lower bound on boolean circuit
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{...
- 65
2
votes
0
answers
81
views
Number of planar graphs with linear edges, given a fixed embedding
Suppose we are given a set of $n$ points on the plane. How many different planar graphs can we form on those $n$ vertices, assuming that each edge must form a straight line between the two vertices ...
- 10.8k
3
votes
1
answer
56
views
Number of planar graphs, given an embedding
I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing ...
- 10.8k
2
votes
2
answers
60
views
Showing asymptotic lower bound on log of recurrence
I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows:
$T(1) ...
- 10.8k
2
votes
1
answer
98
views
Information-theoretic lower bound for succinct string dictionary of the Unicode Name property
Background
The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept ...
- 123
0
votes
0
answers
59
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 ...
- 10.8k
1
vote
1
answer
43
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 ...
- 10.8k
0
votes
0
answers
22
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 ...
- 249
2
votes
1
answer
758
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 ...
- 21
1
vote
1
answer
44
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 ...
- 248
1
vote
1
answer
116
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}...
- 11
2
votes
0
answers
45
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?
- 21
1
vote
1
answer
92
views
Connection between Pseudo random generators and hardness
For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
- 248
1
vote
1
answer
101
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 ...
- 248
4
votes
3
answers
80
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 ...
- 43
3
votes
2
answers
135
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 ...
user114966
1
vote
2
answers
237
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 ...
user114966
3
votes
1
answer
79
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 ...
- 33
1
vote
1
answer
68
views
Lower bound on comparison-based sorting
I have a question from one of the exercises in CLRS.
Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/...
- 23
1
vote
0
answers
14
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 ...
- 215
1
vote
1
answer
46
views
Communication Complexity for Product Distributions
In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) ...
- 249
1
vote
2
answers
49
views
Algebra for min/max bounds
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, ...
- 131
1
vote
1
answer
48
views
Lower bound time complexity for obtaining an arbitrary entry in a hashtable
I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable,
the algorithm should return a pointer to an arbitrary nonempty entry in the ...
- 111
1
vote
1
answer
63
views
Decision tree lower bound for finding two array elements summing to zero
I have to solve this exercise:
Given an unordered array $A[1], \ldots, A[n]$ of positive and negative integers,
determine if there are two indices $i \neq j$ such that
$A[i] + A[j] = 0$. ...
- 53
1
vote
1
answer
34
views
Resolution exponential lower bound... alternative proofs?
I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's Computational Complexity: A Modern ...
- 219
0
votes
1
answer
193
views
1
vote
1
answer
104
views
A Question related to the method of find lower bound : Trivial lower bounds
In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the ...
- 13
0
votes
2
answers
579
views
Lower bound and worst case scenario
We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say ...
- 13