Theoretical Computer Science

Excavator

 Excavator
Edit first post that was inactive for 6 months.
Awarded 295 times.
Major unsolved problems in theoretical computer science?
Awarded Nov 15 at 4:15
Can Lexicographic BFS be implemented in logspace?
Awarded Nov 9 at 4:25
Is the 3-sphere recognition problem NP-complete?
Awarded Nov 2 at 7:17
Problems complete for non-deterministic PSPACE
Awarded Sep 12 at 4:41
Is Bayes optimal RL of a finite set of DFAs feasible?
Awarded Aug 31 at 4:19
Defining finite sets inductively in a proof assistant?
Awarded Apr 26 at 4:25
What is the fastest algorithm for calculating nth term of Fibonacci sequence?
Awarded Mar 25 at 5:27
How can I prove formally semantic equivalence of programming languages?
Awarded Feb 21 at 4:33
Example use cases for induction-recursion
Awarded Feb 15 at 4:15
Provable statements about genetic algorithms
Awarded Feb 1 at 5:16
Computing the Syntactic Congruence
Awarded Jan 29 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
What would be the consequences of factoring being NP-complete?
Awarded Aug 10, 2020 at 4:55
Fast Reduction from RSA to SAT
Awarded Aug 5, 2020 at 4:16
What is the proof of this nonstandard version of Azuma's inequality?
Awarded Jul 10, 2020 at 4:04
How to write the introduction of a research paper?
Awarded Jul 4, 2020 at 6:32
Chernoff bound for weighted sums
Awarded Jun 30, 2020 at 5:52
Is the integer factorization problem harder than RSA factorization: $n = pq$?
Awarded Jun 17, 2020 at 5:10
Open problems on the frontiers of TCS
Awarded Jun 4, 2020 at 4:25
Funny TCS-related papers etc?
Awarded May 25, 2020 at 9:46
How to check if a number is a perfect power in polynomial time
Awarded May 19, 2020 at 4:21
A total language that only a Turing complete language can interpret
Awarded May 19, 2020 at 4:21
1
2 3 4 5

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.