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

learn more… | top users | synonyms

86
votes
16answers
5k 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 ...
47
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 ...
37
votes
0answers
763 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 ...
36
votes
4answers
2k views

What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?
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 ...
32
votes
2answers
1k 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 ...
30
votes
2answers
962 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 ...
27
votes
8answers
2k 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 ...
26
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 ...
25
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 ...
24
votes
0answers
941 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\}$. ...
22
votes
2answers
932 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 ...
21
votes
2answers
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 = ...
21
votes
3answers
1k 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, ...
21
votes
2answers
860 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
2answers
928 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 ...
20
votes
2answers
993 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
371 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 ...
19
votes
4answers
905 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 ...
19
votes
2answers
784 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 ...
19
votes
1answer
360 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 ...
18
votes
1answer
615 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 ...
18
votes
1answer
192 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 ...
18
votes
2answers
553 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 ...
17
votes
6answers
967 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 ...
17
votes
4answers
663 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
2answers
408 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 ...
16
votes
2answers
419 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 ...
15
votes
2answers
472 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 ...
15
votes
2answers
403 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 ...
14
votes
2answers
746 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 ...
14
votes
1answer
315 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
votes
2answers
521 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 ...
13
votes
3answers
697 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 ...
13
votes
1answer
370 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
256 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
2answers
566 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 ...
12
votes
2answers
489 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$ ...
12
votes
1answer
348 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.
12
votes
3answers
527 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
1k 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 ...
12
votes
1answer
245 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
2answers
390 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
1k 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
235 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
389 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 ...
11
votes
2answers
389 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 ...
11
votes
1answer
342 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 ...
11
votes
0answers
119 views

Hardness of optimal sorting

For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known. From a purely theoretical perspective, however, exactly optimal ...
10
votes
2answers
377 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 ...