Theoretical Computer Science

Scholar

 Scholar
Ask a question and accept an answer.
Awarded 2387 times.
$ACC^0$ implementation of a boolean function
Awarded Mar 1 at 15:17
Definition of Rabin acceptance condition for omega automatons
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
Is this homework problem on T-joins wrong? [closed]
Awarded Nov 1 '20 at 19:57
Can the halting problem be solved probabilistically? [closed]
Awarded Oct 20 '20 at 12:10
VC dimension for balanced binary decision trees
Awarded Oct 17 '20 at 8:26
Time complexity of finding chain decomposition of partially ordered set
Awarded Oct 17 '20 at 1:02
On the usage of Arora and Barak's main lemma in their proof of the PCP theorem
Awarded Oct 16 '20 at 15:31
Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?
Awarded Oct 15 '20 at 23:11
Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph
Awarded Oct 9 '20 at 20:31
Complexity of type inference in the simply typed lambda calculus
Awarded Oct 8 '20 at 15:20
Series-parallel DAG characterization
Awarded Oct 2 '20 at 13:55
Sum-of-Squares Certificates
Awarded Sep 29 '20 at 22:47
Rademacher Complexity of the Composition with an Indicator
Awarded Sep 27 '20 at 1:57
Dependence of decidability on the encoding of Turing machines
Awarded Sep 21 '20 at 8:25
Can you find a counter-example for this proposed Graph Isomorphism algorithm?
Awarded Sep 19 '20 at 12:10
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
Awarded Sep 12 '20 at 23:17
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Awarded Sep 9 '20 at 17:49
Pi-calculus (or session types) - proof for weakening lemma
Awarded Sep 8 '20 at 10:02
Graphs-like data structure with weighted vertices
Awarded Sep 7 '20 at 17:36
Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures
Awarded Sep 6 '20 at 3:28
Isomorphic graph embeddings in the Euclidean Space
Awarded Aug 20 '20 at 14:20
Maximum subarray problem with weights
Awarded Aug 17 '20 at 21:37
Complexity of acyclicity of a “nondeterministic” graph
Awarded Aug 15 '20 at 9:48
Formal theory about explaining algorithms
Awarded Aug 12 '20 at 11:05
How can I find the PhD thesis of C.A. Ellis?
Awarded Aug 11 '20 at 8:25
Rewrite relations - proof of correctness
Awarded Aug 9 '20 at 8:12
An efficient Beta-Equivalence algorithm?
Awarded Aug 4 '20 at 2:04
approximate maximum clique given vertex cover
Awarded Jul 21 '20 at 17:57
1
2 3 4 5
…
40