Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
241
questions
1
vote
0
answers
32
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
64
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
0
votes
1
answer
36
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$ ...
- 295
0
votes
1
answer
63
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
34
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
84
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 ...
- 123
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 ...
- 267
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
1
vote
1
answer
79
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
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
3
answers
394
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
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$?
- 323
1
vote
0
answers
219
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
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.
...
- 163
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 ...
user141218
1
vote
1
answer
305
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
163
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 ...
- 411
5
votes
5
answers
966
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
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 ...
2
votes
1
answer
103
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
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 ...
- 11.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 ...
0
votes
0
answers
203
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
61
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 ...
- 11.4k
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) ...
- 11.4k
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
0
votes
0
answers
112
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
44
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 ...
- 11.4k
0
votes
0
answers
31
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
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 ...
- 31
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 ...
- 246
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}...
- 11
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
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 $...
- 246
1
vote
1
answer
126
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 ...
- 246
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
137
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
339
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
86
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
93
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
54
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
65
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) ...
- 259