# Questions tagged [lower-bounds]

The tag has no usage guidance.

246 questions
Filter by
Sorted by
Tagged with
1 vote
28 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 ...
29 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
39 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
33 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 ...
24 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 ...
1 vote
54 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 ...
73 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$...
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$ ...
103 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 ...
34 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 ...
41 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
87 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 ...
90 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
127 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$?
29 views

284 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 ...
229 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, ...
85 views

127 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 ...
143 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
46 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 ...
42 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
65 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
121 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}...
$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?
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 150 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 84 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 138 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 ... 