complexity lowerbounds
75
votes
15answers
3k 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 ...
45
votes
4answers
1k 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 ...
35
votes
3answers
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 ...
34
votes
4answers
1k views
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
32
votes
0answers
515 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 ...
27
votes
2answers
901 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 ...
26
votes
8answers
1k 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 ...
25
votes
1answer
1k 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 ...
24
votes
7answers
1k 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 ...
22
votes
2answers
947 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 ...
21
votes
2answers
745 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, ...
21
votes
0answers
564 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\}$.
...
20
votes
2answers
821 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 ...
20
votes
5answers
344 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 ...
20
votes
2answers
887 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 ...
18
votes
2answers
529 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 ...
18
votes
1answer
343 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 ...
17
votes
4answers
600 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 ...
17
votes
1answer
668 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 ...
17
votes
1answer
570 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 ...
16
votes
6answers
874 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
votes
2answers
392 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 ...
14
votes
2answers
452 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 ...
14
votes
2answers
376 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 ...
13
votes
1answer
351 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 ...
13
votes
1answer
251 views
Reference to lower bound on separator in a grid?
It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle ...
13
votes
1answer
280 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 ...
12
votes
1answer
497 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 ...
12
votes
3answers
504 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 ...
12
votes
2answers
423 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 ...
11
votes
2answers
477 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 ...
11
votes
3answers
553 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 ...
11
votes
2answers
366 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 ...
11
votes
2answers
856 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 ...
11
votes
2answers
840 views
Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?
There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's ...
11
votes
1answer
205 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 ...
11
votes
1answer
208 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 ...
11
votes
1answer
376 views
Lower bounds for Nondeterministic Multiparty Communication
This is a continuation of my previous question on communication lower bounds for partial boolean functions.
Can someone suggest any reference on lower bounds for nondeterministic multiparty ...
10
votes
2answers
472 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 ...
10
votes
2answers
366 views
Lower bounds for linear satisfiability problem
In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
10
votes
1answer
404 views
How many disjoint edge-cuts a DAG must have?
The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest
path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that ...
10
votes
1answer
293 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 ...
10
votes
1answer
299 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 ...
10
votes
0answers
282 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 ...
9
votes
2answers
333 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$ ...
9
votes
2answers
213 views
Lower bound on number of oracle calls for solving $n$ instances of the halting problem
I encountered the following question, which is an easy exercise (spoiler below).
We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of ...
9
votes
1answer
286 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.
9
votes
2answers
390 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$ ...
9
votes
0answers
149 views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
9
votes
0answers
176 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 ...
