Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
260
questions
2
votes
1
answer
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
2
votes
1
answer
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
3
votes
0
answers
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 ...
- 31
8
votes
0
answers
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
6
votes
1
answer
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
2
votes
1
answer
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
0
answers
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
6
votes
0
answers
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
0
votes
0
answers
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 ...
- 101
0
votes
1
answer
113
views
Complexity for universal Counter Machine with {0,1}-valued registers
Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
- 1
1
vote
0
answers
149
views
Triangle detection hardness in regular graphs
Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and ...
- 1,035
2
votes
0
answers
69
views
Obtaining a lower bound of a matrix norm
I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower ...
- 21
2
votes
0
answers
44
views
What is known about the stabilizer rank of this simple state?
Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$,
$$ |\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$
What is known or conjectured about the stabilizer ...
- 1,679
3
votes
1
answer
303
views
ETH based lower bound for $k$-COLORING of bounded degree graph
It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (...
- 1,603
3
votes
1
answer
128
views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
- 12.5k
0
votes
1
answer
156
views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
- 12.5k
1
vote
1
answer
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
0
answers
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
0
answers
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
0
votes
0
answers
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
14
votes
1
answer
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
6
votes
0
answers
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
0
answers
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
2
votes
0
answers
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 ...
- 327
0
votes
1
answer
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
2
votes
0
answers
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
5
votes
2
answers
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
2
votes
2
answers
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
10
votes
3
answers
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
3
votes
2
answers
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 ...
2
votes
0
answers
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
0
answers
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 ...
- 322
6
votes
1
answer
287
views
Big-O bounds on the k-th largest element of iid Gaussians
I'm interested in the following problem. Let $X_1, \dots, X_n$ be iid samples with a $N(0,1)$ distribution. Let $X_{[k]}$ be the $k$-th largest element of $\{X_1, \dots, X_n\}$, so e.g. $X_{[1]} = \...
- 233
0
votes
0
answers
87
views
Lower bound for permutation generator
I'm interested in a problem akin to combinatorial circuits, but in terms of complexity. Apologies for missing the correct terminology, I'll appreciate any corrections.
Given $n$ inputs numbered $1 ......
- 101
9
votes
2
answers
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 ...
- 93
0
votes
0
answers
45
views
Arranging sets in a hierarchy
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 ...
- 299
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 ...
- 327
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 ...
user17918
-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
5
votes
1
answer
236
views
Lower bound for triangle-free graphs
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 ...
- 203
7
votes
1
answer
257
views
How fast can we find and disconnect roots in a forest?
Consider a forest of rooted trees. The problem is to support two operations:
disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree ...
