Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
jam's user avatar
  • 13
1 vote
0 answers
27 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 ...
Harry Vinall-Smeeth's user avatar
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-...
e.gryaznov's user avatar
0 votes
0 answers
18 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 ...
Sooraj S's user avatar
  • 139
1 vote
2 answers
84 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 $...
X4J's user avatar
  • 113
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 ...
CCStudent's user avatar
  • 111
4 votes
1 answer
396 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. ...
Yuval Filmus's user avatar
1 vote
0 answers
31 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 ...
Yury's user avatar
  • 11
0 votes
1 answer
40 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?
NotaChoice's user avatar
2 votes
1 answer
43 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'...
ABBA's user avatar
  • 21
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 ...
Zaz's user avatar
  • 145
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 ...
Syamantak Kumar's user avatar
2 votes
1 answer
76 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 ...
dino-t's user avatar
  • 23
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$...
AvidLearner's user avatar
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$ ...
Gabi G's user avatar
  • 325
0 votes
1 answer
161 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 ...
Alonso Montero's user avatar
0 votes
0 answers
42 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 ...
Makogan's user avatar
  • 341
0 votes
0 answers
52 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 ...
I am Clueless's user avatar
1 vote
0 answers
128 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 ...
Rayan's user avatar
  • 11
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 ...
AK-23's user avatar
  • 123
1 vote
2 answers
137 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 ...
ErroR's user avatar
  • 1,942
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$?
jhjhb's user avatar
  • 1
0 votes
0 answers
31 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)^...
Goli Emami's user avatar
2 votes
1 answer
274 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 ...
Ralff's user avatar
  • 163
2 votes
2 answers
81 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....
pedroth's user avatar
  • 235
0 votes
0 answers
57 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 ...
ErQ65's 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?
ajaykr's user avatar
  • 1
1 vote
3 answers
806 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 ...
ExpressionCoder's user avatar
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$?
Ahmad's user avatar
  • 323
1 vote
0 answers
303 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(...
Osama Naeem's user avatar
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 ...
Tom Finet's user avatar
  • 258
6 votes
1 answer
262 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. ...
MeyCJey's user avatar
  • 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 ...
user avatar
1 vote
1 answer
578 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 ...
Assaf Cohen's user avatar
0 votes
1 answer
194 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 ...
Emad's user avatar
  • 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 ...
MathCurious's user avatar
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 ...
Curious Scientist's user avatar
2 votes
1 answer
145 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 ...
Omid Yaghoubi's user avatar
1 vote
1 answer
68 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 ...
nir shahar's user avatar
  • 11.6k
0 votes
3 answers
362 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 ...
Curious Scientist's user avatar
0 votes
0 answers
242 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, ...
t24akeru's user avatar
  • 155
2 votes
0 answers
93 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{...
Grigori's user avatar
  • 105
2 votes
0 answers
84 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 ...
nir shahar's user avatar
  • 11.6k
3 votes
1 answer
79 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 ...
nir shahar's user avatar
  • 11.6k
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) ...
nir shahar's user avatar
  • 11.6k
2 votes
1 answer
141 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 ...
jschoi's user avatar
  • 123
0 votes
0 answers
185 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 ...
nir shahar's user avatar
  • 11.6k
1 vote
1 answer
48 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 ...
nir shahar's user avatar
  • 11.6k
0 votes
0 answers
48 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 ...
Cryptonaut's user avatar
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 ...
jh1001's user avatar
  • 31

1
2 3 4 5 6