Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
6
votes
1
answer
392
views
How much memory is needed for counting distinct elements in a stream exactly with high probability
Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.
Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, ...
- 9,438
10
votes
1
answer
637
views
Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?
Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$.
If the sequence of Kolmogorov complexities $K(HALT_n)$ were $O(1)$, ...
- 371
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
3
votes
1
answer
431
views
How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?
I have these two problems:
Problem 1 (Dual bin packing problem)
Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin has capacity $W$.
Question: Find ...
- 115
6
votes
1
answer
218
views
Two papers give contradictory bounds on linear probing. How do I resolve the disparity?
I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
- 2,121
1
vote
0
answers
27
views
A question about a claim in "No occurrence obstructions in geometric complexity theory"
It the new preprint
Peter Bürgisser, Christian Ikenmeyer, Greta Panova, "No occurrence obstructions in geometric complexity theory", 2016
it is stated that
1.3. Conjecture (Mulmuley and Sohoni ...
- 12.8k
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
12
votes
1
answer
578
views
Are arithmetic circuits weaker than boolean?
Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear polynomial
$$
f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$
...
- 6,685
8
votes
3
answers
273
views
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
You are given a $n$-sized binary array.
I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):
1) Pre-process the input array ...
- 9,438
4
votes
1
answer
992
views
Space complexity for multiplying $m$ matrices
Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.
The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. ...
- 176
0
votes
1
answer
175
views
Lowerbound for the minimum distance between points in a "nice" triangulation
Suppose we have a unit square $S$ that contains $n$ points. Assume we always have a point at each of the four corners. No we triangulate $S$ by adding non-intersecting segments between the points. ...
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
7
votes
1
answer
162
views
Lower bounds for noncommutative arithmetic circuits with exact division?
It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated ...
- 891
14
votes
1
answer
1k
views
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit ...
- 6,685
0
votes
2
answers
153
views
Mergeable Exact Order Statistics Data Structure
Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that
$$
x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1}
$$
and let's denote this relationship as $S_i &...
user22369
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
16
votes
1
answer
799
views
Is Dynamic Programming never weaker than Greedy?
In the circuit complexity, we have separations between powers of various circuit models.
In the proof complexity, we have separations between powers of various proof systems.
But in the algorithmic,...
- 6,685
5
votes
1
answer
197
views
Implications of a recent negative result to geometric complexity
A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with ...
- 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
8
votes
2
answers
298
views
Uncertainties in GCT program
In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
- 12.8k
8
votes
1
answer
485
views
Are there more polynomial time problems with complexity lower bounds?
I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below.
Exponential Lower Bounds:
Claim: If ...
- 5,127
0
votes
1
answer
165
views
What do these lower bounds really mean?
I was reading an abstract for a paper that gives a minimum number M of good agents that guarantees f-Byzantine gathering, if there are f Byzantine agents. It gives a lower bound of f+1 for strongly ...
- 119
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
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
7
votes
1
answer
149
views
Lower bounds for nonuniform circuits and oracles separating complexity classes
I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation.
Can someone explain how proving lower bounds for circuits and ...
- 4,001
9
votes
2
answers
518
views
What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?
I believe the answers to this question give classes such that for all polynomials $p$,
there is a problem in the class which does not have circuits of size $p(n)$.
However, I'm asking about circuit ...
user6973
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
14
votes
2
answers
713
views
How many negations do we need to compute monotone functions?
Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ ...
- 4,001
12
votes
1
answer
951
views
L/P/PSpace vs P/NP
in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
- 11k
3
votes
1
answer
151
views
Symbolic Execution of the Quine-McCluskey Algorithim
If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function. Has there been any attempts to (for lack of a better term) symbolically ...
- 133
20
votes
1
answer
1k
views
How to prove that USTCONN requires logarithmic space?
USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.
Omer Reingold ...
- 18.9k
8
votes
2
answers
301
views
New Space Lower-Bound Techniques for Streaming Algorithms
Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds?
In general, are we satisfied with the ...
- 81
2
votes
1
answer
440
views
Lower bound for finding repeated elements in sorted array
This is inspired by [1] (which still needs answers).
What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how ...
- 2,329
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
5
votes
1
answer
208
views
Communication complexity of Independent Set game?
Consider the following communication game.
Independent Set game
Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$.
Alice receives a set $X$ of edges, each ...
- 18.9k
6
votes
1
answer
809
views
Lower bounds for inversion counting in comparison model?
For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to ...
- 63
-3
votes
1
answer
607
views
Using Yao's minimax principle [closed]
Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time).
Can you give me an example using Yao's ...
- 5
2
votes
1
answer
259
views
Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?
Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following:
Is there an example of a function $f$ where the nondeterministic ...
6
votes
1
answer
526
views
Nondeterministic communication complexity of set disjointness?
In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$.
(Here $\text{DISJ}_n$ is the $n$-element set disjointness ...
- 18.9k
3
votes
0
answers
188
views
$CIS_G$ problem deterministic lower bound
In notes, http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/clique-notes.pdf, it is mentioned towards end of section $4$ that http://dl.acm.org/citation.cfm?id=237817 shows that ...
- 12.8k
1
vote
0
answers
141
views
Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?
Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. ...
- 6,782
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
3
votes
1
answer
114
views
Lower bounds and impossibility results for distributed transactions
I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations.
To avoid ...
- 2,329
3
votes
1
answer
152
views
Number of different longest common substrings
Given an alphabet $\Sigma$ of size $k$ and two strings $w_1,w_2\in \Sigma^n$ of length $n$. The longest common substring problem asks for a longest string in the set $A(w_1,w_2)$ of all common ...
- 500
12
votes
3
answers
1k
views
Properties expressible in 2-CNF or 2-SAT
How does one show that a certain property cannot be expressed in 2-CNF (2-SAT)? Are there any games, such as pebble games? It seems that the classical black pebble game and the black-white pebble ...
- 171
25
votes
1
answer
1k
views
Why is HAMILTONIAN CYCLE so different from PERMANENT?
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
- 6,685
3
votes
0
answers
138
views
What is the strongest known lower bound against SIZE(n)?
What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
- 1,318
23
votes
2
answers
991
views
Best current space lower bound for SAT?
Following on from a previous question,
what are the best current space lower bounds for SAT?
With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a ...
- 18.9k