Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Chris Beck's user avatar
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,878
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, ...
Neal Young's user avatar
  • 10.8k
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
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 ...
Ryan Williams's 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 ...
David Eppstein's 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 ...
Joshua Grochow's 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 ...
Or Meir's user avatar
  • 5,615
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 ...
Lance Fortnow's user avatar
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 ...
Jeffrey Shallit's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
daniello's user avatar
  • 3,266
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 ...
Lieuwe Vinkhuijzen'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
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$ ...
Joshua Grochow's user avatar
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 ...
J.-E. Pin's user avatar
  • 4,831
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. ...
Dmitri Urbanowicz's user avatar
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
Avi Tal's user avatar
  • 1,606
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 ...
Antimony's user avatar
  • 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.
Ryan Williams's user avatar
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 ...
Yuval Filmus's user avatar
  • 14.5k
6 votes
Accepted

How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

The "dual bin packing problem" is more commonly referred to as the Multiple Knapsack problem. One can show that $ALG \ge (1-1/e) OPT_b$ assuming an optimal algorithm for the Knapsack problem is used ...
Chandra Chekuri's user avatar
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 $...
Michael Blondin's user avatar
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 ...
jbapple's user avatar
  • 11.2k
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 $\...
Yuval Peres's user avatar
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 ...
Joshua Grochow's user avatar
5 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, ...
Jason Gaitonde's user avatar
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) ...
Michael Wehar'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

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