Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
123
votes
18
answers
9k
views
Examples of the price of abstraction?
Theoretical computer science has provided some examples of "the price of abstraction." The two most prominent are for Gaussian elimination and sorting. Namely:
It is known that Gaussian ...
65
votes
5
answers
2k
views
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
- 13.5k
51
votes
4
answers
5k
views
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
- 13.6k
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
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
40
votes
3
answers
2k
views
Circuit lower bounds over arbitrary sets of gates
In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis ...
- 13.7k
39
votes
9
answers
4k
views
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
- 10.6k
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
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
30
votes
1
answer
2k
views
Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates
Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
- 6,013
29
votes
7
answers
3k
views
Proving lower bounds by proving upper bounds
The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to ...
- 20.8k
26
votes
4
answers
2k
views
Separating Logspace from Polynomial time
It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$,...
- 10.6k
25
votes
3
answers
4k
views
Nontrivial algorithm for computing a sliding window median
I need to calculate the running median:
Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-...
- 11.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
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
23
votes
3
answers
1k
views
Representing OR with polynomials
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\...
- 659
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
22
votes
6
answers
2k
views
References on Circuit Lower Bounds
Preamble
Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than ...
- 16.5k
22
votes
2
answers
1k
views
How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?
The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
- 2,035
22
votes
2
answers
603
views
Lower bounds for constant-depth formulae?
We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known ...
- 13.5k
22
votes
2
answers
2k
views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
- 1,344
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
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
21
votes
2
answers
914
views
Deterministic communication complexity vs partition number
Background:
Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}...
- 13.5k
20
votes
4
answers
1k
views
Parity and $AC^0$
Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.
Furst Saxe Sipser to Yao ...
- 3,853
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
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
20
votes
1
answer
436
views
Explain Gurvits's tensor-rank interpretation of Deolalikar's paper
[Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]
On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent ...
- 36.9k
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
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
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
18
votes
2
answers
1k
views
Lower bounds on #SAT?
The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying ...
- 6,782
18
votes
2
answers
1k
views
Status on circuit lower bounds for polylog-bounded depth circuits
Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
- 279
18
votes
2
answers
927
views
Lower bounds on Gaussian complexity
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity ...
- 1,714
18
votes
2
answers
830
views
Bounds on the size of the smallest NFA for L_k-distinct
Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:
$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
- 9,438
17
votes
2
answers
782
views
Better lower bounds than 3n for non-boolean functions?
Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results....
- 7,629
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
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
16
votes
2
answers
1k
views
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
- 163
16
votes
1
answer
606
views
Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?
This is a follow up to this question, and is related to this question of Shiva Kinali.
It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...
- 21.5k
16
votes
2
answers
576
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 ...
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
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
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
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 ...
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
15
votes
1
answer
562
views
Any polynomial which is hard to count but easy to decide?
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$...
- 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
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