Skip to main content
Theoretical Computer Science

Excavator

 Excavator
Edit first post that was inactive for 6 months.
Awarded 304 times.
What would be the consequences of $\mathsf{PH=PSPACE}$?
Awarded Jul 22 at 4:47
What videos should everybody watch?
Awarded Jun 24 at 4:56
Gentle introduction to graph isomorphism for bounded valance graphs
Awarded Jun 18 at 4:10
what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?
Awarded Apr 10 at 5:05
How to think about coherent spaces intuitively?
Awarded Mar 4 at 4:35
Explaining monad transformers in categorical terms
Awarded Feb 26 at 6:18
What papers should everyone read?
Awarded Feb 5 at 4:02
Is a CEK machine an implementation of a CESK machine?
Awarded Jan 19 at 4:04
Are there any implementations of a graph crossing algorithm?
Awarded Jan 13 at 5:50
List of TCS conferences and workshops
Awarded Jan 9 at 4:35
Major unsolved problems in theoretical computer science?
Awarded Nov 15, 2023 at 4:15
Can Lexicographic BFS be implemented in logspace?
Awarded Nov 9, 2023 at 4:25
Is the 3-sphere recognition problem NP-complete?
Awarded Nov 2, 2023 at 7:17
Problems complete for non-deterministic PSPACE
Awarded Sep 12, 2023 at 4:41
Is Bayes optimal RL of a finite set of DFAs feasible?
Awarded Aug 31, 2023 at 4:19
Defining finite sets inductively in a proof assistant?
Awarded Apr 26, 2023 at 4:25
What is the fastest algorithm for calculating nth term of Fibonacci sequence?
Awarded Mar 25, 2023 at 5:27
How can I prove formally semantic equivalence of programming languages?
Awarded Feb 21, 2023 at 4:33
Example use cases for induction-recursion
Awarded Feb 15, 2023 at 4:15
Provable statements about genetic algorithms
Awarded Feb 1, 2023 at 5:16
Computing the Syntactic Congruence
Awarded Jan 29, 2023 at 4:20
Can the mutual information of a "cell" be negative?
Awarded Dec 22, 2022 at 5:21
Algorithms from the Book
Awarded Dec 1, 2022 at 4:30
NP-hard problems on trees
Awarded Nov 9, 2022 at 4:51
Examples of the price of abstraction?
Awarded Oct 27, 2022 at 6:47
Interactive proofs for levels of the polynomial hierarchy
Awarded Oct 18, 2022 at 4:26
Polynomial-time algorithms with huge exponent/constant
Awarded Jul 14, 2022 at 4:35
Converse form of Chernoff bound
Awarded May 30, 2022 at 4:05
Pointers for CS applications of logic
Awarded Apr 24, 2022 at 4:46
Find all pairs of values that are close under Hamming distance
Awarded Apr 1, 2022 at 4:03
Dynamic programming and shortest path problem
Awarded Apr 1, 2022 at 4:03
Combinators for the Primitive Recursive Functions
Awarded Jan 27, 2022 at 4:36
For which problems in P is it easier to verify the result than to find it?
Awarded Nov 30, 2021 at 4:07
Multiplying n polynomials of degree 1
Awarded Oct 21, 2021 at 4:07
What is the best text of computation theory/theory of computation?
Awarded Oct 20, 2021 at 21:16
Programming language supporting infinitary rewriting of regular term graphs?
Awarded Sep 15, 2021 at 5:32
How would I go about learning the underlying theory of the Coq proof assistant?
Awarded Aug 19, 2021 at 4:03
List of TCS conferences and workshops
Awarded Aug 7, 2021 at 4:26
a geometric variant of k-medians. NP-hard or in P?
Awarded Jun 16, 2021 at 4:25
Is there a good notion of non-termination and halting proofs in type theory?
Awarded Jun 13, 2021 at 6:27
Regular languages from category-theoretical point of view
Awarded Apr 27, 2021 at 5:01
Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?
Awarded Apr 21, 2021 at 5:42
"Guarded" negative occurrences in definition of inductive types, always bad?
Awarded Mar 23, 2021 at 6:19
Is the following graph optimization problem approximable within a constant factor?
Awarded Mar 18, 2021 at 5:37
What is the proof for the inconsistency of impredicativity + excluded middle + large elimination in type theory
Awarded Mar 9, 2021 at 4:17
how to swap the value of two variables without an auxilary (helping) variable
Awarded Mar 6, 2021 at 4:41
How can I find the second cheapest spanning tree?
Awarded Jan 30, 2021 at 4:11
Fastest known deterministic algorithm for the undirected Graph Isomorphism problem
Awarded Jan 29, 2021 at 4:11
$⊕P$-completeness of $⊕2SAT$
Awarded Jan 29, 2021 at 4:11
canonical complete problems for $\Delta^P_n$
Awarded Jan 19, 2021 at 5:05
What are graph grammars?
Awarded Jan 11, 2021 at 4:35
Complexity of convolution in the max/plus ring
Awarded Jan 10, 2021 at 4:10
Simple model of computation with homoiconicity
Awarded Jan 7, 2021 at 5:20
What are some good introductory books on type theory?
Awarded Jan 2, 2021 at 6:35
NP complete graph problems about structural properties
Awarded Jan 2, 2021 at 6:35
Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$
Awarded Dec 13, 2020 at 5:46
Implications of unprovability of $P\neq NP$
Awarded Oct 23, 2020 at 4:26
Reverse Chernoff bound
Awarded Oct 15, 2020 at 4:11
What are the limits of computation in this universe?
Awarded Aug 18, 2020 at 4:26
What are the simplest turing-complete systems?
Awarded Aug 15, 2020 at 7:12
1
2 3 4 5 6