Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
246
questions
1
vote
0
answers
28
views
Lower bounds on max-flow and assignment problems
As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
- 11
0
votes
1
answer
29
views
Time complexity of search algorithms?
Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ?
If so, how do we prove it?
- 101
1
vote
1
answer
39
views
Proving lower bound by proving not little o
I have been reading these distributed computing notes. In some of the proofs, for proving lower bound of $\Omega(f(n))$, we prove that no algorithm which solves the problem in $o(f(n))$ exists.
I can'...
- 11
1
vote
0
answers
33
views
How to prove a minimum number of queries needed to determine a piece of information
You have 27 coins, 1 of which is a different weight. Using a balance scale with 2 pans, how can you determine which coin is different in only 4 weighings?
Generalize this to N coins.
Hint
Solution
...
- 111
2
votes
0
answers
24
views
Sample Complexity Lower bound for PCA
I am trying to find (without success) a sample complexity lower bound for PCA. The concrete problem I am considering is -
$X_{1}, X_{2}, \cdots X_{n} \sim D(0, \Sigma)$ are $d$-dimensional vectors ...
1
vote
1
answer
54
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
73
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
37
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$ ...
- 315
0
votes
1
answer
103
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
34
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 ...
- 331
0
votes
0
answers
41
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
87
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
90
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
127
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
29
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
1
answer
163
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 ...
- 163
2
votes
2
answers
79
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
51
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
582
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 ...
- 592
0
votes
1
answer
44
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
277
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 ...
- 258
6
votes
1
answer
220
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
72
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
423
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
178
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
1k
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 ...
- 231
0
votes
1
answer
63
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
122
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
61
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.5k
0
votes
3
answers
284
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
229
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
85
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{...
- 95
2
votes
0
answers
83
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.5k
3
votes
1
answer
68
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.5k
2
votes
2
answers
75
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.5k
2
votes
1
answer
127
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
143
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.5k
1
vote
1
answer
46
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.5k
0
votes
0
answers
42
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 ...
- 269
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
65
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
121
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
56
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
137
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
150
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
84
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
138
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