Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
6
votes
1
answer
372
views
Lower bounds for 3SUM with a free cache
Consider the 3SUM problem: given a set $S$ of $n$ numbers identify $x$,$y$,$z$, s.t $x + y = z$. It is believed that the simple $O(n^2)$ algorithm is the best possible; reductions from 3SUM have been ...
- 61
9
votes
1
answer
692
views
On optimality of Grover algorithm with high success probability
It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for ...
2
votes
0
answers
39
views
Lower bounds for minimum variance estimators in limited space
Cramer-Rao, Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical estimator has the lowest variance possible. Is there any CS related work on the minimum variance ...
- 21
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
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
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
21
votes
2
answers
1k
views
Can addition be carried out in less than depth 5?
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
- 4,001
4
votes
1
answer
371
views
Exponential blowup in Simple Proof of a theorem of Statman by Mairson
I'm studying "A simple proof of a theorem of Statman" by H.G. Mairson.
At page 4, he encodes set/type theory in lambda calculus.
In particular, note che "op" trick in the definition of $eq_{k+1}$.
...
- 411
14
votes
2
answers
511
views
Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?
There are several well-known $\mathsf{AC^0}$ circuit size lower-bound results based on random restrictions and the Switching Lemma.
Can we develop a Switching Lemma result to prove a size lower-bound ...
- 317
-3
votes
1
answer
173
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 ...
9
votes
1
answer
1k
views
How to generate a permutation uniformly by repeating using an one-bit uniform random generator?
If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.
I have a solution: run the one-bit random generator n*n times to ...
- 207
8
votes
1
answer
377
views
Lower Bounds on Running time of Graph Algorithms
Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.
Following is a result that I ...
- 263
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
9
votes
2
answers
221
views
Existence of "colouring matrices"
Edit: there is now a follow-up question related to this post.
Definitions
Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$.
A $c \times c$ matrix $M = (m_{i,j})$ is said to be ...
- 11.5k
7
votes
1
answer
545
views
Razborov's Approximation methods
The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.
People in parameterized complexity theory strongly believe that k-...
- 317
0
votes
1
answer
164
views
Functions and Counting Problems in Streaming Computation
I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the ...
- 317
11
votes
1
answer
609
views
Lower bounds for learning in the membership query and counterexample model
Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
- 10.2k
2
votes
1
answer
84
views
Lower bounds on batched query search
I am not much in the field of databases. But the problem I m facing is the following: given a database $D$, we receive a batch of distinct queries $Q = \{q_1, ..., q _k\}$, where each $q_i$ is a ...
- 644
1
vote
1
answer
396
views
Questions about computing matrix rigidity
Matrix rigidity was introduced by Valiant in 1977:
The rigidity $Rig_M(r)$ of boolean matrix $M$ over GF(2) is the
smallest number of entries of $M$ that must be changed in order to
reduce its rank ...
- 11k
9
votes
2
answers
1k
views
(0,1)-vector XOR problem
this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. ...
- 11k
12
votes
1
answer
520
views
Monotone circuit complexity of computing functions on sparse inputs
The weight $|x|$ of a binary string $x\in\{0,1\}^n$ is the number of ones in the string. What happens if we are interested in computing a monotone function on inputs with few ones?
We know that ...
- 1,831
0
votes
0
answers
158
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
16
votes
2
answers
574
views
Number of binary gates needed to compute AND and OR of n input bits simultaneously
What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The ...
8
votes
1
answer
518
views
Conditional results implying difficulty of improving upper/lower bounds for permanent
Let $A$ be a given square matrix.
Is there any evidence that beating quadratic lower bounds for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?
Is there any plausible conjecture which ...
- 2,208
12
votes
1
answer
546
views
Problems to reduce from to prove an $\Omega(n\log n)$ lower bound
What are the standard problems we can reduce from to prove $\Omega(n\log n)$ lower bounds?
Of course, state problems other than sorting and element distinctness.
- 1,631
20
votes
5
answers
468
views
Reducing space usage of st-connectivity with multiple passes?
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.
Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan ...
- 18.9k
16
votes
3
answers
906
views
How can I show a Gap-P problem is outside #P
There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take ...
- 361
42
votes
2
answers
2k
views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
- 421
19
votes
1
answer
1k
views
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
EDIT (Aug 22, 2011):
I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts ...
- 13.5k
25
votes
2
answers
2k
views
Formula size lower bounds for AC0 functions
Question:
What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?
Background:
Like most lower bounds, ...
- 13.5k
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
1
vote
0
answers
203
views
Circuit lower bound for NAND based arbitrary deterministic computation [closed]
What is the lowest known lower-bound on the number of NAND gates needed in order to perform an arbitrary deterministic computation with a fixed length input and output?
- 176
15
votes
3
answers
992
views
Progress on generalized star-height problem?
The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over ...
33
votes
2
answers
1k
views
Cohomological approach to boolean complexity
A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
- 2,806
10
votes
2
answers
658
views
What happens if we improve the time hierarchy theorems?
In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ ...
- 1,338
14
votes
3
answers
2k
views
Lower Bounds for Data Structures
Are results known which rule out the existence of "too-good-to-be-true" data structures?
For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
- 800
5
votes
1
answer
290
views
Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?
I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(...
- 1,631
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
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
18
votes
2
answers
3k
views
Hierarchy theorem for circuit size
I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.
Is it an interesting approach to class separation?
The motivation for the question is that we ...
- 445
9
votes
1
answer
850
views
Lower bounds on the Threshold function
In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
- 3,280
16
votes
1
answer
477
views
Lower bounds on the size of CFGs for specific finite languages
Consider the following natural question: Given a finite language $L$, what is the smallest context-free grammar generating $L$?
We can make the question more interesting by specifying a sequence of ...
- 14.3k
17
votes
3
answers
927
views
Succinct data structures survey?
Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them.
For those that don't know about succinct data structures:
Given a ...
- 2,359
15
votes
2
answers
564
views
Complexity lower bound: the gap between decision trees and RAMs
I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be partially generalized to the random access machine ...
- 153
12
votes
2
answers
638
views
Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?
This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results.
Specifically, I'm interested in seeing some hardness proofs for problems that are ...
- 534
8
votes
3
answers
812
views
One way randomised communication complexity of disjointness
I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a ...
- 3,950
6
votes
1
answer
1k
views
Highest lower bound on NP problems (TSP)
I'll try another question that I haven't been able to find almost any kind of information about, thanks a lot for any kind of pointers or explanations.
Is there a list of the proven lower bounds of ...
- 165
13
votes
2
answers
2k
views
Reversing a list using two queues
This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
- 1,458
22
votes
2
answers
1k
views
Protocol partition number and deterministic communication complexity
Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between ...
- 5,840
7
votes
1
answer
379
views
Stronger Lower Bounds on Nondeterministic Multiparty Communication
This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication.
From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty ...
- 3,280