Questions tagged [lower-bounds]
questions about lowerbounds on functions, usually the complexity of an algorithm or a problem
279
questions
11
votes
1
answer
480
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 ...
- 3,280
7
votes
2
answers
685
views
Communication lower bounds for partial boolean functions
There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy.
1) How do we ...
- 3,280
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
9
votes
1
answer
208
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 ...
- 969
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
5
votes
1
answer
504
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 ...
- 2,100
13
votes
2
answers
5k
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 ...
- 1,520
11
votes
1
answer
1k
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.
- 2,589
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.6k
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
8
votes
2
answers
1k
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 ...
- 763
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
6
votes
5
answers
284
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)...
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
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
12
votes
1
answer
683
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. ...
- 20.8k
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
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
10
votes
2
answers
437
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,945
1
vote
3
answers
610
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 ...
7
votes
4
answers
1k
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
- 20.8k
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 ...
14
votes
1
answer
345
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,...
- 9,596
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
18
votes
2
answers
925
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
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
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