The lower-bounds tag has no usage guidance.
0
votes
1answer
34 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
1answer
51 views
Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)
Take Kruskal's algorithm as an example. Why is it used to find the lower bound? When it can't guarantee an optimal solution?
5
votes
1answer
96 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
18 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
47 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
19 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 ...
0
votes
0answers
12 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
1answer
23 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
21 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\...
0
votes
1answer
46 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
48 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
24 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
117 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
30 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
18 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
57 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
80 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
62 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
50 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 ...
0
votes
2answers
316 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
51 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 ...
0
votes
1answer
49 views
On $BPP\not=SUBEXP$ and $SUBEXP\not\subseteq P/poly$?
Let $SUBEXP\not\subseteq P/poly$ hold. We know $BPP\subseteq P/poly$.
So we know $SUBEXP\not\subseteq BPP$ holds.
So either $BPP \cap SUBEXP=BPP$ holds or $BPP \cap SUBEXP\not=BPP$ holds.
In https:...
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
288 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
64 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 ...
-1
votes
1answer
254 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
87 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
1k 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
121 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
76 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
65 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
86 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
213 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
112 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
354 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
76 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 ...
4
votes
1answer
64 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
207 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
88 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
57 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
270 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
165 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
85 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
408 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$ (...
4
votes
1answer
57 views
Original literature on adversary argument
I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.
I cannot find the ...
6
votes
1answer
823 views
(Nontrivial) Algorithms for finding the third largest element of a set
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
4
votes
3answers
365 views
Why is the lower bound of element uniqueness in $\Omega(n\log n)$?
I wish to discuss the element uniqueness problem. First let's define the problem:
Definition from wikipedia:
In computational complexity theory, the element distinctness problem
or element ...
