Skip to main content

Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
29 views

How far can we push "counting argument" for proving lower bounds of time complexity?

It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
0 votes
0 answers
4 views

Deterministic online caching algorithm competitive ratio lower bound proof

I don't understand the adversary based proof in CLRS for proving lower bound of Ω (k) on competitive ratio of any deterministic online caching algorithm given that ...
4 votes
1 answer
101 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 ...
1 vote
0 answers
28 views

Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
2 votes
1 answer
77 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 ...
0 votes
0 answers
19 views

Analysis of Simon's Algorithm: Probability Expression for Matching Queries

The Simon's problem is that, given a function $f:\{0,1\}^n\to\{0,1\}^n$ such that, for all $x,y\{0,1\}^n$ t satisfies $$ f(x)=f(y)\text{ iff }x=y\oplus s $$ where $s\in \{0,1\}^n$, and the Simon's ...
3 votes
2 answers
133 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 ...
1 vote
2 answers
86 views

Bound $T$ asymptotically tight | Recursive trees

Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that, $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$ Bound $...
9 votes
2 answers
874 views

Optimal upper bound on the number of states in the complement of an NFA

I have my own version of lex and I would like to add the complement operation. Derived from that I can then add the intersection and difference also. My version ...
0 votes
1 answer
20 views

When does augmented indexing become easy?

Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output. Alice gets as input a bit vector $X=(x_1,...,x_N)$, for some ...
4 votes
1 answer
402 views

Read-once complexity of a matrix problem

Given a binary $n \times n$ matrix, we would like to decide whether there is a row or a column which consists entirely of $1$s. The caveat is that after we read an entry of the matrix, it is erased. ...
2 votes
1 answer
44 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'...
1 vote
0 answers
34 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 ...
0 votes
1 answer
45 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?
1 vote
0 answers
36 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 ...
2 votes
0 answers
32 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 ...
3 votes
0 answers
76 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$...
5 votes
2 answers
3k 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 ? ...
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$ ...
0 votes
1 answer
170 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 ...
0 votes
0 answers
43 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 ...
0 votes
0 answers
54 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
130 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 ...
2 votes
1 answer
95 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 ...
2 votes
1 answer
299 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 ...
1 vote
2 answers
138 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$?
0 votes
0 answers
32 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)^...
2 votes
2 answers
82 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....
0 votes
0 answers
58 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 ...
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 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 ...
1 vote
1 answer
615 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 ...
6 votes
1 answer
264 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. ...
1 vote
1 answer
122 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}...
1 vote
3 answers
819 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 ...
0 votes
2 answers
330 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 ...
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$?
1 vote
0 answers
309 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(...
0 votes
0 answers
155 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 ...
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 ...
2 votes
1 answer
73 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 ...
0 votes
1 answer
196 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 ...
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 ...
0 votes
3 answers
368 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 ...
2 votes
2 answers
79 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) ...
0 votes
1 answer
67 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
148 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 ...
1 vote
1 answer
69 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 ...
0 votes
1 answer
434 views

Decision tree and information-theoretic lower bound

Consider the following problem : ...

1
2 3 4 5 6