# Tag Info

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$. ...
• 4,868
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 ...
• 27.5k

### 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 ...
• 3,698

### 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. ...
• 7,550
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$ ...
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 ...
• 10.5k

### 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 ...
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.
• 885
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 ...
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 ...