Andy Drucker
  • Member for 11 years, 5 months
  • Last seen more than a month ago
What kind of mathematical background is needed for complexity theory?
34 votes

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

View answer
Why does randomness have stronger effect on reductions than on algorithms?
28 votes

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

View answer
Examples where the uniqueness of the solution makes it easier to find
Accepted answer
23 votes

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

View answer
Is optimally solving the n×n×n Rubik's Cube NP-hard?
21 votes

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

View answer
The cozy neighborhoods of "P" and of "NP-hard"
20 votes

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

View answer
If P = BQP, does this imply that PSPACE (= IP) = AM?
Accepted answer
18 votes

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

View answer
Lower bounds on Gaussian complexity
Accepted answer
17 votes

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

View answer
Above #P and counting search problems
Accepted answer
14 votes

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

View answer
Hardness of noisy Boolean functions
14 votes

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

View answer
Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
14 votes

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

View answer
DFA intersection in subquadratic space?
14 votes

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

View answer
Smallest Boolean circuit to generate a language
Accepted answer
11 votes

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

View answer
The cozy neighborhoods of "P" and of "NP-hard"
11 votes

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

View answer
Stochastic version of a strongly NP-Complete problem
10 votes

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

View answer
Are there known to exist functions with the following direct-sum property?
10 votes

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

View answer
What is the complexity of the fastest method of k-coloring any graph?
9 votes

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
Reduction SAT to a problem on a planar graph with as few vertices as possible
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
Fast convolution over small finite fields
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
Computing any information about Max-3SAT
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 $\...

View answer
Evidence that PPAD is hard?
8 votes

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

View answer
How hard is it to count the number of local optima for a problem in PLS?
Accepted answer
7 votes

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

View answer
Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)
Accepted answer
7 votes

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

View answer
Two Variants of NP
Accepted answer
6 votes

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.

View answer
Which results in complexity theory make essential use of uniformity?
Accepted answer
6 votes

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

View answer
Subset $k$-product
Accepted answer
5 votes

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

View answer
grover's algorithm
4 votes

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

View answer
research on systematically attacking multiple instances of undecidable problems
Accepted answer
2 votes

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

View answer
Comparison between the maximum clique and maximum biclique problem
Accepted answer
2 votes

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

View answer
On Random Self-reducible properties
Accepted answer
2 votes

I don't know the answer to Question (1)---I suspect there is no such reduction. But I have a couple of points to make. A non-adaptive random self-reduction (to the uniform distribution) is a poly-...

View answer
The complexity of recognizing optimal set systems for the V-C dimension
1 votes

This doesn't answer the question, but it might be helpful. Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented: ...

View answer