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
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$.
...
- 5,103
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, ...
- 10.9k
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 ...
- 27.5k
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.5k
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,741
9
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 ...
- 5,101
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,645
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,985
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 ...
- 10.9k
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,276
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
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 ...
- 2,184
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,722
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$ ...
- 37.8k
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,616
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
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.5k
6
votes
Petri net termination
Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $...
- 2,592
6
votes
Accepted
Can three stacks be implemented in one array, with O(1) push/pop time?
Fredman and Goldsmith showed in "Three Stacks" (Journal of Algorithms, 1994) that $\Theta(n^\varepsilon)$ bits of wasted space is achievable. It is also the minimum needed for arrays of size at least ...
- 11.2k
6
votes
Accepted
Big-O bounds on the k-th largest element of iid Gaussians
This is not a complete answer by any means, but just a quick estimate on $\mathbb{E}[\sum_{i=1}^k X_{[i]}]$ that is slightly better than the trivial bound of $O(k\sqrt{\log n})$. If this is your goal, ...
- 995
6
votes
Accepted
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\...
- 451
5
votes
Accepted
Application of weak determinantal identities to GCT?
Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the ...
- 37.8k
5
votes
Accepted
Maximum shortest word accepted by pushdown automata
Counter Automata
I was a co-author for a paper where we investigated this problem for counter automata. We were able to show that the length of a shortest string accepted by an $n$-state (non-empty) ...
- 5,157
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. ...
- 7,590
4
votes
Accepted
Hardness of Subgraph isomorphism problem for sparse pattern graph
It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know ...
- 3,276
4
votes
Succinct data structures survey?
There is now a book on the subject: Compact Data Structures: A Practical Approach, by Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586
- 141
4
votes
Accepted
The SQ argument in Balazs Szorenyi's paper
This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these ...
- 18.2k
4
votes
Problem in deterministic time $n^p$ and not lower
For many years researchers have studied pebbling problems and emptiness/reachability problems. Some of these problems have known unconditional resource lower bounds.
Such a problem $X$ is typically ...
- 5,157
Only top scored, non community-wiki answers of a minimum length are eligible