# Questions tagged [lower-bounds]

questions about lowerbounds on functions, usually the complexity of an algorithm or a problem

260 questions
Filter by
Sorted by
Tagged with
114 views

### Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn ...
• 23
112 views

### Is the center of a BFS tree a good approximation of the graphs center?

Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$). Finding the center of the graph can easily be done using all-pairs-shortest-...
• 21
40 views

### Online assignment lower bound results

I am reading the following paper which presents a $(1-\epsilon)$-competitive online algorithm for the MaxMin (similar to the makespan) problem, defined as follows: a set of requests are arriving in an ...
144 views

### What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$. The Entropy-Constrained Quantization problem asks what is the best ...
• 9,358
208 views

### Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
• 600
153 views

### Divide and Conquer Algorithm for 1-Median Problem

Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the ...
• 267
1 vote
53 views

### Decision tree vs. pebble game lower bounds

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
• 383
134 views

### $\mathbf{AC}^0$ lower bounds for $\mathsf{Gap}\text{-}\mathsf{Max3SAT}$

Various gapped maximization problems are known not to be $\mathbf{NP}$-hard under $\mathbf{AC}^0$ reductions, e.g., $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$ (see, e.g., Proposition 4 of ...
• 161
75 views

### Low-Treewidth Sorting Networks

It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
113 views

• 12.5k
1 vote
134 views

### Average-case randomized communication complexity in the small-advantage regime

Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that  \Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, ...
• 1,733
1 vote
51 views

### Complexity Lower Bounds for 3D Sparse Gaussian Elimination

I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ...
• 111
1 vote
215 views

### Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
• 1,490
38 views

### Maximum resistor with sublinear number of measurements

Consider a set $X = \{x_1, \dots, x_n\}$ of positive real numbers (or natural numbers, if you like) to be a set of resistors. For any subset $S \subset X$, we can build resistive circuits and measure ...
• 11
848 views

### Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines? Background: I recently stumbled upon the ...
• 4,900
158 views

### Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$

This question is about computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$. The computation model we are considering is the unit-cost RAM machine with linear ...
• 685
1 vote
153 views

### Proof that quantum computers can't easily invert permutations

Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(1)$ is even and $0$ if $\sigma^{-1}(1)$ is odd. This is the famous ...
• 153
162 views

### Time complexity of Succinct-CVP

I want to know what is the best known lower time complexity of Succinct-CVP? The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of ...
139 views

### Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for ...
• 171
163 views

### Why is it difficult for $GCT$ to prove super quadratic lower bound?

We have a quadratic lower bound for the Permanent versus Determinant problem. Why is it difficult for $GCT$ to improve it?
• 529
343 views

### Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Background It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$. Although some natural problems are known to exist, many of them ...
• 4,900
200 views

### Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
• 91
882 views

### Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
• 907
126 views

### Understanding non-equivalence of proof lengths according to proof systems

Here, in section 4.3, Fortnow says: But to prove P != NP we would need to show that tautologies cannot have short proofs in an arbitrary proof system. I am ...
100 views

### Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
• 203
1 vote
100 views

### Switching lemma for polynomials over $\mathbb{F}_2$

Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$. Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total ...
287 views

• 101
1k views

### Can three stacks be implemented in one array, with O(1) push/pop time?

Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
45 views

Suppose you have sets $S_1, \dots S_m$ such that $\sum_i |S_i| = n$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $S_i$ is a parent (or ancestor) of $S_j$ iff $S_j \... • 1,035 1 vote 0 answers 100 views ### Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands Has anyone studied the asymptotics of problems in complexity classes like$BPP$? The thought came to me that if a problem in$BPP$only requires$O(log(n))$bits of entropy to solve then, intuitively, ... • 1,131 1 vote 1 answer 84 views ### The SQ argument in Balazs Szorenyi's paper I am asking about the proof in Theorem 5 (page 6) of this paper, http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf Quite a few things about this short argument seem unclear to me, Towards the ... • 1,443 1 vote 0 answers 268 views ### On$BPP$in$P^{NP}$and$SETH$It is believed showing$BPP$in$P$involves good$PRG$s and faces lower bound barriers. Does showing$BPP$in$P^{NP}$which would mean$BPP\neq EXP^{NP}$face similar$PRG$and give lower bounds? ... • 12.5k 4 votes 1 answer 147 views ### Strong seeded randomness extractors with low entropy loss I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ... • 141 1 vote 0 answers 43 views ### Optimally fair stable matching There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively. In the traditional loyd shapeley algorithm for$n$men and$n$women, given randomly ... 3 votes 0 answers 103 views ### Why do most 0/1 matrices need linear arithmetic circuits of size$\Omega(n^2/\log(n))$? I am reading Alon et al.'s paper Linear Circuits over$GF(2)$and I am having trouble seeing the counting argument showing that most matrices need a circuit of size$\Omega(n^2/\log n)$. This result ... • 31 7 votes 1 answer 162 views ### Lower bound for enumerating k closest pair of points Consider 1 dimensional points$x_1, \dots x_n, x_i \in \mathbb{R}$where the distance between any two points is defined as$d(x_i, x_j) = \vert x_i - x_j \vert$. The goal is to enumerate all$n^2$... • 1,035 3 votes 1 answer 277 views ### Conesequences of$\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$Does$\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$has any separation of classes or consequences? My main question is can use this to show that$P \neq NP$or some thing useful ... 3 votes 0 answers 86 views ### Lower bound for reversing a list using queues How do you prove (or disprove) that a list of length$n$cannot be reversed in time$o(n \log n)$using$O(1)$queues? Each queue is FIFO. Time refers to the number of operations on the queues. ... • 2,222 5 votes 0 answers 57 views ### Inapproximability Results for APX-hard Geometric Optimization Problems A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ... -1 votes 1 answer 119 views ### Finding upper and lower bounds of a problem [closed] We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans ... • 111 5 votes 0 answers 142 views ### How hard is it to generate a set of relatively prime numbers between two given bounds? Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given$a$,$b$, and$k \in \mathbb{N}$. Does there exist a set$S \...
• 4,900
I was reading a set of notes where it says It can be shown that $\Omega(n^2)$ space is needed for one-pass algorithms to determine if an (unweighted, undirected) graph $G$ with $n$ nodes contains ...