Results from the 2022 Developer Survey are now available
Theoretical Computer Science

Scholar

 Scholar
Ask a question and accept an answer.
Awarded 2490 times.
Is there a relation between the techniques used by Dan Willard, versus those of Brown and Palsberg, to exclude diagonalization?
Awarded yesterday
How can arbitrary combinational logic be done with just addition and multiplication?
Awarded 2 days ago
NLOGTIME versus $\exists$DLOGTIME
Awarded Jun 24 at 11:55
Enumerating all simply typed lambda terms of a given type
Awarded Jun 23 at 17:55
Trying to understand the intuition behind Yao's Minimax Principle
Awarded Jun 19 at 17:41
What are the application of Scott-Topology in theoretical computer science?
Awarded Jun 10 at 17:56
What is a "Covering Function"?
Awarded Jun 10 at 9:12
What is the computational power of the Calculus of Constructions?
Awarded Jun 8 at 14:45
Question about "Free-ness" of Free SCWF
Awarded Jun 8 at 4:16
Showing that a modification of an NP-Complete problem is also NP-Complete
Awarded Jun 3 at 22:12
Are there survey papers in theoretical computer science?
Awarded May 28 at 3:51
Similarities and differences between Pie and popular languages with dependent types
Awarded May 27 at 22:00
Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem
Awarded May 26 at 21:03
Is QMA known to contain Co-NP?
Awarded May 24 at 11:01
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
Awarded May 20 at 13:11
CFG - How can I describe a language that dictates a word and its opposite?
Awarded May 17 at 11:21
Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)
Awarded May 13 at 13:47
Can you always throw away the types when evaluating lambda expressions?
Awarded May 13 at 4:33
Complexity of matrix diagonalization
Awarded May 8 at 12:15
How to find the size of an ϵ-net of a vector space?
Awarded May 8 at 7:34
Maximal uniquely decodable codes
Awarded Apr 29 at 9:30
Operations on Sentential Decision Diagrams
Awarded Apr 29 at 8:11
How to show that the median cannot be maintained in $O(1)$ time?
Awarded Apr 27 at 16:34
Words of the form $(a^n b)^n$ in a context-free language
Awarded Apr 26 at 17:07
What's the logical counterpart to jumps with arguments on CPS terms?
Awarded Apr 25 at 14:01
Restriction of a convex function to {0, 1}^n
Awarded Apr 23 at 23:33
VC-dimension of the infinite intersection of two spheres
Awarded Apr 21 at 9:41
No free lunch theorem
Awarded Apr 18 at 9:36
Complexity of finding approximate solutions for systems of polynomial equations
Awarded Apr 11 at 23:36
Proving a property of minimal st-separators that are not minimum st-separators
Awarded Apr 6 at 6:31
Is there a way to define dependent types without explicit substitutions internally within agda?
Awarded Mar 27 at 11:40
Another variation of $k$-means problem in the plane
Awarded Mar 23 at 22:33
Is the weighted sum of subset prefix product problem NP-hard?
Awarded Mar 22 at 21:05
Question about BPP complexity class [closed]
Awarded Mar 16 at 14:04
Name for words without squared symbols
Awarded Mar 8 at 21:42
Binary Trees for Nearest Neighbor Search
Awarded Mar 6 at 10:48
Maximum Vertex Cover
Awarded Mar 1 at 10:27
Why does it matter how difficult a proof is?
Awarded Feb 23 at 14:19
Intuitive way to handle variable binding
Awarded Feb 16 at 1:40
The complexity of 3SAT
Awarded Feb 11 at 11:16
Proof of SPFA's worst-case complexity?
Awarded Feb 10 at 16:27
Interpolation to find polynomial multivariate derivative
Awarded Feb 3 at 18:56
Why can't opaque optics form a category?
Awarded Jan 25 at 0:10
Is there an Upper Bound on Number of Redundant Clauses in a satisfiable $3-SAT$?
Awarded Jan 23 at 1:20
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
Awarded Jan 22 at 14:47
What are the issues with a set-like interpretation of quantifiers in type theory?
Awarded Jan 9 at 19:17
How to show that Color Tiles is NP-Complete
Awarded Jan 9 at 0:27
Validity problem of intuitionistic two-variable logic
Awarded Dec 29, 2021 at 14:06
Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? [closed]
Awarded Dec 26, 2021 at 20:51
Alternative to LBA for recognising context-sensitive languages
Awarded Dec 24, 2021 at 16:17
Set cover with rewards
Awarded Dec 20, 2021 at 15:25
3-SAT runtime if an optimal order to eliminate possible solutions is known
Awarded Dec 13, 2021 at 4:51
Algorithm for finding traffic equilibrium
Awarded Dec 11, 2021 at 18:25
Which universities in the U.S. are doing research in type theory?
Awarded Dec 2, 2021 at 17:55
Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
Awarded Nov 25, 2021 at 8:17
Q: Trusting program output from an untrusted machine
Awarded Nov 24, 2021 at 2:40
Is there a precise definition for big O notation with 2 or more variables [closed]
Awarded Nov 22, 2021 at 15:26
Hardness of computing the dimension of an integral polytope?
Awarded Nov 16, 2021 at 10:32
What is the complexity of HORN-2CNF entailment?
Awarded Nov 15, 2021 at 12:04
Effect of HoTT/Univalence Axiom on equality between terms of inductive types?
Awarded Nov 14, 2021 at 23:41
1
2 3 4 5
…
42

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.