Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
3
votes
1answer
99 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. ...
1
vote
0answers
36 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 ...
3
votes
0answers
83 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 ...
0
votes
0answers
34 views
(Conditional) Lower Bounds for Space-Bounded Data Structures
I have a data structure problem which is solvable in $\tilde{O}(n^3)$ space with $\tilde{O}(1)$ query time, and I suspect that it's not solvable in $\tilde{O}(n^2)$ space with $\tilde{O}(1)$ query ...
5
votes
0answers
105 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$ ...
3
votes
1answer
202 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 ...
3
votes
0answers
43 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.
...
4
votes
0answers
47 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 ...
-1
votes
1answer
53 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 ...
5
votes
0answers
134 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
votes
1answer
136 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 ...
7
votes
1answer
213 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 ...
2
votes
1answer
81 views
Petri net termination
Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example ...
4
votes
0answers
172 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 ...
4
votes
1answer
120 views
Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?
Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$.
We know from Boppana's 1997 paper on the average sensitivity of ...
-5
votes
1answer
122 views
Should GCT focus on $PSPACE\not\subseteq P/poly$?
GCT tries to show $P$ is not $NP$ by showing $NP$ is not in $P/poly$.
Could it be useful in showing $\Sigma_{i+1}\not\subseteq P^{\Sigma_i}/Poly$ at every $i>0$?
Suppose if it turns out that $\...
3
votes
1answer
154 views
Separations between testing and tolerant testing for (natural) classes of functions?
Note: I am considering here property testing in the query model, with regard to Hamming distance. (So, for instance, of Boolean functions—I'm phrasing it that way below.) I am in particular not ...
4
votes
0answers
169 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 ...
0
votes
1answer
185 views
What do stronger circuit lower bounds give in terms of derandomization?
We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.
This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
2
votes
1answer
96 views
Non-Uniform Lower Bounds for NSPACE
If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of ...
1
vote
1answer
295 views
Common terminology used for lower/upper bounds
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
1
vote
0answers
56 views
\alpha-path on Euclidean graphs
Consider the following problem:
Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
1
vote
0answers
31 views
Problem dependent lower bound for stochastic bandits with full information
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
8
votes
0answers
98 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 ...
7
votes
1answer
216 views
What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?
Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (...
6
votes
0answers
122 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 ...
3
votes
0answers
160 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 ...
12
votes
1answer
363 views
Compressing information about the halting problem for oracle Turing machines
The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.
More precisely,...
2
votes
1answer
121 views
Application of weak determinantal identities to GCT?
In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to ...
9
votes
0answers
144 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 ...
2
votes
1answer
117 views
On $\Delta_i^P$
We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$.
If $P=BPP$ is there a 'higher' randomized class ...
1
vote
0answers
71 views
Tribes function vs (modified) polynomial threshold circuits
Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ ...
2
votes
1answer
90 views
Counting xyz-graphs in $\mathbb{Z}_n^3$
This is a followup question to: Lower bound on the largest restrained cubic subset
How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$
This question may be seen ...
3
votes
2answers
122 views
Lower bound on the largest restrained cubic subset
Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:
Each row in the cube (in any of the three directions) has exactly 2 ...
6
votes
1answer
119 views
Reference request: complexity of $k$-partite $k$-SAT
Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT:
given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal ...
1
vote
0answers
111 views
Information theoretic lower-bound on object graph serialization
This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
10
votes
0answers
451 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
votes
0answers
84 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 ...
5
votes
0answers
158 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^\...
9
votes
1answer
182 views
Where can I find examples of error correcting codes of the following types?
First, apologies if this question is in appropriate or trivial for this site. I'm a physicist looking for some help outside his comfort zone.
In PRL 87 167902 (2001) it is claimed that
"...for an ...
5
votes
1answer
135 views
Hardness of Subgraph isomorphism problem for sparse pattern graph
Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
15
votes
0answers
297 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 ...
4
votes
0answers
87 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 ...
7
votes
1answer
243 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$, ...
10
votes
1answer
262 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)$, ...
5
votes
0answers
204 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 ...
4
votes
0answers
126 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 "...
4
votes
0answers
160 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 ...
3
votes
1answer
205 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 ...
6
votes
1answer
187 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, ...
