Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
16
votes
2
answers
1k
views
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
- 163
-1
votes
0
answers
65
views
What are you favorite techniques at finding lower bounds?
I know that for finding lower bounds there are information-theoretic techniques like Le Cam's Two point method, Fano inequality and Assouad, other approaches use packing number. Is there a "...
- 53
0
votes
1
answer
106
views
Confusion about lower bounds and upper bounds in learning theory
In computer science, lower bounds and upper bounds are defined as follow:
$$m \geq g(n) \implies m = \Omega(g(n))$$
$$m \leq g(n) \implies m = \mathcal{O}(g(n))$$
However, in proving lower bounds and ...
- 53
4
votes
1
answer
105
views
Lower bound for constant degree monotone arithmetic circuits
Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size $n^{10}$?
- 891
1
vote
0
answers
78
views
Conditional lower bounds for reachability
Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)?
I mean some ...
- 1,588
1
vote
0
answers
41
views
How to understand this evolutionary algorithm lower bound calculation?
I have a proof that I understand the most of it except one step
Lemma 10. The expected number of steps the $(1+1)$ EA takes to optimize a linear function with all non-zero weights is $\Omega(n \ln n)$....
- 111
13
votes
1
answer
898
views
Law of the Excluded Middle in complexity theory
A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one ...
- 7,465
0
votes
0
answers
20
views
The minimal number of messages required to solve the mutual exclusion problem in a symmetric distributed system
In the seminal paper introducing their namesake algorithm for solving the mutual exclusion problem in a distributed system, Ricart and Agrawala assert (in the first paragraph of section 4 Message ...
- 354
5
votes
1
answer
155
views
Arithmetic Circuit Hierarchy?
The answers to the following question -
Hierarchy theorem for circuit size
give a "circuit hierarchy theorem" for boolean circuits. Does there exist a similar hierarchy theorem for ...
- 151
6
votes
1
answer
573
views
Find odd-ranked numbers from a list
From a list of $n$ distinct numbers, I want to find the set consisting of all odd-ranked numbers (1st, 3rd, 5th, ...). How many comparison queries do I need?
I could sort the whole list using $O(n\log ...
- 123
6
votes
0
answers
161
views
Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?
Background
What is currently known for depth-2 $CC^0$ circuits with restricted gate types:
In [1] it is shown that $(MOD_p)^k \circ MOD_m$ circuits (that is, $k$ layers of $MOD_p$ gates at the output)...
- 1,204
2
votes
1
answer
137
views
Counting argument for LTF circuits
In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
- 327
14
votes
1
answer
373
views
What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?
I am faced with the following problem:
A uniformly random $n \times n$ matrix $M$ over a finite field $\mathbb{F}$ is sampled. The algorithm has oracle access to the matrix entries, and each query to ...
- 818
5
votes
2
answers
143
views
Time/space lower bounds on Majority (in the multitape TM model)
MAJORITY is the language of bitstrings where more than half of the bits are 1s. I'm interested in lower bounds in the multitape TM model.
This can be solved in $DTISP(O(n), O(\log(n))$ with a naive ...
- 1,204
4
votes
0
answers
192
views
Exact lower bound on matrix multiplication
The recent publication in Nature of "Discovering faster matrix multiplication algorithms with reinforcement learning" by Fawzi et al. has shown a method for discovering fewer element ...
- 905
12
votes
2
answers
681
views
Quadratic lower bound
Consider three arrays $A,B,C$ of size $N$ consisting of integers. I want to verify the following constraint: for any two indices $0 \leq i,j < N$, $A[i] < A[j] \land B[i] < B[j] \implies C[i] ...
- 1,177
5
votes
1
answer
321
views
Deciding if all matrix multiplication entries have at least two witnesses
Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...
- 1,177
4
votes
0
answers
81
views
Universal Relation
In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
- 41
2
votes
2
answers
416
views
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$The question that I am wondering in this post is if there is any intuition to ...
- 125
3
votes
1
answer
182
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 ...
- 33
2
votes
1
answer
142
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
49
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
151
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,438
6
votes
1
answer
217
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 ...
- 630
2
votes
1
answer
195
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 ...
- 265
1
vote
0
answers
65
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 ...
- 803
6
votes
0
answers
153
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 ...
- 235
0
votes
0
answers
77
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
124
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
2
votes
0
answers
171
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,177
2
votes
0
answers
78
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
59
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,959
3
votes
1
answer
344
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,723
3
votes
1
answer
135
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.8k
0
votes
1
answer
183
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.8k
1
vote
1
answer
165
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
62
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
217
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,530
0
votes
0
answers
39
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 ...
- 111
14
votes
1
answer
1k
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 ...
- 5,127
6
votes
0
answers
165
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 ...
- 775
1
vote
0
answers
154
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 ...
- 173
2
votes
0
answers
172
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
166
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
3
votes
0
answers
166
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?
- 539
5
votes
2
answers
402
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 ...
- 5,127
2
votes
2
answers
220
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).
...
- 149
11
votes
3
answers
1k
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 ...
- 917
3
votes
2
answers
129
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
102
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 ...
- 213