14

Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example, $$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$$ is a statement that ...


12

There are (at least) two areas where existing barriers have little to say: ACC Lower Bounds There is no known barrier to proving that TC0 is not in (non-uniform) ACC -- other than the possibility that the separation may be false. It's unclear whether the Natural Proofs barrier should apply to ACC. The question boils down to: should we expect there to be ...


9

Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program. See the paper Expressing combinatorial optimization problems by Linear Programs, by Yannakakis. This result was improved recently by Fiorini, Massar, Pokutta, Tiwary, and De Wolf to drop the "symmetric" requirement in ...


8

This answer is for your "somewhat related question": In the following recent paper, Klee-Minty cubes were used explicitly to show that there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis ...


6

Razborov and Rudich's result in their natural proofs paper is quite general. It is not restricted to $\mathsf{P}$ vs. $\mathsf{NP}$. I personally like the clarity of the explanation in Stasys Jukna's recent book "Boolean Function Complexity: Advances and Frontiers": Definition 18.30. A function $G : \{0,1\}^l \to \{0,1\}^n$ with $l < n$ is called an $...


Only top voted, non community-wiki answers of a minimum length are eligible