# Questions tagged [lower-bounds]

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

233 questions
Filter by
Sorted by
Tagged with
1k views

### Highest lower bound on NP problems (TSP)

I'll try another question that I haven't been able to find almost any kind of information about, thanks a lot for any kind of pointers or explanations. Is there a list of the proven lower bounds of ...
2k 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 ...
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 ...
349 views

### Stronger Lower Bounds on Nondeterministic Multiparty Communication

This is a continuation of my previous question on Lower bounds for Nondeterministic Multiparty Communication. From the answer, the $\mu^\infty$ norm lower bounds nondeterministic multiparty ...
436 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 ...
569 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 ...
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 ...
2k 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 ...
167 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 ...
900 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 ...
494 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 ...
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 ...
851 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.
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 ...
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$,...
869 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 ...
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 ...
282 views

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 ...