2022 Developer Survey is open! Take survey.
32 votes
Accepted

Nontrivial algorithm for computing a sliding window median

Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $...
user avatar
21 votes
Accepted

How many negations do we need to compute monotone functions?

Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the ...
user avatar
  • 2,789
19 votes
Accepted

Properties expressible in 2-CNF or 2-SAT

A family of bitvectors is the class of solutions to a 2-SAT problem if and only if it has the median property: if you apply the bitwise majority function to any three solutions you get another ...
user avatar
17 votes
Accepted

Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Hmm, turns out there's actually an matching upper bound that isn't too hard: To produce the truth table $HALT_n$ in a finite amount of time, the only information that is needed is the number of ...
user avatar
15 votes
Accepted

Ackermann Function Time Complexity

There are "natural" problems hard for Ackermannian time; in fact there is a growing body of literature on the subject. A place to start is the survey in Section 6 of Complexity Hierarchies Beyond ...
user avatar
  • 3,314
14 votes
Accepted

Why is HAMILTONIAN CYCLE so different from PERMANENT?

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone ...
user avatar
13 votes
Accepted

Complexity lower bound of finding the factorial of a number

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over ...
user avatar
  • 4,400
13 votes

How to prove that USTCONN requires logarithmic space?

The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$...
user avatar
  • 2,267
12 votes
Accepted

Lower bound for NFA accepting 3 letter language

The bounds... We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the ...
user avatar
11 votes

Better lower bounds than 3n for non-boolean functions?

here are new results on this said to be the 1st in ~3 decades and some brief commentary A better-than-3n lower bound for the circuit complexity of an explicit function / Find, Golovnev, Hirsch, ...
user avatar
  • 10.8k
11 votes

Uncertainties in GCT program

It depends what you count as "the GCT program." Consider the specific suggestion (GCT I, GCT II) to use the vanishing/nonvanishing of certain multiplicities in the orbit closures of the determinant ...
user avatar
11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a ...
user avatar
10 votes

Properties expressible in 2-CNF or 2-SAT

Let $P(x_1,\ldots,x_n)$ be a property on $n$ variables. Suppose that there is a 2CNF formula $\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ such that $$P(x_1,\ldots,x_n) \Leftrightarrow \exists y_1 \cdots \...
user avatar
  • 14.1k
9 votes

Nontrivial algorithm for computing a sliding window median

Edit: This algorithm is now presented here: http://arxiv.org/abs/1406.1717 Yes, to solve this problem it is sufficient to perform the following operations: Sort $n/k$ vectors, each with $k$ elements....
user avatar
9 votes
Accepted

Time complexity of d-dimensional convex hull

I don't know any nontrivial lower bounds other than the $\Omega(n\log n)$ algebraic-decision-tree lower bound for two dimensions, which also extends to larger $d$. As for upper bounds: In 3d, the ...
user avatar
9 votes
Accepted

Deterministic communication complexity vs partition number

This question has just been resolved! As I mentioned, it was known that $Pn(f) \leq D(f) \leq (Pn(f))^2$, but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there ...
user avatar
9 votes

Separating Logspace from Polynomial time

It made my day when my friend James told me that this thread from long ago was rekindled. Thank you for that. Also, I had an urge to share some interesting references that are relevant to L vs Log(...
user avatar
9 votes
Accepted

Nondeterministic communication complexity of set disjointness?

$N^1(DISJ_n) \geq n$. The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. ...
user avatar
9 votes

What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?

$S^p_2$ and $PP$ are both known not to have $n^k$-circuits for any fixed k and there is no known containment between them. Details in my blog post. Update: As Rickey Demer points out, these results ...
user avatar
9 votes
Accepted

Are arithmetic circuits weaker than boolean?

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given ...
user avatar
9 votes
Accepted

Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution ...
user avatar
9 votes
Accepted

Where can I find examples of error correcting codes of the following types?

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many ...
user avatar
  • 5,055
8 votes

Separating Logspace from Polynomial time

[1] proves a lower bound for instances of mincost-flow whose bit-sizes are sufficiently large (but still linear) compared to the size of the graph, and furthermore proved that if one could show the ...
user avatar
8 votes
Accepted

equivalent way(s) of expressing P=?NP problem in linear programming?

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 ...
user avatar
  • 1,713
8 votes
Accepted

Implications of a recent negative result to geometric complexity

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an ...
user avatar
8 votes

Lower bounds for noncommutative arithmetic circuits with exact division?

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials. They ...
user avatar
8 votes
Accepted

Reference request: complexity of $k$-partite $k$-SAT

Claim: If there exists an $\epsilon > 0$ such that for every $k'$, $k'$-partite $k'$-SAT can be solved in $2^{n(1-\epsilon)}$ time, then SETH fails. Proof: Suppose such an algorithm exists. We ...
user avatar
  • 3,186
8 votes
Accepted

What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Virginia Vassilevska Williams lectured at a bootcamp (link to outline) at the Simons Institute, and presents what may be your memory in the introductory video. The whole workshop is worthwhile; the ...
user avatar
8 votes

Maximum shortest word accepted by pushdown automata

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because ...
user avatar
7 votes
Accepted

Any polynomial which is hard to count but easy to decide?

(I am posting my comments as an answer in response to the OP’s request.) As for Question 1, let fn: {0,1}n→ℕ be a family of functions whose arithmetic circuit requires exponential size. Then so does ...
user avatar
  • 16.2k

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