15 votes
Accepted

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$. ...
Huck Bennett's user avatar
  • 4,868
13 votes
Accepted

Law of the Excluded Middle in complexity theory

There are several other non-constructive arguments that work along similar Karp-Lipton-esque lines, such as Santhanam's proof (STOC 2009) that $PromiseMA$ is not in $SIZE(n^k)$ for some $k$, and ...
Ryan Williams's user avatar
8 votes

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

To give an alternative (slightly older) reference to the one proposed in another answer, the result "If the SETH is true, then $n$-variable CSP over alphabets of size $d$ cannot be solved in time ...
Michael Lampis's user avatar
5 votes

Law of the Excluded Middle in complexity theory

I finally managed to track down the paper that I was struggling to recall. Why are Proof Complexity Lower Bounds Hard? by Ján Pich and Rahul Santhanam, FOCS 2019. Their main result is: Theorem 1. ...
Timothy Chow's user avatar
  • 7,550
4 votes
Accepted

Lower bound for constant degree monotone arithmetic circuits

The Nisan--Wigderson polynomials are one example. That is, let $$ \mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}. $$ Let $k$ ...
Robert Andrews's user avatar
3 votes
Accepted

Confusion about lower bounds and upper bounds in learning theory

I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed. To elaborate on Usul's comment. Upper bounds are of the ...
Aryeh's user avatar
  • 10.5k
3 votes

How can I show a Gap-P problem is outside #P

This area has grown immensely in the 12 years since I asked the question. In particular, Ikenmeyer, Pak and Panova have shown that the squares of symmetric group characters are not in #(P), unless the ...
David E Speyer's user avatar
3 votes
Accepted

Is there a conditional lower bound for the k max subarray sum problem?

In "Computing Maximum-Scoring Segments Optimally" by Fredrik Bengtsson & Jingsen Chen the authors describe an $O(n)$ algorithm.
orlp's user avatar
  • 885
2 votes

Is there a lower bound for the problem of finding the best straight line partition

This is not a complete answer, but is too long for a comment. Consider the following generalization of your problem: (Maximum Weight Halfplane) We are given a set $S$ of $m$ weighted points in the ...
Tassle's user avatar
  • 881
1 vote

Arithmetic Circuit Hierarchy?

This question has a somewhat trivial answer because the polynomial $x^{2^s}$ requires $s$ multiplications, so you can just take $h = x_1^{2^{f(n)}}$. This is one of the reasons why in algebraic ...
Vladimir Lysikov's user avatar

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