Theoretical Computer Science

Student

 Student
First question with score of 1 or more.
Awarded 4795 times.
Equivalence between GNFA and NFA/DFA
Awarded 2 days ago
Assignment problem for forming pairs of real numbers
Awarded Sep 24 at 19:17
Fast algorithms for time bounded Kolmogorov complexity
Awarded Sep 24 at 1:48
Recent advances in computer science since 2010?
Awarded Sep 23 at 11:45
How does NP-completess of decision problems relate to NP-completeness of search problems?
Awarded Sep 13 at 23:32
Is this proof for completeness of regular model checking correct?
Awarded Sep 13 at 16:27
If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?
Awarded Sep 12 at 20:58
Encoding of continuous functions in PPAD
Awarded Sep 11 at 15:10
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
Awarded Sep 8 at 13:31
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
Awarded Sep 8 at 10:55
Is there a well-defined notion of an “R/poly” complexity class?
Awarded Sep 7 at 8:09
Is is true that every monad transformer is equivalent to its underlying/base monad?
Awarded Sep 6 at 12:30
Hardness of maximization of a univariate polynomial (as a function of its degree)
Awarded Aug 28 at 1:57
How "Algebrization" is "A New Barrier in Complexity Theory"?
Awarded Aug 22 at 23:40
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
Awarded Aug 22 at 21:19
Utility of automated alphabet abstraction in automata learning?
Awarded Aug 21 at 5:17
Structural Complexity Theory References
Awarded Aug 20 at 22:46
Application LCL definition to vertex coloration
Awarded Aug 20 at 18:41
Semi-Thue systems and deterministic computation
Awarded Aug 19 at 12:41
Overlap operator for simple ( regex-like ) Patterns
Awarded Aug 19 at 10:56
Testing positivity of a function by an IP system?
Awarded Aug 18 at 10:15
Name and complexity of a stone placement puzzle
Awarded Aug 18 at 9:15
How is FNP defined? Or, is FNP closed under relaxation?
Awarded Aug 15 at 17:51
(post deleted or otherwise unavailable)
Awarded Aug 7 at 0:34
Using a certificate in the proof of NP hardness
Awarded Aug 3 at 23:16
Real life application of two-way DFA
Awarded Aug 1 at 22:32
Shortest Common Supersequence of Permutations
Awarded Jul 31 at 17:55
I am looking for a detailed list of known reductions of NP-Complete problems
Awarded Jul 28 at 14:40
Fractional but not integer multi-commodity minimum cost flow
Awarded Jul 26 at 9:51
Can you regain the Church-Rosser property in languages with continuations?
Awarded Jul 26 at 6:43
Finding $k \times k$ rectangle in a matrix with maximum sum
Awarded Jul 24 at 0:57
clique problem in graphs with bounded degree
Awarded Jul 21 at 15:41
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Awarded Jul 18 at 18:56
Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?
Awarded Jul 17 at 5:07
Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?
Awarded Jul 17 at 2:25
Two disjoint paths with minimum product of weights -NP-completeness
Awarded Jul 15 at 10:05
Maximizing merges with restrictions
Awarded Jul 14 at 22:32
Algorithm for comparing list elements backwards
Awarded Jul 14 at 21:57
Is data structure necessarily a functor?
Awarded Jul 14 at 9:33
Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?
Awarded Jul 13 at 5:26
Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG
Awarded Jul 12 at 17:40
Enumerating part of an arrangement
Awarded Jul 10 at 21:27
What is the solution of this equation on regular languages?
Awarded Jul 8 at 21:36
Information Bottleneck - Calculating the Mutual information between the Labels and the Features [closed]
Awarded Jul 6 at 8:46
Are MSO formulae expressible as existential SO formulae over arbitrary structures?
Awarded Jul 5 at 9:36
What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?
Awarded Jul 4 at 11:20
In the age of powerful AI, can all software be written using only tests?
Awarded Jul 3 at 14:34
What are the applications of Belief Revision?
Awarded Jun 29 at 19:49
Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing
Awarded Jun 28 at 19:21
General collection with the current state of complexity bounds of well-known unsolved problems?
Awarded Jun 27 at 23:16
Is the Moser-Tardos algorithm used in any real-world applications?
Awarded Jun 27 at 16:02
Why are impossibility results harder for uniform sparsest cut than non-uniform?
Awarded Jun 27 at 16:02
Maximum cardinality matching on DAGs
Awarded Jun 26 at 17:06
Does there exist constant overhead reduction between common cryptographic primitives?
Awarded Jun 24 at 23:31
Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?
Awarded Jun 24 at 23:31
Exploding number of homomorphisms
Awarded Jun 22 at 23:41
Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?
Awarded Jun 16 at 12:22
The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli
Awarded Jun 15 at 13:09
How do we show directly coNP is in MIP?
Awarded Jun 13 at 12:10
Most Matrices are Rigid
Awarded Jun 12 at 16:43
1
2 3 4 5
…
80

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.