Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
0
votes
0answers
22 views
Dynamic Perfect Hashing and Lower Bound
I am writing a Seminar about dynamic perfect hashing and its lower bound by the FKS schema using the the adversary method mentioned here by using a Tree data structure. But somehow i don t get how ...
2
votes
0answers
61 views
Postive interval problem lower bound
I was trying to solve the question given below.
Algorithm :
Using divide and conquer technique, divide the input till we get a very small size array's ( let us say of size 2 ). Solve these small ...
1
vote
0answers
17 views
Hardness of single source shortest path
Bellman Ford solves the single source shortest path problem when a graph may have both positive and negative weights in $O(|E||V|)$ time. This complexity is much larger than both the input and output ...
-1
votes
2answers
70 views
Why do you need at least ln(n!) many comparison to sort a list?
"If every element comparison (testing whether $a_i \le a_j$ ) provides at most one bit of information, argue that you need at least on the order of $\ln(n!)$ many tests/comparisons to sort the list."
...
0
votes
1answer
37 views
Do you >have< to define the upper and lower bound? (context: traveling salesman)
Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling ...
1
vote
2answers
86 views
Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)
Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution?
(Thanks to many comments ...
6
votes
1answer
126 views
Does finding a cycle with $\log n$ length in $\text{P}$?
Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
1
vote
0answers
19 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
2
votes
1answer
62 views
Using Yao's principle to find a lower bound
This is a HW question, so I'm not expecting any answers, just a general guidance/help.
Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
0
votes
1answer
22 views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
-1
votes
0answers
13 views
Lower Bound of a K-element Comparison sort
I'm trying to find the lower bound of a comparison sort, if I can find the minimum of k elements in one comparison. I'm not sure how to set up a decision tree to solve this problem.
1
vote
2answers
37 views
findMax reduce to sort
Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too?
I'm ...
0
votes
0answers
23 views
Using Turán's theorem to select two pairs [duplicate]
I have 30 objects , 15 have the color red and 15 have the color blue
and function that maps two objects to 1 if the two objects red ,0 other wise.
$$f:\{o_1,o_2\dots o_n\} \times \{o_1,o_2\dots o_n\...
1
vote
1answer
83 views
lower bound proof with adversary argument
We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
2
votes
0answers
24 views
Query complexity of exact learning and combinatorial parameter
When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following ...
1
vote
1answer
49 views
Minimum and maximum of sum of inverse degree of a graph
Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
2
votes
0answers
34 views
Highest lower bound on an NP complete problem
What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
2
votes
1answer
136 views
Correctness of lower bound proof
I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.
Given a sorted array $A$ (of $n$ ...
1
vote
1answer
38 views
Proof of Lower Bound for Deterministic Distinct Elements Algorithm
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma ...
0
votes
1answer
20 views
Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound [duplicate]
how to use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound.
this is a algorithm of my class home work,but i dont know how to solve it.
3
votes
0answers
67 views
How hard is APPROXIMATE-#SAT? [closed]
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
0
votes
1answer
92 views
Is this lower bound proof for the comparison-based sorting problem correct?
Here is a lower bound proof for the comparison-based sorting problem:
Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take ...
3
votes
1answer
67 views
How to prove that a problem can't be solved in time $\mathcal O(n^{1/2 - \epsilon})$?
I have seen many problems in graph theory and in other related fields which admit a sublinear (in input size) running time $\mathcal O(n^{1/2})$ algorithm, where $n$ is the input size. I am not sure ...
0
votes
0answers
67 views
How to find lower bound of f(n) for master theorem
I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has.
I usually ...
3
votes
0answers
35 views
From SETH to circuit lowerbounds
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)
In threshold ...
1
vote
2answers
429 views
Is it possible to solve 3SUM in $O(n^2)$ time?
Problem: 3SUM
Input: Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers.
Task: Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.
...
0
votes
0answers
25 views
Circuit Lower bound for $EXP^{NP}$
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.
Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).
By using the ...
3
votes
1answer
70 views
Tight bound on the number of intersections between a line and a triangulation
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of ...
18
votes
2answers
3k views
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.
Question : How to prove that it is impossible to ...
4
votes
4answers
339 views
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?
If the latter, is it possible for there to be general-purpose sorting algorithms which perform ...
2
votes
1answer
73 views
“Natural” reductions vs “Polynomial-time many-one” reductions (Karp Reductions)
For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical ...
0
votes
1answer
316 views
How to prove that matrix inversion is at least as hard as matrix multiplication?
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
0
votes
1answer
88 views
Find a subset in constant many queries
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.
Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.
Question : $\mathbb{S} \subseteq \mathbb{Z}$,...
1
vote
1answer
2k views
how to find upper bound and lower bound of quadratic equation
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields ...
1
vote
1answer
201 views
Best Algorithm for searching for an index in an array such that A[i] = i
Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log ...
1
vote
0answers
120 views
Reductions: Lower Bound and Upper Bound
The question is from my complexity-theory course.
Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can ...
1
vote
1answer
66 views
Lower bounds: Detecting a length 2 path
Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.
3
votes
1answer
88 views
Proving that converting min-heaps to max-heaps requires time Ω(n)
Suppose I have a min-heap SH stored inside an array. I can perform the operations:
view-min(SH) in $O(1)$
extract-min(SH) in $O(\log n)$
insert(SH) in $O(\log n)$
is-empty(SH) in $O(1)$
If I want to ...
1
vote
1answer
252 views
Doubt regarding address calculation in two-dimensional arrays
I am reading about the address calculation formulas for one and two-dimensional arrays. I have two related doubts concerning it.
In one of the problems, we are asked to calculate the ...
1
vote
1answer
126 views
Lower bound on space of DFS keeping the running time linear
$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$
Input : A Directed graph $G$ and a source vertex $u$.
Find : Is $v$ reachable from vertex $u$ for all $v \in V$ ?
Model of computation : Word RAM , one ...
4
votes
1answer
450 views
Complexity of determining whether three points are collinear from a set of points
Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?
I wan't to know the complexity of this decision problem and present my approach as ...
1
vote
1answer
80 views
Lower Bound for Sorted 2-Sum
Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$.
What is the lower bound for this problem?
I ...
5
votes
1answer
71 views
Lower bound of degree of polynomial approximating parity
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$
It is known [See e.g. Lemma 5 of this lecture note] that any ...
0
votes
1answer
270 views
How to solve a knapsack problem with increased weight limit?
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the ...
2
votes
0answers
98 views
Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound
I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
3
votes
1answer
63 views
Evasiveness of acyclicity of undirected graph
The lecture note by Jeff Erickson discusses "Evasive Graph Properties":
We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether ...
1
vote
1answer
331 views
Can we count the number of inversions in time $\mathcal{O}(n)$?
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).
Is there more asymptotically efficient way to do it? $\...
0
votes
1answer
213 views
Lower bound on worst case pancake number?
Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$.
I think ...
1
vote
1answer
105 views
Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?
Look at this solution:
Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION ...
3
votes
1answer
461 views
Lower bound for $k$-sorting an array
This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.
We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (...
