Theoretical Computer Science

Revival

 Revival
Answer more than 30 days after a question was asked as first answer scoring 2 or more. This badge can be awarded multiple times.
Awarded 632 times.
Complexity of computing invertible functions with reversible circuits
Awarded Mar 1, 2018 at 23:52
Beating naive dynamic programming: examples similar to integer partitions?
Awarded Feb 16, 2018 at 14:21
Complexity of propositional LTL with past operators and freeze quantifier?
Awarded Feb 15, 2018 at 10:26
What is computational complexity of calculating the Variance-Covariance Matrix?
Awarded Feb 12, 2018 at 14:45
Minimal Cost of Eulerian Path
Awarded Feb 11, 2018 at 14:52
What are some standard books/papers on Information Theory?
Awarded Jan 25, 2018 at 17:11
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
Awarded Jan 23, 2018 at 15:41
Automated proving that a program doesn't halt
Awarded Jan 12, 2018 at 22:16
Suggested approach to cover data structure literature
Awarded Jan 9, 2018 at 9:30
Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?
Awarded Jan 6, 2018 at 7:38
Cases of Linear programming known to be in $NC$?
Awarded Dec 28, 2017 at 6:47
Relation between interval temporal logic and linear temporal logic
Awarded Dec 24, 2017 at 18:15
Problems in NC not known to lie in NC2
Awarded Dec 22, 2017 at 15:46
Are there variants of visibly pushdown automata that allow pushing of words onto the stack?
Awarded Nov 30, 2017 at 10:22
Good algorithms to solve ATSP
Awarded Nov 24, 2017 at 14:00
To what extent, computational ability for hard tasks helps in solving easy tasks
Awarded Nov 2, 2017 at 5:33
Bipartite matching with degree domination
Awarded Oct 4, 2017 at 2:52
How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?
Awarded Oct 2, 2017 at 0:12
Knot Recognition as a Proof of Work
Awarded Sep 30, 2017 at 16:57
Time Hierarchies in DSPACE(O(s(n)))
Awarded Sep 23, 2017 at 7:47
String version of even-odd partition problem
Awarded Sep 5, 2017 at 8:11
Automata recognizing $X^*$ for a finite code $X$
Awarded Sep 4, 2017 at 12:00
Are there distribution properties which are "maximally" hard to test?
Awarded Aug 14, 2017 at 18:00
An analog of DP for the second level of the polynomial hierarchy
Awarded Aug 11, 2017 at 16:58
Parse structure of a range concatenation grammar (RCG)
Awarded Aug 2, 2017 at 4:52
Graph factors of maximum weight
Awarded Jul 25, 2017 at 13:05
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
Awarded Jul 17, 2017 at 21:26
DTIME and PSPACE
Awarded Jul 14, 2017 at 9:41
Name for "uniformly polynomial" subclass of XP?
Awarded Jul 13, 2017 at 12:04
Is it possible to unambiguously read back λ terms from interaction nets without node types?
Awarded Jul 4, 2017 at 15:40
Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?
Awarded Jul 1, 2017 at 12:26
Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
Awarded Jun 19, 2017 at 1:55
Does a universal index exist?
Awarded Jun 17, 2017 at 13:12
Low rank Log rank conjecture
Awarded Jun 7, 2017 at 17:28
Gap-Hamming with different "threshold" (i.e., not $n/2$)
Awarded Jun 3, 2017 at 21:00
research papers for undergraduate students
Awarded Jun 2, 2017 at 12:55
Graph addition chains
Awarded May 26, 2017 at 14:30
Is the following problem NP hard?
Awarded May 21, 2017 at 21:48
Increasing the capacity to maximize the min cut
Awarded May 17, 2017 at 18:50
Scheduling to maximize idle time
Awarded May 16, 2017 at 8:25
Does Rabin/Yao exist (at least in a form that can be cited)?
Awarded Apr 19, 2017 at 10:59
Decide whether a point is a vertex of a polytope?
Awarded Apr 17, 2017 at 7:50
Hard extendability problems
Awarded Apr 7, 2017 at 15:48
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Awarded Apr 3, 2017 at 3:18
Approximate degree of $\textrm{AC}^0$
Awarded Mar 31, 2017 at 19:37
What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?
Awarded Mar 29, 2017 at 14:06
Is there a result in computability theory that does not relativize?
Awarded Mar 27, 2017 at 8:12
Pathfinding search over a space with known changing costs
Awarded Mar 27, 2017 at 0:17
(post deleted or otherwise unavailable)
Awarded Mar 26, 2017 at 18:40
How can non-terminating $\lambda$-terms be turned into fixed-point combinators?
Awarded Mar 19, 2017 at 20:10
How to state the adequacy of an encoding of lambda calculus in itself?
Awarded Mar 13, 2017 at 15:25
NP-hardness of a bilinear program?
Awarded Mar 12, 2017 at 8:28
A maximization problem containing summation and multiplication
Awarded Mar 9, 2017 at 21:34
Do there exist groups with word problems in arbitrary P-degrees?
Awarded Mar 2, 2017 at 20:32
Has this generalization of the vertex cover problem been researched?
Awarded Feb 23, 2017 at 4:44
Quasi-polynomial time algorithm for permutation group isomorphism
Awarded Feb 16, 2017 at 2:21
Understanding between lambda-calculus and other abstract machines (like Turing machine and Markov algorithm)
Awarded Feb 8, 2017 at 12:12
Status of PP-completeness of MAJ3SAT
Awarded Feb 7, 2017 at 20:21
Why SHA-224 and SHA-256 use different initial values?
Awarded Feb 7, 2017 at 19:17
Type checking, Hypothetical judgments, meaning explanations and computational type theory
Awarded Feb 7, 2017 at 4:25
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.