Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
  • 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$?
user avatar
  • 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)^...
user avatar
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 ...
user avatar
  • 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....
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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$?
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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{...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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) ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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}...
user avatar
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?
user avatar
  • 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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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/...
user avatar
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 ...
user avatar
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) ...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
  • 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$. ...
user avatar
  • 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 ...
user avatar
0 votes
1 answer
193 views

Decision tree and information-theoretic lower bound

Consider the following problem : ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 13

1
2 3 4 5