Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
90
questions with no upvoted or accepted answers
50
votes
0
answers
2k
views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $...
- 6,685
32
votes
0
answers
6k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 6,685
19
votes
0
answers
1k
views
Lower bounds on single-source shortest paths in directed graphs
Are there any non-trivial lower bounds on the complexity of single-source shortest paths (SSSP) in a directed graph, where all edges have non-negative edge weights? Can we rule out the possibility of ...
- 11.7k
17
votes
0
answers
491
views
Can short-distance connectivity be harder than connectivity?
Has anybody seen the following (or similar) question being considered:
Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the
presence/absence of short $s$-$t$ ...
- 6,685
15
votes
0
answers
405
views
Set Intersection lower bounds
Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
- 1,177
15
votes
1
answer
439
views
Characterization of read-once formulae over the full binary basis
Background
A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (...
- 13.5k
12
votes
0
answers
284
views
Hardness of optimal sorting
For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known.
From a purely theoretical perspective, however,
exactly optimal ...
- 1,085
10
votes
0
answers
312
views
Monotone circuit complexity of matroids?
Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid.
I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these ...
- 6,685
10
votes
0
answers
174
views
Hardness in P: methods to show optimality of $O(m^2n)$-like time?
In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{...
- 381
10
votes
0
answers
287
views
Lower bound method for ordered binary decision diagrams
This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?:
If you want to prove some exponential ...
- 1,338
9
votes
0
answers
200
views
Fourth(?) moment method for minimum value
I would like to lower bound the quantity $\Pr[X\ge t, Y\ge t]=\Pr[\min(X,Y)\ge t]$ using the small moments of $X$, $Y$ and $XY$.
In particular I am interested in the case where $E[X]=E[Y]=0$, but $E[X ...
- 958
9
votes
0
answers
538
views
How to prove "obvious" facts?
The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" ...
- 6,685
9
votes
0
answers
215
views
References for de-amortization
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
- 525
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
8
votes
0
answers
116
views
Reference for a circuit lower bound for slightly superexponential time
It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem.
My question is ...
- 891
8
votes
0
answers
305
views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
- 2,482
8
votes
0
answers
260
views
Existence of "colouring matrices" — a generalisation
This is a generalisation of the following post: Existence of "colouring matrices".
As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner ...
- 11.5k
8
votes
0
answers
259
views
For median is it optimal to compare in pairs first?
Median can be done in linear time and is now down to (I think) $2.97n$.
The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small.
The following theorem, if true, may help improve ...
- 549
7
votes
0
answers
316
views
Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?
In many publications on the computational complexity of Sum of Squares (SoS) algorithms, it is typical to study the degree-$4$ relaxation; e.g.
Rounding Sum-of-Squares Relaxations
Sum-of-Squares ...
- 451
7
votes
0
answers
156
views
Size complexity of probabilistic two-way automata for a Boolean function
I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
- 171
7
votes
0
answers
245
views
Data structures lower bounds on Turing machines
Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?
I guess that people are mostly interested in models with random access, but ...
- 71
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
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
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
6
votes
0
answers
332
views
How hard is APPROXIMATE-#SAT?
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
- 203
6
votes
0
answers
181
views
Lower bound for Yao's algorithm on general addition chains?
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that
$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
- 500
6
votes
0
answers
183
views
Converse to natural proofs theorem?
Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'.
Is it easy to see the converse 'if there is no $2^{n^\...
- 12.8k
6
votes
0
answers
118
views
Lower bounds for randomized frequency estimation algorithms
Consider a stream of elements $s_1s_2\ldots s_N$.
A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?
It ...
- 9,438
6
votes
0
answers
272
views
The latest concerning Valiant-Vazirani
I'm wondering what the best method obtained for the Valiant-Vazirani theorem is. We can state the following criteria:
(1) First and foremost, has anyone been able to derandomize it?
(2) If not, ...
- 2,100
6
votes
0
answers
221
views
Lowerbounds for in-situ permutation
What is the best known lowerbound for the worst case complexity of in-situ permutation (also called in-place rearrangement)? Has there been any reported progress after the 1970's article by Knuth (...
- 161
5
votes
0
answers
69
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
5
votes
0
answers
147
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 \...
- 5,127
5
votes
0
answers
100
views
Using epsilon biased sets for circuit lower bounds
I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to ...
- 1,443
5
votes
0
answers
250
views
What is the status of Determinantal Complexity of Permanent
Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.
What is the status of the problem of Permanent's ...
user34945
5
votes
0
answers
131
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 179
5
votes
0
answers
293
views
Sketch of Razborov's paper "On the method of approximations"
(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
- 11k
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
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
4
votes
0
answers
229
views
Is $NEXP^{NP}$ known to not be contained in $NP/poly$?
To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$.
For more info, see "Superpolynomial circuits, almost sparse oracles ...
- 5,127
4
votes
0
answers
97
views
Sampling Functions Efficiently vs Pseudorandom Generators
Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions ...
- 1,062
4
votes
0
answers
263
views
Algebraic decision trees and adversary arguments
In the comparison tree model, we establish lower bounds on computing
$\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems
on which we know lower bounds in the algebraic ...
- 83
4
votes
0
answers
139
views
Natural Problems NSPACE[n] but not in DTIME[n]
It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in
$\mathrm{DTIME}[o(n\log n)]$.
Are there examples of "...
- 111
4
votes
0
answers
176
views
Nondeterministic communication complexity of Hamming distance
It is something that I think should be known:
what is nondeterministic communication complexity of following task:
is $H(x,y) \geq k$?
There is an obvious upper bound $k \log(n)$. I would expect ...
- 891
4
votes
0
answers
247
views
One-way randomized complexity of (variants of) Gap-Hamming-Distance?
The $\textsf{GapHammingDistance}$ problem over $\{0,1\}^n$ is defined as follows: Alice (resp. Bob) is given an input $x\in\{0,1\}^n$ (resp, $y\in\{0,1\}^n$), under the promise that their Hamming ...
- 4,451
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
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
3
votes
0
answers
114
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
3
votes
0
answers
95
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,537
3
votes
0
answers
168
views
Circuit's with gate computing only "simple" functions
I was curious if something like that is known or was studied.
Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.
Now let's ...
- 891
3
votes
0
answers
181
views
Finding median in a changing array
Consider the problem of needing to support an $n$ integers array structure with two operations:
Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
Median() - return the median value of ...
- 9,438