Theoretical Computer Science

Necromancer

 Necromancer
Answer a question more than 60 days later with score of 5 or more. This badge can be awarded multiple times.
Awarded 859 times.
What circuit depth is enough to compute a log-space complete problem?
Awarded yesterday
An analog of DP for the second level of the polynomial hierarchy
Awarded Sep 21 at 8:52
What is the smallest Turing machine where it is unknown if it halts or not?
Awarded Sep 19 at 21:47
Why most of the top TCS conferences are not double-blind?
Awarded Sep 18 at 1:40
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
Awarded Sep 13 at 12:21
Is there any inherently ambiguous indexed language?
Awarded Sep 2 at 0:46
Complexity results for Lower-Elementary Recursive Functions?
Awarded Jun 29 at 13:08
Solid applications of category theory in TCS?
Awarded Jun 9 at 15:10
What are the #P-complete subfamilies of #2-SAT?
Awarded May 24 at 12:52
Is there a complexity theory analogue of Rice's theorem in computability theory?
Awarded Apr 21 at 2:34
What is the fastest algorithm for calculating nth term of Fibonacci sequence?
Awarded Mar 21 at 20:42
Does this game terminate?
Awarded Mar 16 at 12:06
Is there a generalization of the GO game that is known to be Turing complete?
Awarded Feb 8 at 19:11
Most efficient inplace merge algorithms (stable and unstable)
Awarded Feb 5 at 8:46
Proof of Levenshtein distance
Awarded Jan 23 at 6:18
Intersection non-emptiness problem over regular expressions and NFA
Awarded Jan 3 at 5:12
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
Awarded Jan 2 at 13:56
Why do TCS papers have author names in alphabetical order of their surnames?
Awarded Dec 6, 2022 at 16:52
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Awarded Nov 22, 2022 at 19:50
Can typed lambda calculi express *all* algorithms below a given complexity?
Awarded Nov 14, 2022 at 9:35
Constant in Komlos conjecture
Awarded Nov 11, 2022 at 15:33
Notion of "quotient" or "inverse" for recognizable tree languages?
Awarded Nov 4, 2022 at 8:28
What's the expressive power of Simply Typed Lambda calculus?
Awarded Nov 3, 2022 at 7:16
Efficiently computable variants of Kolmogorov complexity
Awarded Oct 27, 2022 at 20:40
Reverse Chernoff bound
Awarded Oct 12, 2022 at 19:30
Have any generalizations of maximum weight matching been studied?
Awarded Oct 9, 2022 at 18:35
Are there NP-complete problems with polynomial expected time solutions?
Awarded Sep 22, 2022 at 16:56
How is Lambda Calculus a specific type of Term Writing system?
Awarded Sep 15, 2022 at 7:21
The number of cliques in a graph: the Moon and Moser 1965 result
Awarded Aug 20, 2022 at 13:00
Solid applications of category theory in TCS?
Awarded Jul 27, 2022 at 14:51
The existence of planar distance preserver?
Awarded Jul 7, 2022 at 0:25
Does Memcomputing really solve an NP-complete problem?
Awarded Jul 5, 2022 at 23:04
Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem
Awarded Jun 30, 2022 at 16:10
An analog of DP for the second level of the polynomial hierarchy
Awarded May 10, 2022 at 15:37
minimizing size of regular expression
Awarded Mar 18, 2022 at 21:21
Is linearizability equivalent to consensus problem?
Awarded Jan 16, 2022 at 23:36
what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?
Awarded Dec 30, 2021 at 23:16
Barriers to show $P=NP$
Awarded Nov 23, 2021 at 19:50
Can we approximate the number of words accepted by an NFA?
Awarded Nov 8, 2021 at 14:26
Is there an efficient beta-equivalence algorithm?
Awarded Nov 5, 2021 at 17:10
Common false beliefs in theoretical computer science
Awarded Oct 19, 2021 at 21:41
Multimodal logic with quantification over modal operators
Awarded Oct 8, 2021 at 19:06
Proof of $DLOGTIME-CC^0 = MOD[<,bit]$
Awarded Sep 30, 2021 at 21:32
Common false beliefs in theoretical computer science
Awarded Sep 28, 2021 at 8:26
Busy Beaver Equivalent for the Untyped Lambda Calculus
Awarded Aug 23, 2021 at 14:02
What Books Should Everyone Read?
Awarded Aug 4, 2021 at 5:50
What videos should everybody watch?
Awarded Aug 3, 2021 at 5:51
Is there a result in computability theory that does not relativize?
Awarded Aug 2, 2021 at 12:21
What is the best place to get BibTeX entries for ICLR and other machine learning papers?
Awarded Jul 30, 2021 at 22:40
Are there any open problems left about DFAs?
Awarded Jul 28, 2021 at 13:17
Status of PP-completeness of MAJ3SAT
Awarded Jul 8, 2021 at 22:21
NLOGTIME versus $\exists$DLOGTIME
Awarded Jul 5, 2021 at 10:17
Separating words with random DFAs
Awarded Jun 26, 2021 at 10:51
The complexity of determining if a fixed graph is a minor of another
Awarded May 31, 2021 at 17:34
Most memorable CS paper titles
Awarded May 16, 2021 at 18:41
Formally Verified Complexity Theory
Awarded Apr 28, 2021 at 15:15
$RL=L$ Progress Since 2006
Awarded Apr 28, 2021 at 4:35
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
Awarded Apr 13, 2021 at 1:46
Why SHA-224 and SHA-256 use different initial values?
Awarded Apr 11, 2021 at 20:01
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
Awarded Apr 7, 2021 at 23:27
1
2 3 4 5
…
15

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.