Theoretical Computer Science

Editor

 Editor
First edit.
Awarded 4344 times.
Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?
Awarded Nov 23 at 16:31
How to calculate processor throughput boundary in CSAPP?
Awarded Nov 22 at 11:22
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
Awarded Nov 20 at 8:47
Technical limitations of Turing machines due to the input and output encoding of values
Awarded Nov 18 at 19:40
Technical limitations of Turing machines due to the input and output encoding of values
Awarded Nov 18 at 13:27
(post deleted or otherwise unavailable)
Awarded Nov 18 at 12:47
(post deleted or otherwise unavailable)
Awarded Nov 16 at 20:10
What’s the complexity of this decision problem with bit shifting?
Awarded Nov 16 at 3:28
Learning arithmetic series
Awarded Nov 13 at 21:42
Unable to understand the Sample complexity of PAC learning
Awarded Nov 9 at 13:11
Known Variant of Set Cover?
Awarded Nov 8 at 21:15
Does PAC learnable imply agnostic PAC learnable for binary classification tasks?
Awarded Nov 4 at 9:05
Is the 3-sphere recognition problem NP-complete?
Awarded Nov 1 at 18:06
Representation of binary strings by graphs and hypergraphs
Awarded Oct 30 at 13:45
(post deleted or otherwise unavailable)
Awarded Oct 29 at 14:16
The hardness of active learning with fixed budget
Awarded Oct 21 at 16:05
Self Referential Undecidability Construed as Incorrect Questions
Awarded Oct 19 at 11:11
(post deleted or otherwise unavailable)
Awarded Oct 17 at 15:08
Deciding Satisfiability of a "Universal" Second-Order Logic Formula
Awarded Oct 16 at 8:56
Bottom up TSP solution?
Awarded Oct 12 at 21:06
How to calculate the data transmission rate with path-loss?
Awarded Oct 8 at 9:18
A variation of the longest path problem
Awarded Oct 6 at 20:16
How to prove `(∀(M : Monad). ∀a. a → M a) ≅ 𝟙`
Awarded Oct 4 at 17:28
Is Gödel's speed-up theorem an instance of Blum's speedup theorem?
Awarded Oct 3 at 23:25
Fast algorithms for time bounded Kolmogorov complexity
Awarded Sep 24 at 13:36
Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?
Awarded Sep 23 at 14:15
Recent advances in computer science since 2010?
Awarded Sep 23 at 9:51
What are the consequences of $BPP \neq P$?
Awarded Sep 22 at 6:15
What is the smallest Turing machine where it is unknown if it halts or not?
Awarded Sep 17 at 21:21
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
Awarded Sep 14 at 12:08
How does NP-completess of decision problems relate to NP-completeness of search problems?
Awarded Sep 13 at 23:32
A contradiction in the realm of quantum digital and analog computation
Awarded Sep 11 at 12:35
What is the type of the lambda term $\lambda a.a(\lambda yt.t)(ya)$?
Awarded Sep 8 at 16:36
Complexity of the inevitability problem over monoids
Awarded Sep 6 at 23:27
Linear Programming Sensitivity to Matrix
Awarded Sep 6 at 22:55
(post deleted or otherwise unavailable)
Awarded Sep 6 at 5:31
Power of non-implicationally-complete Frege systems and Boolean equational calculus
Awarded Sep 5 at 23:05
(post deleted or otherwise unavailable)
Awarded Sep 5 at 22:06
Is Bayes optimal RL of a finite set of DFAs feasible?
Awarded Aug 30 at 12:32
Algebra in complexity theory
Awarded Aug 28 at 21:10
Hardness of maximization of a univariate polynomial (as a function of its degree)
Awarded Aug 28 at 15:41
How "Algebrization" is "A New Barrier in Complexity Theory"?
Awarded Aug 22 at 15:26
Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover
Awarded Aug 21 at 21:36
(post deleted or otherwise unavailable)
Awarded Aug 21 at 19:55
Structural Complexity Theory References
Awarded Aug 21 at 4:35
Semi-Thue systems and deterministic computation
Awarded Aug 19 at 12:26
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
Awarded Aug 18 at 21:49
Overlap operator for simple ( regex-like ) Patterns
Awarded Aug 18 at 7:36
Name and complexity of a stone placement puzzle
Awarded Aug 17 at 15:11
Application LCL definition to vertex coloration
Awarded Aug 17 at 13:57
(post deleted or otherwise unavailable)
Awarded Aug 16 at 20:05
Running time analysis of problems with a variable in problem definition
Awarded Aug 13 at 23:08
Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent
Awarded Aug 10 at 21:15
Why do we use Hoeffding inequality in UCB approach to drive the confidence set in multi-armed bandit problem?
Awarded Aug 10 at 21:07
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Awarded Aug 8 at 10:34
What is formal definition of non-deterministic algorithm in context of primitive/general recursion?
Awarded Aug 4 at 18:25
Is there a calculus or formalism for measuring set relations between algorithm outputs?
Awarded Jul 29 at 4:34
I am looking for a detailed list of known reductions of NP-Complete problems
Awarded Jul 28 at 12:35
(post deleted or otherwise unavailable)
Awarded Jul 28 at 8:10
Using a certificate in the proof of NP hardness
Awarded Jul 27 at 5:20
1
2 3 4 5
…
73

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.