Theoretical Computer Science

Good Answer

 Good Answer
Answer score of 25 or more. This badge can be awarded multiple times.
Awarded 643 times.
Recent advances in computer science since 2010?
Awarded 2 days ago
What is the big version of NC?
Awarded 2 days ago
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
Awarded Sep 21 at 15:49
What would be the consequences of PH=PSPACE?
Awarded Aug 8 at 10:47
Why does Coq have Prop?
Awarded Jul 7 at 15:37
Book on Probability
Awarded Jun 4 at 12:57
Deciding emptiness of intersection of regular languages in subquadratic time
Awarded May 31 at 9:22
Universal Function approximation
Awarded Apr 26 at 23:41
How to make the Lambda Calculus strong normalizing without a type system?
Awarded Apr 17 at 3:25
Theoretical Computer Science vs other Sciences?
Awarded Mar 19 at 22:41
What constitutes denotational semantics?
Awarded Mar 16 at 13:03
Can any program be implemented mechanically?
Awarded Jan 21 at 20:11
What's the status of Babai's Graph isomorphism result?
Awarded Jan 4 at 1:33
is "spaghetti sort" really O(n) (even as a thought experiment) ?
Awarded Dec 25, 2022 at 18:10
How to publish a paper?
Awarded Dec 25, 2022 at 8:12
NP-hard problems on trees
Awarded Nov 9, 2022 at 7:20
NP-hard problems on trees
Awarded Nov 8, 2022 at 10:25
Interactive proofs for levels of the polynomial hierarchy
Awarded Oct 21, 2022 at 22:33
How does the BosonSampling paper avoid easy classes of complex matrices?
Awarded Oct 14, 2022 at 0:15
Shallow versus Deep Embeddings
Awarded Sep 28, 2022 at 16:35
Can a computer simulate itself as part of a simulated world?
Awarded Aug 30, 2022 at 8:21
Techniques for showing that problem is in hardness "limbo"
Awarded Aug 18, 2022 at 20:33
Concise introduction to algorithms for mathematicians
Awarded Aug 2, 2022 at 7:42
Oracle Construction for Grover's Algorithm
Awarded May 18, 2022 at 17:57
Are there languages that are not in RE nor CO-RE?
Awarded Apr 5, 2022 at 15:41
Major unsolved problems in theoretical computer science?
Awarded Mar 15, 2022 at 1:56
Empirical results in CS papers
Awarded Jan 31, 2022 at 13:06
Is finding Logspace reductions harder than P reductions?
Awarded Jan 24, 2022 at 23:50
Are research papers hard to read?
Awarded Nov 9, 2021 at 13:11
Is Descriptive Complexity dead?
Awarded Nov 5, 2021 at 16:46
What's the relation and difference between Calculus of Inductive Constructions and Intuitionistic Type Theory?
Awarded Oct 9, 2021 at 8:55
Symbolic Execution is a case of Abstract Interpretation?
Awarded Oct 7, 2021 at 12:21
Do any quantum algorithms improve on classical SAT?
Awarded Sep 24, 2021 at 11:57
EXPSPACE-complete problems
Awarded Sep 23, 2021 at 10:07
Does $VP \neq VNP$ imply $P \neq NP$?
Awarded Aug 25, 2021 at 12:50
Theoretical explanations for practical success of SAT solvers?
Awarded May 22, 2021 at 16:57
Is it NP-hard to play international draughts correctly?
Awarded May 10, 2021 at 17:53
What are natural examples of non-relativizable proofs?
Awarded Mar 21, 2021 at 15:27
Why would one ever use an Octree over a KD-tree?
Awarded Feb 15, 2021 at 19:32
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Awarded Feb 8, 2021 at 6:42
Algebra oriented branch of theoretical computer science
Awarded Jan 19, 2021 at 19:50
Merging Two Binary Search Trees
Awarded Jan 13, 2021 at 13:21
What kind of mathematical background is needed for complexity theory?
Awarded Dec 19, 2020 at 8:56
Research and open challenges in Programming Language Theory
Awarded Nov 22, 2020 at 15:01
Polynomial-time algorithms with huge exponent/constant
Awarded Oct 22, 2020 at 9:04
Has parameterized complexity led to better algorithms?
Awarded Oct 12, 2020 at 20:05
What does 'gadget' mean in NP-hard reduction?
Awarded Oct 12, 2020 at 15:11
What would it mean to disprove Church-Turing thesis?
Awarded Oct 10, 2020 at 17:11
NP-hard problems on trees
Awarded Oct 6, 2020 at 7:57
For which problems in P is it easier to verify the result than to find it?
Awarded Oct 6, 2020 at 7:57
When does "X is NP-complete" imply "#X is #P-complete"?
Awarded Sep 8, 2020 at 5:10
Translating SAT to HornSAT
Awarded Aug 31, 2020 at 2:57
Optimal algorithm for finding the girth of a sparse graph?
Awarded Aug 6, 2020 at 6:35
Applications of topology to computer science
Awarded Jul 31, 2020 at 1:59
Solid applications of category theory in TCS?
Awarded Jul 29, 2020 at 11:02
Finding the shortest path in the presence of negative cycles
Awarded Jul 20, 2020 at 13:47
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Awarded May 24, 2020 at 16:26
Lipton's most influential results
Awarded May 24, 2020 at 14:25
Uses of algebraic structures in theoretical computer science
Awarded May 12, 2020 at 5:27
Complexity of the Fisher-Yates Shuffle Algorithm
Awarded May 5, 2020 at 11:36
1
2 3 4 5
…
11

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.