Theoretical Computer Science

Scholar

 Scholar
Ask a question and accept an answer.
Awarded 2410 times.
Proving that a given formula in LTL is the smallest way to express it
Awarded 2 days ago
Find research partner (profession and beginner)
Awarded Jun 5 at 17:06
What is the polynomial representation of the Hamming weight function?
Awarded Jun 1 at 16:45
Example of an context-sensitive language with a specific number of words of length $n$
Awarded May 29 at 8:58
Resource for Understanding this Notation [closed]
Awarded May 27 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 at 9:10
Two valued variant of subset sum problem
Awarded May 22 at 21:32
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Awarded May 19 at 7:46
Linear Integer Arithmetic Satisfiability with Three Literals [closed]
Awarded May 10 at 1:05
What does x.y notation mean?
Awarded May 9 at 6:10
Finding vertex separator such that the induced subgraph has minimal number of edges
Awarded May 8 at 21:31
Are there strongly normalizing lambda terms that cannot be given a System F type?
Awarded May 2 at 21:32
upper bound on the total number of fixed-length paths in an acyclic graph [closed]
Awarded May 2 at 1:45
Pi-type over a list in dependent type theory
Awarded Apr 29 at 13:26
Are uniqueness rules converse to introduction rules?
Awarded Apr 29 at 11:33
Relative error estimation of a special type of GapP function
Awarded Apr 29 at 8:21
Where, if any, is there currently any research being done on the subject of ternary computers? [closed]
Awarded Apr 26 at 20:57
Why does LTL equivalence (with next oeprator) implie trace equivalence in finite transition machines?
Awarded Apr 20 at 10:49
KRW Conjecture: separation of NC^1 and P
Awarded Apr 11 at 10:25
Approximating Independent Dominating set on bipartite graphs
Awarded Mar 30 at 2:03
Maximum weight matching with classes of edges in a multi-edge bipartite graph
Awarded Mar 28 at 18:41
How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?
Awarded Mar 25 at 8:23
Do theoretical computer scientists work more with proving theorems, or work more with data?
Awarded Mar 24 at 16:05
Where is $MA$ more relevant than $\exists BPP$?
Awarded Mar 20 at 20:07
Subset sum for lists [closed]
Awarded Mar 15 at 13:57
Has parameterized complexity led to better algorithms?
Awarded Mar 15 at 13:20
$ACC^0$ implementation of a boolean function
Awarded Mar 1 at 15:17
Definition of Rabin acceptance condition for omega automatons [closed]
Awarded Feb 28 at 12:34
A stronger Flow Decomposition Theorem?
Awarded Feb 22 at 8:21
Problem conditions to use Laplacian solvers
Awarded Feb 20 at 15:28
It is known that $L \subsetneq PH$?
Awarded Feb 19 at 19:26
Effect of self loops on mixing time?
Awarded Feb 19 at 19:19
VC generalization bound extended to other types of target functions
Awarded Feb 15 at 17:04
NP-Completeness of Finding Minimum Automaton, in Gold's paper
Awarded Feb 14 at 18:41
How to solve an unification problem on $\mathbb{N}$?
Awarded Feb 13 at 12:27
Reduction of a language to a shorter equivalent [closed]
Awarded Feb 11 at 15:35
A sorting algorithm that uses the minimum comparasions possible
Awarded Feb 10 at 18:18
(post deleted or otherwise unavailable)
Awarded Feb 9 at 8:25
Multi agent path following with collision avoidance with pre-determined path
Awarded Feb 7 at 19:18
NP-hardness of a planar SAT variant
Awarded Jan 31 at 23:26
Context weakening as an explicit rule for languages of the the lambda cube?
Awarded Jan 22 at 22:50
Variable wire weights in DLOGTIME-uniform circuits
Awarded Jan 22 at 16:34
Number of 4 cycles
Awarded Jan 15 at 16:49
What is the complexity of model checking Process Logic (LTL fragment)?
Awarded Jan 10 at 20:19
Knowing if there are two solutions to the subset sum problem
Awarded Jan 8 at 16:28
Is there any such thing as a non-nested hierarchy?
Awarded Jan 6 at 19:32
Minimizing $L_2$ norm of a vector with two distinct entries
Awarded Jan 3 at 11:42
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Awarded Dec 29 '20 at 11:22
Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time
Awarded Dec 28 '20 at 21:10
“Parity testing set” for disjoint pairs of sets
Awarded Dec 22 '20 at 9:36
Standard Name for a vertex removal like operation
Awarded Dec 19 '20 at 17:17
Complexity of a satisfiability problem
Awarded Dec 11 '20 at 20:18
Composition theorem for randomized communication complexity
Awarded Dec 9 '20 at 17:56
Why is plus-comm a b $:\equiv$ refl (plus a b) not a proof of the commutativity of addition?
Awarded Nov 30 '20 at 16:19
how to define “correlation” between languages?
Awarded Nov 29 '20 at 17:02
Is Descriptive Complexity dead?
Awarded Nov 27 '20 at 21:32
What's the intuition behind Rademacher complexity?
Awarded Nov 19 '20 at 10:10
Is solving the following system of boolean equations NP-hard?
Awarded Nov 17 '20 at 11:25
Computability and continuity
Awarded Nov 10 '20 at 17:12
Busy Beaver Equivalent for the Untyped Lambda Calculus
Awarded Nov 3 '20 at 3:55
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.