As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [lower-bounds]

The tag has no usage guidance.

241 questions
Filter by
Sorted by
Tagged with
1 vote
32 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 ...
64 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$...
36 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$ ...
63 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 ...
28 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 ...
34 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
50 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 ...
84 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 ...
1 vote
118 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 ...
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$?
28 views

179 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 ...
203 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, ...
80 views

113 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 ...
112 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 ...
1 vote
44 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 ...
31 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 ...
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 ...
1 vote
61 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 ...
1 vote
119 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}...
55 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?
1 vote
121 views

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 $... 1 vote 1 answer 126 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 ... 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 ... 3 votes 2 answers 137 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 ... 1 vote 2 answers 339 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 ... 3 votes 1 answer 86 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 ... 1 vote 1 answer 93 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/...
1 vote
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 ...
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) ...