Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
241
questions
1
vote
0
answers
30
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 13
3
votes
0
answers
56
views
Lower bound of continuous random walk
Let $X_1,...X_T$ be i.i.d. random variables supported on the $[-1,1]$ segment, with an expected value of 0 and positive variance.
Let $H_t = | \sum_{i=1}^t X_i|$, and let $H = \max_{1\leq t\leq T} H_t$...
- 229
4
votes
1
answer
91
views
Conditional lower bounds on the running time of the single source shortest path problem
Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
CommunityBot
- 1
4
votes
2
answers
2k
views
Minimal number of comparisons - sorting $6$ elements
I've been thinking about sorting $6$ elements with the minimal possible number of comparisons. I can do it in $10$ comparisons but I've no idea if this is optimal. Or is there a better algorithm ?
...
- 129
0
votes
1
answer
35
views
Universal lower bound of the multi message problem
The multi message problem is:
Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M_i$ of size $\Omega(\log(n))$ to each vertex $v_i$ ...
- 370
0
votes
1
answer
62
views
Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite.
There is a sequence of ...
- 145
0
votes
0
answers
28
views
Definition of an algebraic decision tree
I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct.
From what I have read it ...
- 143
0
votes
0
answers
33
views
What is an "almost tight bound"
I am doing some research for a paper that I am writing and one of the papers that I have come across that has some interesting results talks about an "almost tight bound". I am not a ...
1
vote
0
answers
50
views
Bounding function for Travelling Salesman Problem
I have been studying the Branch and Bound paradigm. I came across an approach to solve the Travelling Salesman Problem using branch and bound where a specific kind of bounding function was used. I've ...
- 11
2
votes
1
answer
83
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 ...
- 156
1
vote
1
answer
78
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 ...
CommunityBot
- 1
1
vote
2
answers
118
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 ...
0
votes
0
answers
45
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
2
votes
2
answers
77
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
49
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
4
answers
2k
views
Worst run-time for 3 nested loop
Suppose we need to find a tight asymptotic bound on the worst case run time of the following program
...
- 27.4k
1
vote
1
answer
299
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 ...
CommunityBot
- 1
6
votes
1
answer
202
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.
...
- 2,195
1
vote
1
answer
119
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}...
CommunityBot
- 1
1
vote
3
answers
384
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 ...
- 438
0
votes
2
answers
236
views
Sorting algorithm which sorts half the possible inputs in linear time
Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time.
(For the other half the algorithm can ...
- 27.4k
0
votes
1
answer
42
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$?
- 14.5k
1
vote
0
answers
217
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
154
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
3
votes
1
answer
1k
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 ...
CommunityBot
- 1
2
votes
1
answer
66
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 ...
- 4,161
0
votes
1
answer
159
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 ...
- 274k
5
votes
5
answers
965
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 ...
- 26.4k
0
votes
3
answers
179
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 ...
- 1,554
2
votes
2
answers
71
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) ...
- 1,554
0
votes
1
answer
61
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 ...
- 4,161
2
votes
1
answer
101
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 ...
- 274k
1
vote
1
answer
56
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 ...
- 274k
0
votes
1
answer
308
views
Decision tree and information-theoretic lower bound
Consider the following problem :
...
CommunityBot
- 1
0
votes
0
answers
202
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,
...
- 155
2
votes
0
answers
80
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
82
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 ...
- 11.4k
3
votes
1
answer
60
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 ...
- 274k
2
votes
1
answer
113
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
4
votes
1
answer
242
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 ...
- 22.4k
7
votes
1
answer
10k
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 ...
6
votes
1
answer
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 ...
- 1,171
0
votes
0
answers
109
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 ...
- 11.4k
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 ...
D.W.♦
- 152k
0
votes
0
answers
30
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 ...
- 259
1
vote
1
answer
61
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 ...
- 13.3k
1
vote
1
answer
121
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 $...
- 7,325
2
votes
0
answers
55
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?
- 121