Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
281
questions
0
votes
0
answers
34
views
Nonexistence of short integer program sequence which generates squares - II
Is there a way to show within a mixed integer linear program with constant number of integer variables, $poly(\log B)$ number of real variables and constraints of length $poly(\log B)$ (say length $\...
- 13.2k
6
votes
0
answers
148
views
Proof complexity of Sudoku
Let $P$ be a $N$x$N$ Sudoku puzzle
(assume $N=n^2$ for some $n\in \mathbb{N}$,
e.g. standard $9$x$9$ puzzle is $n=3$).
We can represent it in propositional logic as follows:
Variables
$p_{i,j,k}$: ...
- 21.8k
1
vote
1
answer
89
views
Is there a conditional lower bound for the k max subarray sum problem?
Consider an array $A$ of integers of length $n$. The $k$-max subarray sum asks us to find up to $k$ (contiguous) non-overlapping subarrays of $A$ with maximum sum. If $A$ is all negative then this ...
- 3,902
4
votes
1
answer
184
views
Is there a lower bound for the problem of finding the best straight line partition
I recently asked the following algorithms question on another site. The best answer so far is $O(n^4)$ time. The input is of size $O(n^2)$ and the output is just a number so I was wondering if there ...
- 3,902
17
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\...
- 173
0
votes
1
answer
128
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 ...
- 65
4
votes
1
answer
124
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}$?
- 901
1
vote
0
answers
87
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,736
1
vote
0
answers
45
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
15
votes
2
answers
1k
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,590
5
votes
1
answer
162
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
587
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 ...
- 133
6
votes
0
answers
168
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,234
2
votes
1
answer
155
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
402
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
154
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,234
4
votes
0
answers
255
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
696
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,187
5
votes
1
answer
323
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,187
4
votes
0
answers
88
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
507
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
202
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
160
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
51
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,488
6
votes
1
answer
225
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
205
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
70
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 ...
- 851
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
78
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
128
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
176
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,187
2
votes
0
answers
89
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
66
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 ...
- 2,184
3
votes
1
answer
373
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,827
3
votes
1
answer
136
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 ...
- 13.2k
0
votes
1
answer
196
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 $...
- 13.2k
2
votes
1
answer
185
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,753
1
vote
0
answers
66
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
222
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,540
0
votes
0
answers
40
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,157
6
votes
0
answers
168
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
159
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 ...
- 193
2
votes
0
answers
177
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 ...
- 337
0
votes
1
answer
172
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
168
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
435
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,157
2
votes
2
answers
231
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).
...
- 309
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