Theoretical Computer Science

Enlightened

 Enlightened
First to answer and accepted with score of 10 or more. This badge can be awarded multiple times.
Awarded 1314 times.
Why the "balanced vs constant function" problem is not a proof that P ≠ BPP?
Awarded yesterday
Where is the model theory in programming language theory?
Awarded May 25 at 10:11
Computational Complexity of Computer Vision Problems
Awarded May 15 at 9:51
What is the formal definitions of the reduction related to the "call/cc" (call with the current continuation) operator?
Awarded Apr 6 at 10:17
Fault-tolerant programming languages / paradigms?
Awarded Mar 30 at 23:33
Find odd-ranked numbers from a list
Awarded Mar 28 at 23:42
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
Awarded Feb 24 at 12:09
Strong normalization property of CoC inside CoC
Awarded Feb 7 at 12:06
Is #P contained in PSPACE?
Awarded Jan 29 at 15:41
Algebraic equivalent of SAT?
Awarded Jan 9 at 1:18
Explaining monad transformers in categorical terms
Awarded Dec 29, 2022 at 13:32
Did Jinliang Wang solve the P versus NP problem?
Awarded Dec 27, 2022 at 17:35
Is $PSPACE$ believed to be different than $PP$?
Awarded Dec 15, 2022 at 14:37
Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?
Awarded Dec 8, 2022 at 11:21
How do separations in of query complexities imply complexity class separations relative to oracles?
Awarded Dec 8, 2022 at 11:21
How to tell if an effect is algebraic?
Awarded Nov 14, 2022 at 13:09
Unique $k$-SAT benchmarks
Awarded Nov 4, 2022 at 18:26
Is Church-pentation implementable in Agda?
Awarded Nov 4, 2022 at 14:11
Number of permutations that satisfy a given set of comparisons
Awarded Oct 14, 2022 at 23:21
$k$-clique in $k$-partite graph
Awarded Oct 13, 2022 at 11:52
Hartmanis-Stearns conjecture and the computable transcendental numbers
Awarded Sep 21, 2022 at 4:02
Is the maximum independent set in cubic planar graphs NP-complete?
Awarded Aug 1, 2022 at 21:01
Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic
Awarded Jun 9, 2022 at 15:40
The complexity of the permanent of low rank matrices
Awarded Jun 8, 2022 at 15:05
Are there survey papers in theoretical computer science?
Awarded May 28, 2022 at 9:01
How to show that the median cannot be maintained in $O(1)$ time?
Awarded Apr 30, 2022 at 7:32
"Spurious" Type Equivalences in MLSub/Algebraic Subtyping
Awarded Apr 28, 2022 at 4:32
Generating Graphs with Trivial Automorphisms
Awarded Apr 22, 2022 at 23:18
The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis
Awarded Apr 9, 2022 at 9:04
Step-indexing: Where to begin?
Awarded Mar 24, 2022 at 8:33
$AC^0$[subexp] vs. NC
Awarded Mar 23, 2022 at 11:26
Why does it matter how difficult a proof is?
Awarded Mar 4, 2022 at 18:05
Finding appropriate spanning tree of connected bipartite graph
Awarded Jan 21, 2022 at 17:41
Find research partner (profession and beginner)
Awarded Jan 15, 2022 at 14:47
Swapping arguments of variables in higher-order pattern unification
Awarded Dec 30, 2021 at 14:51
Universal and existential types
Awarded Dec 14, 2021 at 0:51
Which universities in the U.S. are doing research in type theory?
Awarded Dec 2, 2021 at 18:06
The entropy of a convolution over the hypercube
Awarded Dec 1, 2021 at 13:35
Travelling Salesman and Planar Travel - Generalized TSP
Awarded Nov 30, 2021 at 23:36
Full names of C. K. Chow and C. N. Liu
Awarded Nov 22, 2021 at 17:40
Can we approximate the number of words accepted by an NFA?
Awarded Nov 12, 2021 at 4:31
Does Approx Carathéodory's theorem implies dimensionality reduction
Awarded Nov 4, 2021 at 22:40
Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$
Awarded Nov 2, 2021 at 7:17
Is there an efficient beta-equivalence algorithm?
Awarded Nov 1, 2021 at 18:35
Cartesian factorization of a finite set of n-tuples
Awarded Oct 19, 2021 at 16:33
Why is HAMILTONIAN CYCLE so different from PERMANENT?
Awarded Oct 17, 2021 at 8:11
What is the connection between moments of Gaussians and perfect matchings of graphs?
Awarded Oct 2, 2021 at 10:56
Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?
Awarded Sep 23, 2021 at 18:16
How to acknowledge answers of TCS in the paper?
Awarded Sep 9, 2021 at 14:07
Can theoretical computer science be applied in social sciences?
Awarded Aug 24, 2021 at 18:03
Subexponential hardness assumption
Awarded Aug 14, 2021 at 1:27
What are the obstructions to extending $L=SL$ to $L=NL$?
Awarded Jul 29, 2021 at 1:20
Natural examples of context-sensitive languages from practice
Awarded Jul 18, 2021 at 19:56
Sparsification Lemma for k-SAT and Exponential Time Hypothesis
Awarded Jul 4, 2021 at 22:02
What are some standard books/papers on Information Theory?
Awarded Jun 30, 2021 at 6:48
Existing implementation of Scott's reduction?
Awarded Jun 19, 2021 at 18:32
Are there two definitions of Cobham's thesis?
Awarded Jun 18, 2021 at 21:57
Trade off between time and query complexity
Awarded Jun 15, 2021 at 9:10
A Question on Convex Conjugate Duality for KL Divergence
Awarded Jun 11, 2021 at 9:16
Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$
Awarded Jun 7, 2021 at 15:36
1
2 3 4 5
…
22

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.