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 ...
- 2,799
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 ...
- 371
13
votes
Accepted
Find odd-ranked numbers from a list
Lemma 1. Any comparison-based algorithm requires $\Omega(n\log n)$ comparisons in the worst case.
Proof sketch. Let $A$ be any comparison-based algorithm for the problem. Let $x=(x_1, x_2, \ldots, ...
- 9,595
13
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$.
...
- 4,788
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 ...
- 36.9k
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, ...
- 11k
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 ...
- 27.3k
11
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 ...
- 27.3k
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 ...
- 8,616
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 ...
- 36.9k
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 ...
- 50.9k
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 ...
- 5,350
9
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 ...
- 6,967
9
votes
Quadratic lower bound
I think this works, but I don't have time to check the details carefully right now. I'll sketch the ideas and finish later, or someone else can check.
Lemma 1. There is an $O(n\log n)$-time algorithm ...
- 9,595
8
votes
Is Dynamic Programming never weaker than Greedy?
I think the answer to my Question 1 is affirmative: there are matroids on which simple DP fails badly! That is, simple DP may be much worse than Greedy when trying to solve an optimization problem ...
- 6,685
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 ...
- 36.9k
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 ...
- 1,899
8
votes
Examples of the price of abstraction?
Reingold's algorithm solves undirected s-t connectivity in logarithmic space.
If we use a pointer machine, which maintains pointers as abstract objects without a total ordering, the problem can no ...
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 ...
- 3,256
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 ...
- 1,934
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 ...
- 3,416
7
votes
Accepted
Lower bounds for nonuniform circuits and oracles separating complexity classes
Yes, yes, and yes.
The basic idea is to consider the characteristic function of a language $L$
(the oracle you're constructing) at length $n$ as a string of length $2^n$
that will be an input to a ...
- 36.9k
7
votes
Progress on generalized star-height problem?
This answer is dedicated to the memory of Janusz (John) Antoni Brzozowski, who passed away on October 24, 2019.
John is certainly the person who made the star-height problems so famous. Indeed, at a ...
- 4,771
7
votes
Should GCT focus on $PSPACE\not\subseteq P/poly$?
Sure, in principle it could be used to separate the levels of $\mathsf{PH}$...the key thing is to find polynomial families complete for the relevant classes (or, at least polynomial families $f, g$ ...
- 36.9k
7
votes
Accepted
How fast can we find and disconnect roots in a forest?
The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. ...
7
votes
Accepted
Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$
This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N
- 1,596
7
votes
Maximum shortest word accepted by pushdown automata
(Answer inspired by Lamine's comment)
We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack ...
- 917
7
votes
Accepted
Quadratic lower bound
One can also find an $O(n \log n)$ time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.
- 27.3k
6
votes
Is it possible to use random restrictions to obtain a lower-bound for $\mathsf{TC^0}$?
See also the recent paper of Daniel Kane and Ryan Williams, Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-2 and Depth-3 Threshold Circuits (STOC 2016).
Ryan describes the paper as ...
- 14.3k
6
votes
Accepted
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
I believe that what you are looking for is a compact data structure supporting the rank operation. See...
https://en.m.wikipedia.org/wiki/Succinct_data_structure
Specifically, you can modify Emils (...
Only top scored, non community-wiki answers of a minimum length are eligible