Questions tagged [lower-bounds]

questions about lowerbounds on functions, usually the complexity of an algorithm or a problem

Filter by
Sorted by
Tagged with
0
votes
0answers
128 views

Does this meet the space requirements for the lower 3-SAT bounds?

According to "What are the best current lower bounds on 3SAT?", Ryan Williams has an answer that states that the (time * space) requirements for 3-SAT must meet or exceed $n^{2 \cos(\pi/7) - o(1)}$ ...
0
votes
0answers
155 views

covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each

Let the problem, $P_{overlapping}$, be the following. We have an $N_1 \times N_2$ grid. Each cell of the grid can have the value either 0 or 1. Assume that we have $a \times b$ overlapping windows as ...
-1
votes
1answer
113 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 ...
-3
votes
1answer
516 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 ...
-3
votes
1answer
166 views

Lower bounds on $Q_{\epsilon}(IP)$

I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product. I have Nayak's lower bound, but I am not sure ...
-5
votes
1answer
184 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 $\...

1 2 3 4 5
6