Theoretical Computer Science

Scholar

 Scholar
Ask a question and accept an answer.
Awarded 2448 times.
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
Awarded 9 hours ago
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 '21 at 14:06
What final state does simplified Linz Ĥ applied to ⟨Ĥ⟩ transition to? [closed]
Awarded Dec 26 '21 at 20:51
Alternative to LBA for recognising context-sensitive languages
Awarded Dec 24 '21 at 16:17
Set cover with rewards
Awarded Dec 20 '21 at 15:25
3-SAT runtime if an optimal order to eliminate possible solutions is known
Awarded Dec 13 '21 at 4:51
Algorithm for finding traffic equilibrium
Awarded Dec 11 '21 at 18:25
Which universities in the U.S. are doing research in type theory?
Awarded Dec 2 '21 at 17:55
Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
Awarded Nov 25 '21 at 8:17
Q: Trusting program output from an untrusted machine
Awarded Nov 24 '21 at 2:40
Is there a precise definition for big O notation with 2 or more variables [closed]
Awarded Nov 22 '21 at 15:26
Hardness of computing the dimension of an integral polytope?
Awarded Nov 16 '21 at 10:32
What is the complexity of HORN-2CNF entailment?
Awarded Nov 15 '21 at 12:04
Effect of HoTT/Univalence Axiom on equality between terms of inductive types?
Awarded Nov 14 '21 at 23:41
Finding a path in a graph hitting a particular vertex
Awarded Nov 6 '21 at 5:48
exact path cover for undirected graph
Awarded Oct 24 '21 at 19:02
star height of star-free languages
Awarded Oct 19 '21 at 10:21
Divide and Conquer Algorithm for 1-Median Problem
Awarded Oct 11 '21 at 6:26
Upper bound on the expected number of correct bits via a "lossy compression"
Awarded Oct 3 '21 at 10:56
Non-random errors with a Reed Solomon code
Awarded Sep 28 '21 at 5:12
How does axiom K contradict univalence?
Awarded Sep 26 '21 at 0:27
Is function composition associative in non-pure programming languages?
Awarded Sep 22 '21 at 18:21
Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses
Awarded Sep 19 '21 at 10:34
Does Horn SAT (Horn formula in CNF) have an integral polytope?
Awarded Sep 13 '21 at 22:18
Partition a graph into two clusters
Awarded Sep 10 '21 at 22:42
Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?
Awarded Sep 8 '21 at 23:04
Computational complexity of Turán-type problems
Awarded Sep 7 '21 at 18:17
Relationship between Random Graph Theory and TCS
Awarded Sep 1 '21 at 19:41
Some issues with proof of Fundamental Theorem of Statistical learning
Awarded Aug 29 '21 at 11:08
Recursive generic oracles
Awarded Aug 25 '21 at 15:25
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Awarded Aug 24 '21 at 18:27
Can theoretical computer science be applied in social sciences?
Awarded Aug 24 '21 at 17:41
A variant of two-counter machine
Awarded Aug 22 '21 at 13:11
Lexicographic Boolean satisfiability
Awarded Aug 13 '21 at 19:31
Max-k-cut with negative edge weights
Awarded Aug 11 '21 at 5:20
What is tightest known (VC-style) sample complexity bound for uniform convergence of empirical means?
Awarded Aug 6 '21 at 14:02
Can I research in web technologies with an academic approach?
Awarded Aug 3 '21 at 2:47
(post deleted or otherwise unavailable)
Awarded Jul 28 '21 at 1:51
Fixed points of fixed-point combinator?
Awarded Jul 15 '21 at 5:31
Can you embed a Turing Machine into the Pi calculus with just one replication operator?
Awarded Jul 15 '21 at 1:51
How to acknowledge answers of TCS in the paper?
Awarded Jul 7 '21 at 12:19
NEXPTIME-completeness with more time for reductions
Awarded Jun 29 '21 at 15:32
Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy
Awarded Jun 28 '21 at 17:48
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
Awarded Jun 28 '21 at 14:18
Is time-slot matchmaking NP-hard?
Awarded Jun 24 '21 at 19:18
Proving that a given formula in LTL is the smallest way to express it
Awarded Jun 17 '21 at 16:11
Find research partner (profession and beginner)
Awarded Jun 5 '21 at 17:06
What is the polynomial representation of the Hamming weight function?
Awarded Jun 1 '21 at 16:45
Example of an context-sensitive language with a specific number of words of length $n$
Awarded May 29 '21 at 8:58
Resource for Understanding this Notation [closed]
Awarded May 27 '21 at 21:41
Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$
Awarded May 25 '21 at 9:10
Two valued variant of subset sum problem
Awarded May 22 '21 at 21:32
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Awarded May 19 '21 at 7:46
Linear Integer Arithmetic Satisfiability with Three Literals [closed]
Awarded May 10 '21 at 1:05
What does x.y notation mean?
Awarded May 9 '21 at 6:10
Finding vertex separator such that the induced subgraph has minimal number of edges
Awarded May 8 '21 at 21:31
Are there strongly normalizing lambda terms that cannot be given a System F type?
Awarded May 2 '21 at 21:32
upper bound on the total number of fixed-length paths in an acyclic graph [closed]
Awarded May 2 '21 at 1:45
1
2 3 4 5
…
41

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.