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.
Implementation of Wilf-Zeilberger and related methods
Awarded Feb 1, 2017 at 17:27
Real number $p$ such that a $p$-coin makes the undecidable decidable
Awarded Jan 28, 2017 at 14:58
Minimizing residual finite state automata
Awarded Jan 26, 2017 at 10:30
Is there a theory that combines category theory/abstract algebra and computational complexity?
Awarded Jan 21, 2017 at 14:56
Generalizing linear interpolation to posets
Awarded Jan 21, 2017 at 5:16
Can one amplify P=NP beyond P=PH?
Awarded Jan 14, 2017 at 21:57
Can one amplify P=NP beyond P=PH?
Awarded Jan 12, 2017 at 16:46
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
Awarded Jan 11, 2017 at 10:17
Is the 2016 implementation of Shor's algorithm really scalable?
Awarded Jan 2, 2017 at 22:31
Why use two separate tables in cuckoo hashing?
Awarded Dec 22, 2016 at 10:34
Is counting the words in a finite regular language #P-complete?
Awarded Dec 19, 2016 at 17:41
Defining primitive recursive functions over general data types
Awarded Dec 16, 2016 at 23:44
A property of suffix-free regular languages of maximal state complexity for the reverse operation
Awarded Dec 12, 2016 at 5:48
Maximum computational power of a C implementation
Awarded Nov 24, 2016 at 22:23
Does every NO instance of this promise problem have a local refutation?
Awarded Nov 21, 2016 at 16:26
Random 3-SAT: What is the consensus experimental range of the threshold?
Awarded Nov 15, 2016 at 16:23
Minimizing a submodular function given noisy oracle access
Awarded Nov 7, 2016 at 0:21
Super Mario Galaxy problem
Awarded Oct 31, 2016 at 10:53
Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)
Awarded Oct 26, 2016 at 14:42
FPT algorithm for mixed integer program
Awarded Oct 8, 2016 at 14:27
How do I figure out how to combine simpler quantum gates to create the gate I want?
Awarded Oct 6, 2016 at 11:49
what is "one-to-one reduction from a function f to another function g"
Awarded Oct 2, 2016 at 4:59
Triangular Mesh Reordering - Huddling Triangles
Awarded Sep 23, 2016 at 9:27
Are there any heuristics that works solely on graphs?
Awarded Sep 9, 2016 at 19:24
Encoding quadratic constraints in a constraint satisfaction problem into SAT
Awarded Sep 5, 2016 at 8:53
Parallel algorithms for reachability in directed planar graphs
Awarded Aug 12, 2016 at 2:20
Which graph parameters are NOT concentrated on random graphs?
Awarded Aug 10, 2016 at 3:46
Forms of types in the calculus of constructions
Awarded Aug 10, 2016 at 0:30
Is there an approximation algorithm for MAX k DOUBLE SET COVER?
Awarded Jul 16, 2016 at 17:22
Deciding whether an NC${}^0_3$ circuit computes a permutation or not
Awarded Jul 15, 2016 at 18:47
Is joint Kolmogorov Complexity order invariant?
Awarded Jul 11, 2016 at 15:28
Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs
Awarded Jul 8, 2016 at 12:01
Understanding efficient classical simulation of quantum computing
Awarded Jul 8, 2016 at 10:39
What's "pseudo time" when used in comparison with semaphores
Awarded Jun 28, 2016 at 9:14
Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?
Awarded Jun 26, 2016 at 2:15
One sided approximation degree
Awarded Jun 9, 2016 at 6:19
Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism
Awarded May 30, 2016 at 15:36
(post deleted or otherwise unavailable)
Awarded May 5, 2016 at 15:36
Patience Sort+ ping pong merge implementation
Awarded May 4, 2016 at 19:11
How does the Multiplicative Weights Update method maximize entropy?
Awarded Apr 30, 2016 at 20:53
DAG reachability with O(n log n) space and O(log n)-time queries?
Awarded Apr 25, 2016 at 6:40
Efficient Shamir secret sharing reconstruction
Awarded Apr 10, 2016 at 15:14
Is there a set theoretic way to look at SQL?
Awarded Mar 27, 2016 at 3:50
Is there any hidden subgroup of a symmetric group which can be efficiently determined?
Awarded Mar 17, 2016 at 17:36
Entropy inequality of joint von Neumann entropy given some marginal inequalities
Awarded Feb 6, 2016 at 5:56
Is `sort` typeable on elementary affine logic?
Awarded Feb 4, 2016 at 18:37
Can we not output the Kolmogorov complexity?
Awarded Jan 31, 2016 at 21:58
How is the MA version of SETH proven to be false?
Awarded Jan 20, 2016 at 3:52
Subset of a bipartite graph with maximal number of minimal unmatched vertices
Awarded Jan 20, 2016 at 1:19
Poly-time Algorithm for Non-Linear Optimization
Awarded Jan 18, 2016 at 15:14
Definition of Planar 3-SAT
Awarded Jan 12, 2016 at 19:32
(post deleted or otherwise unavailable)
Awarded Jan 7, 2016 at 4:43
Approximation algorithms for the maximum $2$-independence set problem
Awarded Jan 1, 2016 at 14:01
Sparse subgraph preserving rooted edge connectivity up to $k$
Awarded Dec 31, 2015 at 8:27
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Awarded Dec 24, 2015 at 17:41
maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph
Awarded Dec 23, 2015 at 22:20
On optimality of Grover algorithm with high success probability
Awarded Dec 23, 2015 at 16:10
Maintain mex with efficient union
Awarded Dec 21, 2015 at 12:39
Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time
Awarded Dec 20, 2015 at 6:03
Complete problems or alternative definitions of the complexity class NP^GI?
Awarded Dec 16, 2015 at 6:57
1
…
3 4
5
6 7
…
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.