Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lower-bounds]

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

8
votes
1answer
162 views

Separation of classes with different amounts of advice?

The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine. But give the Turing machine some advice and ...
19
votes
4answers
855 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 ...
5
votes
1answer
492 views

What is the running time of taking a limit?

I'm interested in finding the running time(s) for determining mathematical limits. For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$. I'd like to know more about algorithms for determining ...
13
votes
2answers
4k 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 ...
10
votes
1answer
815 views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
40
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 ...
23
votes
4answers
1k 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$,...
8
votes
2answers
772 views

Lower bound of checking graph connectivity on stream

I would like to check the status of the space lower bound for solving connectivity problem on stream in $p$ passes. The $\Omega(n/p)$ was stated in the literature but it seems to be for a slightly ...
21
votes
6answers
1k 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 ...
6
votes
5answers
279 views

What is/are the lower bounds for finding a something akin to complex residue?

Given a function $\sum_{i=-N}^N{c_i x^i}$: $f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$. The constant $c_0$ is desired, and we start with only $f(x)...
15
votes
1answer
503 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 ...
57
votes
4answers
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 ...
11
votes
1answer
577 views

Using Kolmogorov complexity to establish proof complexity lower bounds?

The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. ...
38
votes
9answers
3k 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 ...
14
votes
2answers
671 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 ...
10
votes
2answers
403 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 ...
1
vote
3answers
577 views

Major conjectures used to prove complexity lower bounds?

Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned ...
6
votes
4answers
742 views

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
110
votes
17answers
7k 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 elimination ...
13
votes
1answer
278 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 hyperplane,...
20
votes
1answer
403 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
2answers
602 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 ...
22
votes
2answers
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 ...
21
votes
2answers
513 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 ...
46
votes
4answers
4k views

What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?