$\bullet$ The book Extremal Combinatorics, by Stasys Jukna, is IMO too little-known within the complexity community. It's a great collection of combinatorial techniques written largely with an eye to ...

First, let me comment on the specific case of the Valiant-Vazirani reduction; this will, I hope, help clarify the general situation. The Valiant-Vazirani reduction can be viewed/defined in several ...

3-SAT may be one such problem. Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT. (The speedup is exponential, although the reduction in the exponent is ...

A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, ...

Two comments, neither of which amount to an answer, but which may provide some useful further reading. 1) Schöning defined two classes of NP problems called the "Low Hierarchy" and the "High ...

Great question! Short answer: no implication like $$\mathsf{P} = \mathsf{BQP} \Rightarrow \mathsf{IP} = \mathsf{AM}$$ is known; but that doesn't mean it's not worth trying to prove... I would ...

This appears to be a very hard problem, related to a more widely-studied one. Suppose we consider a square invertible matrix A, and define c(A) as the minimal number of elementary row operations ...

If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of ...

for Question 1, the answer is Yes, and can be shown as follows. (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at ...

Lattice problems are a good source of candidates. Given a basis for a lattice $L$ in $R^n$, one can look for a nonzero lattice vector whose ($\ell_2$) norm is smallest possible; this is the '...

Dick Lipton and colleagues recently worked on this problem, and Lipton blogged about it here: http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/ It appears that doing ...

I will point out a simple connection to nondeterministic circuits, and comment briefly on cryptographic hardness. For $S \subseteq \{0, 1\}^n$, define the image complexity, denoted $imc(S)$, as the ...

The hypothesis that the Polynomial Hierarchy does not collapse has been one of the most fertile paths to discovery in complexity theory. Many of these results can be phrased as saying that specific ...

A first observation is that the stochastic version of an optimization problem will always be at least as hard as the deterministic version, since fixed constant values in an optimization instance are ...

There’s another result that further constrains the possibilities for the kind of direct-sum phenomenon you're looking for. A well-known early result of Shannon (tightened by Lupanov) showed that all ...

There are non-obvious improvements over simple brute-force search for $k$-coloring (and for many other NP-hard problems). The obvious approach would take roughly $k^n$ time, but one can do it in time $... View answer 9 votes You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; ... View answer 8 votes A recent paper by Alexey Pospelov appears to give the state of the art. (It isn't the first to achieve the bounds I'll quote, but it achieves them in a unified way for arbitrary fields, and equally ... View answer 8 votes I believe that we can show: Claim. There's a value$0 < c < 1$such that the following is true. Suppose there's a deterministic poly-time algorithm that, given an$m$-clause 3-SAT instance$\...

Buhrman et al. showed there is an oracle relative to which all TFNP functions are poly-time computable, yet the Polynomial Hierarchy is infinite. TFNP is a class which contains PPAD and its cousins. ...

I can partially answer your question: counting the local optima of a PLS-complete search problem can indeed be #P-hard. First, as Yoshio points out, there is a search problem $P_1$ in PLS whose ...

The problem is coNP-complete and so unlikely to have a poly-time algorithm. (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.) Here is a simple reduction from ...

For Class 2, one somewhat silly example is R(p, a) = {p is an integer polynomial, a is in the range of p, and |a| = O(poly(|p|)}. R is in Class 2 but undecidable.

We suspect Permanent requires superpolynomial-size circuits (in either of the arithmetic or Boolean models). However, if we consider Boolean circuits with threshold gates, currently we can only prove ...

Over the integers, it looks like Subset Product is at least as hard as the Exact Cover problem http://en.wikipedia.org/wiki/Exact_cover parametrized by the number of sets used in the exact cover. (...

The Grover algorithm in its simplest form searches a list of $N$ bits for an occurrence of a bit with value 1. If a 1 is present, Grover will find one with high probability in $O(\sqrt{N})$ steps. ...

Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?". These algorithms (which may be ...

Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by R B), here is a paper whose abstract gives some detailed information about the ...